Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >实践|Bernstein-Vazirani算法及实践

实践|Bernstein-Vazirani算法及实践

作者头像
量子发烧友
发布于 2023-03-08 02:35:35
发布于 2023-03-08 02:35:35
68100
代码可运行
举报
文章被收录于专栏:量子发烧友量子发烧友
运行总次数:0
代码可运行

点击上方↑↑↑“量子发烧友”关注我

Bernstein-Vazirani算法及实践

本文将主要介绍Bernstein-Vazirani算法的基本概念、Bernstein-Vazirani问题以及该问提的经典与量子解决方式。本文对Bernstein-Vazirani算法的实现将主要使用启科量子的配套产品量子编程框架QuTrunk、可视化量子编程软件QuBranch以及启科量子自研的量子后端设备QuBox。

1.Bernstein-Vazirani算法

Bernstein-Vazirani算法是由Ethan Bernstein和Umesh Vazirani于1992年提出的一个算法。该算法主要用于求解编码函数,是一个条件限制版的Deutsch-Jozsa算法。也就是说Bernstein-Vazirani的工作建立在Deutsch和Jozsa早期工作理论上来探索量子查询复杂度。他们对该领域的贡献主要为编写出一个用于隐藏字符串问题的量子算法。已经有人证明了Bernstein-Vazirani算法时间复杂度在BQP和BPP之间,该算法的非递归量子查询复杂度仅为11。这一量子算法的最核心价值在于加快了查询速度, 而不是执行时间本身。

那么何为BQP复杂度和BPP复杂度?在计算复杂性理论中,BQP(bounded-error quantum polynomial time)是量子计算机在多项式时间内可以解决的一类决策问题,所有实例的错误概率最多为1/3。BPP这个每个字母分别代表"Bounded-error"(有限错误),"Probabilistic"(机率的),"Polynomial time"(多项式时间)。BPP是在多项式时间内以概率图灵机解出问题的集合, 并且对所有的输入、输出结果出错的概率在1/3之内。当一个问题属于BPP问题集合时,则存在一个多项式时间内的算法允许随机决定,且对于该算法的任何输入都必须在错误率为1/3的概率下给出正确判断。

2.Bernstein-Vazirani问题

假设一个函数f(x)满足₀₁₂,以x作为输入,并返回结果0或1。现在给定一个输入x,函数,其中,最终预计会找到s。因此,Bernstein-Vazirani算法目标为求解s。

2.1经典方式求解

采用经典方式求解Bernstein-Vazirani问题,所列表达式为。给定一个输入x,隐藏位串 s 可以按输入序列使用算子oracle查找。如输入x为100…0,010…0,001…0,000…1,经典算法求解方式只能查询生成1位信息,任意隐藏字符串s具有n位信息,所以经典查询的复杂度为O(n)。

示例:当n=2时的Bernstein-Vazirani问题。经典设元素为两位,s向量表示为,所代表函数为4种类(00,01,10,11)。此时的Bernstein-Vazirani问题为,S可对应01、10两种取值,复杂度O(2)。

2.2量子方式求解

关于Bernstein-Vazirani问题的经典算法中Oracle构造可以表示如下图:

而经典算法中Oracle构造可以表示为如下图:

构造步骤:

  • 首先初始化输入的量子比特,得到输出量子比特;
  • 对每个量子比特进行H门操作;
  • 应用设计出的量子Oracle算子 找到搜索目标;
  • 经过量子Oracle门操作后,再次进行H门操作得到态。根据。对于任意量子比特得到经过以上步骤量子门操作后的输出态表达式为。

整个Bernstein-Vazirani算法过程可表示为:

3.Bernstein-Vazirani算法的实现

3.1Bernstein-Vazirani算法——以QuTrunk为例

  • 步骤一:QuTrunk环境准备
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
    from qutrunk.circuit import QCircuit
    from qutrunk.circuit.gates import CNOT, X

以上调用qutrunk.circuit实现量子线路功能,qutrunk.circuit.gates实现量子逻辑门使用。

  • 步骤二:设置量子比特数、量子线路后端、量子寄存器等
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
    num_qubits = 9
    secret_num = 2 ** 4 + 1
    circuit = QCircuit(resource=True)

    qureg = circuit.allocate(num_qubits)
  • 步骤三:按QuTrunk的量子汇编语言输入量子线路
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
    X * qureg[0]

    bits = secret_num
    bit = 0
    for qb in range(1, num_qubits):
        bit = int(bits % 2)
        bits = int(bits / 2)
        if bit:
            CNOT * (qureg[0], qureg[qb])

    success_prob = 1.0
    bits = secret_num
    for qb in range(1, num_qubits):
        bit = int(bits % 2)
        bits = int(bits / 2)
        success_prob *= circuit.get_prob_outcome(qb, bit)
  • 步骤四:运行Bernstein-Vazirani算法并打印结果
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
    print(f"solution reached with probability {success_prob}")
    circuit.print()

    circuit.run()
    circuit.show_resource()

输出统计信息如下,包括了所用量子比特数、量子逻辑门、算法运行时间、后端设备运行时间等,具体如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 *solution reached with probability 1.0  
qreg q[9]  
creg c[9]  
X * q[0]  
MCX(1) * (q[0], q[1])  
MCX(1) * (q[0], q[5])  
==================Counter==================  
Counter(quit=9)  
qubits = 9  
quantum_gates = 3  
total_time = 0.0024347305297851562  
qutrunk_time = 0.0009989738464355469  
backend_time = 0.0014357566833496094*

参考资料:

[1]https://qiskit.org/textbook/ch-algorithms/bernstein-vazirani.html#3a.-Experiment-with-Simulators--

[2]https://baike.baidu.com/item/BQP/22700880?fr=aladdin

[3]Ethan Bernstein and Umesh Vazirani (1997) "Quantum Complexity Theory" SIAM Journal on Computing, Vol. 26, No. 5: 1411-1473, doi:10.1137/S0097539796300921.

— 完 —

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-12-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 量子发烧友 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
QuTrunk使用教程之Bell Pair电路及Deutsch算法
QuTrunk是启科量子自主研发的量子编程框架。QuTrunk基于Python提供了量子编程API,对量子编程相关的基本概念做了代码层面的抽象封装和实现,如Qubit代表单个量子比特,每个量子比特默认持有一个经典比特,方便存放量子比特对测量结果。
量子发烧友
2023/02/24
3620
QuTrunk使用教程之Bell Pair电路及Deutsch算法
下(应用篇)| 推荐几款较流行的量子算法
量子算法是量子计算机的必要软件支撑,同时量子算法的研究也是推动量子计算发展的强大动力。以下将对各个发展阶段的典型量子算法进行比较分析。
量子发烧友
2023/02/24
2.1K0
下(应用篇)| 推荐几款较流行的量子算法
量子线性系统算法及实践——以Cirq为例
求解线性方程组是科学计算中的一个基础问题,也可利用线性方程组构造复杂的算法,如数值计算中的插值与拟合、大数据中的线性回归、主成分分析等。而正是由于线性求解问题在学科中的基础性作用,其在科学、工程、金融、经济应用、计算机科学等领域也应用广泛,如常见的天气预报,需要通过建立并求解包含百万变量的线性方程组实现对大气中类似温度、气压、湿度等的模拟和预测;如销量预测,需要采用线性回归方式的时序预测方法进行预测。
量子发烧友
2023/03/08
1.1K0
量子线性系统算法及实践——以Cirq为例
启科量子自主研发量子计算模拟后端 QuSprout 并正式开源
QuSprout 的开源旨在让更多的开发者、专家学者或爱好者参与到量子技术的研发上来,更快推动量子技术发展(开源地址见文末)。
量子发烧友
2023/02/24
2210
启科量子自主研发量子计算模拟后端 QuSprout 并正式开源
QuTrunk+Runtime+QuSaaS+AWS量子计算编程实战
QuTrunk 是启科量子自主研发的一款免费、开源、跨平台的量子计算编程框架,包括量子编程API、量子命令转译、量子计算后端接口等。它提供多种量子计算体验,提供本地量子计算Python计算后端,提供OMP多线程、MPI多节点并行、GPU加速等计算模式。
量子发烧友
2023/03/08
9030
QuTrunk+Runtime+QuSaaS+AWS量子计算编程实战
实践|量子编程初试
导读 QuBranch与QuTrunk项目是启科量子发起的量子编程软件工具开发项目。QuBranch是以VS Code庞大的生态群为基础,专为量子编程开发的一种编程工具,支持Windows、Mac、Linux等操作系统和编辑、调试、量子模拟执行等功能,可为量子编程提供集成开发环境。QuTrunk是启科量子自主研发的量子编程框架,基于python提供量子编程API,对量子编程涉及到的基本概念做了代码层面的抽象封装和实现,主要为量子编程提供底层服务。为加速量子软件开发与实践进程,本文将简要介绍QuBranch与QuTrunk,并通过软件已开发功能进行量子算法运行演示。
量子发烧友
2023/02/24
6550
实践|量子编程初试
通用量子算法:量子相位估计算法
量子相位估计算法(quantum phase estimation,QPE)也称作量子特征值估计算法,是很多量子算法的基本步骤,其中包括Shor`s算法(秀尔算法)和HHL算法(线性方程组的量子算法)。它的作用就是快速的估计一个酉变换的特征值。由于酉矩阵拥有一个性质:酉矩阵的特征值都是模为1的复数。所以对酉矩阵而言,其特征值和相位基本是对等的。
量子发烧友
2023/02/24
1.3K0
通用量子算法:量子相位估计算法
Qutrunk与Paddle结合实践--VQA算法示例
QuTrunk 是启科量子开发和已经开源的一款量子编程框架软件产品,它使用 Python 作为宿主语言,利用Python 的语法特性实现针对量子程序的 DSL(领域专用语言),所有支持 Python 编程的 IDE 均可安装使用 QuTrunk。QuTrunk 基于量子逻辑门、量子线路等概念提供量子编程所需的各类API。这些 API 分别由相应的模块实现,比如 QCircuit 实现量子线路功能,Qubit 实现量子比特,Qureg 实现量子寄存器,Command 对应每个量子门操作的指令, Backend 代表运行量子线路的后端模块,gate 模块实现了各类基础量子门操作。同时 QuTrunk 还可以作为其他上层量子计算应用的基础,比如:量子算法、量子可视化编程、量子机器学习等。
量子发烧友
2023/02/24
5070
Qutrunk与Paddle结合实践--VQA算法示例
实践|QuTrunk实践之基础量子逻辑门
经典计算中,最基本的单元是比特,在经典计算中对比特的操作采用电信号的处理方式,不同的逻辑门对应相应的电信号处理方式,实现对比特的基本操作。我们可以通过不同的逻辑门组合来达到控制电路的目的。类似于经典计算,量子计算中对量子比特的操作需要操纵使用量子逻辑门使量子态发生演化,通过不同的量子逻辑门组合最终实现量子线路的控制。使用量子逻辑门,我们有意识的使量子态发生演化。
量子发烧友
2023/03/08
6440
实践|QuTrunk实践之基础量子逻辑门
前沿 | 经典计算的天花板:科学家找到只有量子计算才能解决的问题
Oracle Separation of BQP and PH:https://eccc.weizmann.ac.il/report/2018/107/
机器之心
2018/07/26
6270
前沿 | 经典计算的天花板:科学家找到只有量子计算才能解决的问题
量子算法与实践——Grover算法
量子计算机的算力可体现为量子计算机可实现并行计算, Grover算法(Quantum Search Algorithm)是量子计算领域的主要算法之一。Grover算法是由Grover于1996年提出的平方根加速的随机数据库量子搜索算法,旨在利用量子计算机进行比经典计算机更快的数据搜索。在数据库足够混乱且没有具体的数据结构限定的条件下,Grover算法可以快速解决从N个未分类的客体中寻找出某个特定个体的问题。除搜索时间远短于经典计算外,其强大之处还在于Grover算法的公式可适用于很多问题,比如:密码学、矩阵和图形问题、优化以及量子机器学习等。本文将从Grover算法的实现原理、应用与实践等方面介绍Grover算法。
薛大叔的量子猫
2022/11/07
4.8K0
QuTrunk与MindSpore量子神经网络初探
QuTrunk 是启科量子开发和已经开源的一款量子编程框架软件产品,关于QuTrunk的详细介绍,用户可以访问启科的开发者社区站点详细了解,也可以进入github上此项目下进行查询。
量子发烧友
2023/03/08
7750
QuTrunk与MindSpore量子神经网络初探
谷歌实现量子霸权论文曝光,圈内人士:量子计算的里程碑事件
9 月 20 日,据《财富》、《金融时报》等多家外媒报道,谷歌已经利用一台 53 量子比特的量子计算机实现了传统架构计算机无法完成的任务,即在世界第一超算需要计算 1 万年的实验中,谷歌的量子计算机只用了 3 分 20 秒。
机器之心
2019/09/24
5290
谷歌实现量子霸权论文曝光,圈内人士:量子计算的里程碑事件
量子算法与实践--变分量子态对角化算法
变分混合量子—经典算法是近期在量子计算机上有希望实现的一种候选算法。在这些算法中,量子计算机评估一个门序列所耗费的成本与经典的成本评估相比较低,速度上也会更快一些。通过量子计算机评估的门序列信息,最终也可用于经典计算机调整门序列的参数。
量子发烧友
2023/02/24
7450
量子算法与实践--变分量子态对角化算法
混合量子-经典体系对量子数据的分类问题
经典计算机中可以利用比特位和逻辑门进行二进制运算,在物理硬件方面,二进制运算主要通过半导体的特殊电性质实现。在量子计算机中,主要利用量子的纠缠和叠加特性通过量子比特位和量子逻辑门来实现运算。量子计算对算力的加速优势也在量子计算机不断发展中得到证实。但关于量子计算机与经典计算机的存在性问题,并非取而代之这么简单。目前,在物理硬件设备基础和量子技术的发展方面,依然无法制造出可以超越经典计算的通用量子计算机。
量子发烧友
2023/03/08
4550
混合量子-经典体系对量子数据的分类问题
量子计算 + AI:科幻照进现实?
说到量子计算,很多人第一反应可能是:“这玩意儿离我们还远着呢吧?” 确实,量子计算现在还处于早期发展阶段,但如果你是个AI开发者,或者对计算加速有需求,那你真的应该关注它。量子计算可能成为未来AI训练和推理的“加速器”,帮助我们在海量数据中找到最优解。
Echo_Wish
2025/03/22
1100
量子计算 + AI:科幻照进现实?
量子机器学习新思路——构建参数化的量子线路
人工智能的发展已经历60余年,自1956年至今人工智能发展共经历了三个发展阶段。在技术阶段上,AI发展的技术阶段可分为运算智能阶段、感知智能阶段和认知智能阶段三个层次。当前,人工智能的发展正处于第三次发展浪潮之中,处于认知智能时代的初级阶段。
量子发烧友
2023/03/08
6240
量子机器学习新思路——构建参数化的量子线路
学界 | 南科大翁文康:「量子霸权」的基础概念和可行方案
论文:Quantum supremacy: some fundamental concepts
机器之心
2018/07/30
8700
学界 | 南科大翁文康:「量子霸权」的基础概念和可行方案
量子计算对 bitcoin 的威胁
在两周前的 BBL 上,我给团队介绍了 bitcoin,相关的 slides 见: github.com/tyrchen/unchained 其中花了点时间谈论了 quantum computing
tyrchen
2018/03/28
1.1K0
量子计算对 bitcoin 的威胁
使用启科QuPot+Runtime+QuSaaS进行量子应用开发及部署-调用AWS Braket计算后端
使用启科QuTrunk开发的量子应用可以通过QuSaaS 部署到启科QuPot云环境中对用户提供服务。本文将介绍如何使用QuTrunk进行AWS云上应用程序的开发和如何通过QuSaaS将量子应用部署到QuPot平台,并且QuTrunk计算后端调用AWS Braket服务。具体展示之前,先和大家简要介绍下启科的量子计算相关软件:QuPot和QuSaaS和Runtime。
量子发烧友
2023/03/08
6250
使用启科QuPot+Runtime+QuSaaS进行量子应用开发及部署-调用AWS Braket计算后端
推荐阅读
相关推荐
QuTrunk使用教程之Bell Pair电路及Deutsch算法
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验