量子搜索算法例题详解_量子算法与编程入门

量子搜索算法例题详解_量子算法与编程入门量子搜索算法Groversearch问题定义:Problem:f:{0,1,2,3,……,N−1}→{0,1}f:{0,1,2,3,……,N−1}→{0,1}找到f(x)=1的x解法经典解法:经典解法很简单,就是把每一个都看一遍,如果只有一个x对应的f(x)=1,那么平均是要看一半,才能找到那个x。时间复杂度O(N)量子解法:使用Groversea…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

量子搜索算法 Grover search

问题定义:

Problem:

f:{0,1,2,3,……,N−1}→{0,1}f:{0,1,2,3,……,N−1}→{0,1}

找到 f(x)=1 的x

解法

经典解法:

经典解法很简单,就是把每一个都看一遍,如果只有一个x对应的f(x)=1,那么平均是要看一半,才能找到那个x。

时间复杂度O(N)

量子解法:

使用Grover search 算法,时间复杂度在 O(根号N)

Grover search 算法

Grover search 算法一共分为两步:

  1. Phase Inversion
  2. Inversion about the Mean

然后不断的迭代这两步我们就能够得到结果了。

首先我们先看看这两个步骤分别在做什么:

我们把 f(x)=1的 |x〉 称为 x∗ ,我们要找的也就是这个 x∗ 。

Phase Inversion:

这一步主要是把 x∗ 的概率幅翻转,变成负数,而其他的保持不变。

即,量子搜索算法例题详解_量子算法与编程入门

Inversion about the Mean

量子搜索算法例题详解_量子算法与编程入门

用图可能更好表达这两个步骤究竟在做什么:

量子搜索算法例题详解_量子算法与编程入门

图1到图2,就是Phase Inversion,把x∗的概率幅翻转到了下面,图2中的虚线就是我的概率幅的平均值,图2到图3 就是我们的Inversion about the Mean,对着平均值翻转一次,其余x的概率幅是高于平均值的,所以 2μ−αx 让他们变小了,而我们的 x∗ 他的概率幅是个负数,所以 2μ−αx后他增加了。

不断的重复这个步骤, x∗ 他的概率幅会越来越大,最后我们测量的时候就会很容的找到他。

进行了 √N 后,他的概率幅就会达到 1/√2 ,算概率就是1/2。

那么接下来的问题就是,这些操作是怎么实现的?

Phase Inversion:

这个步骤要做的事情就是,

量子搜索算法例题详解_量子算法与编程入门

符号是和f(x)是否为1相关的,进一步化简就是 量子搜索算法例题详解_量子算法与编程入门

有没有一丝熟悉感?

把f(x)的结果给放到相位上去,这是我们在Parity Problem中就遇到的问题。

当时的解决方法是把答案比特变成 |−〉。

量子搜索算法例题详解_量子算法与编程入门

一般情况,如果我们打算放置答案的比特是 |b〉,那么输入的比特就是|b⊕f(x)〉

量子搜索算法例题详解_量子算法与编程入门

最后一个比特的值如果在|+〉|−〉坐标下测量,一定是 |−〉,f(x)的差别也变到了符号上,即 (−1)f(x)

Inversion about the Mean

把 αx变成 2μ−αx,这个就要比前一个麻烦了

这其实是要求我把现在的态对着 μ 翻转。

对着 μ 翻转会吗?

不太会。

但是我会对着 |0〉 的翻转啊。

对角线第一个值为1,其余为-1,非对角线的都为0。

量子搜索算法例题详解_量子算法与编程入门

这个矩阵轻而易举的可以让 |0〉 保持不变,非 |0〉的符号全都翻转。

量子变换要求矩阵式酉矩阵,这个矩阵很明显满足 UU†=U†U=I

接下来怎么做呢?

我们先把我们的态整体来一个从 |μ〉 到 |0〉 的旋转,对着 |0〉 翻转后,又从 |0〉 到 |μ〉 翻转回去。

|μ〉 是一个怎样的态?

所有的x的概率都一样,也就是我们的superposition 量子搜索算法例题详解_量子算法与编程入门

量子搜索算法例题详解_量子算法与编程入门|x〉 和 |0〉之间的相互转换,这就是我们最最熟悉的Hadamard Transform了

第二部分的电路图如下:

量子搜索算法例题详解_量子算法与编程入门

这个矩阵是可以直接计算的:

量子搜索算法例题详解_量子算法与编程入门

我这里直接给出答案,得到的矩阵值呢是下图左边的这个矩阵:
量子搜索算法例题详解_量子算法与编程入门

在对应的 αx的结果恰好是 量子搜索算法例题详解_量子算法与编程入门

而 量子搜索算法例题详解_量子算法与编程入门 恰好就是 2μ

至此,呈上最完整的电路图模块:

量子搜索算法例题详解_量子算法与编程入门

第一个H门是数据的初始化,第二个门是为了翻转 x∗,第三四五个门是为了对 |μ〉 翻转,二三四五这四个门就是要给重复的模块了,不断的重复他们就可以不断的提高 x∗的概率幅,最终找到 x∗。

 

参考资料:

Quantume Mechanics & Quantume Computation Lecture 11

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234995.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • c++写windows窗口程序_windows7硬件配置要求

    c++写windows窗口程序_windows7硬件配置要求原文转载:http://blog.csdn.net/da_keng/article/details/50589145纯属转载,复制过来方便编程时寻找。感谢作者:I-Awakening复制前补充:在刚学C#,用ManagementObjectSearcher竟然不能解析到头文件,需要手动AddReferance..前言:我们在很多情况下想要获得计算机的…

  • Java调用so文件[通俗易懂]

    Java调用so文件[通俗易懂]公司的硬件让我帮忙调用一个so文件,想着一直都没机会自己写一个jni,于是就答应了,在调用的过程中还踩了不少坑,特地写一篇博客记录一下。一、使用技术原本是想直接用java自带的jni,但是我们硬件只给了一个so文件,而且里面的函数命名等规则不符合java的jni调用标准,于是就打算使用框架jna来调用。JNA就是建立在JNI之上,它简化了Java调用原生函数的过程。JNA提供了一…

  • c++ set集合的使用方法详解

    c++ set集合的使用方法详解set集合是c++stl库中自带的一个容器,set具有以下两个特点:1、set中的元素都是排好序的2、set集合中没有重复的元素常用操作:begin()  返回set容器的第一个元素的地址end()    返回set容器的最后一个元素地址clear()  删除set容器中的所有的元素empty()   判断set容器是否为空max_size()

  • 41.XDMA寄存器详解5-H2C SGDMA/C2H SGDMA寄存器组剖析

    41.XDMA寄存器详解5-H2C SGDMA/C2H SGDMA寄存器组剖析目录1.上节回顾2.H2CSGDMA寄存器组2.1H2CSGDMA标识寄存器2.2H2CSGDMA描述符基地址寄存器2.3H2CSGDMA邻接描述符数量寄存器2.4H2CSGDMA描述符信用寄存器3.C2HSGDMA寄存器组4.下节内容1.上节回顾上节我们讲述了ConfigBlock寄存器组,我们今天来看H2CSGDMA/C2HSGDMA寄存器组,如下。H2CSGDMA/C2HSGDMA寄存器组主要是用来描述每个通道DMA描述符相关的一些

    2022年10月30日
  • 计算机考研复试C语言常见面试题「建议收藏」

    计算机考研复试C语言常见面试题「建议收藏」本文是我2021年考研时准备的复试面试题,现在拿出来给大家分享一下觉得好的点个赞哦,毕竟当初我也是整理了好久,改了好几次版本呢祝大家都上岸!!!!P.S.我当初整理的时候是word,直接复制过来的话代码不会自动变成CSDN的代码块,所以代码我是一段一段重新标记为CSDN代码段的,这样大家看起来舒服点C语言基础目录1、static关键字的作用22、C++和C的区别23、Java的方法重载24、重写和重载25、面向对象编程36、c++可以有多个父类37

  • 八个Android项目源码

    八个Android项目源码给大家分享几个Android开发项目源码,大部分功能相信可以在实战项目中直接使用,供大家下载学习,大部分项目是基于AndroidStudio开发,IDE为Eclipse的童鞋可通过网上教程自行转换,这里就不多说了。有句话说,不贴墙纸的装修都是耍流氓,无源码无效果图的文章也算是耍流氓,尴尬,那就直接上图吧。最近在整理GitHub,打算把一些以前做过的项目中部分功能和使用的技术点资料上传,回头也和大家分享。OK,要去忙了,再不去忙项目,测试版出不来就危险了,希望有一天不用敲代码也可以吃到馒头,吼吼~~

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号