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

实践|Bernstein-Vazirani算法及实践

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

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

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
运行
复制
    from qutrunk.circuit import QCircuit
    from qutrunk.circuit.gates import CNOT, X

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

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

    qureg = circuit.allocate(num_qubits)
  • 步骤三:按QuTrunk的量子汇编语言输入量子线路
代码语言:javascript
代码运行次数:0
运行
复制
    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
运行
复制
    print(f"solution reached with probability {success_prob}")
    circuit.print()

    circuit.run()
    circuit.show_resource()

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

代码语言:javascript
代码运行次数:0
运行
复制
 *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 删除。

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

评论
登录后参与评论
暂无评论
推荐阅读
再来利用java学学javaweb——–html+css+ JavaScript[通俗易懂]
​ * 表单项标签: * input:可以通过type属性值,改变元素展示的样式 * type属性: * text:文本输入框,默认值 * placeholder:指定输入框的提示信息,当输入框的内容发生变化,会自动清空提示信息 * password:密码输入框 * radio:单选框 * 注意: 1. 要想让多个单选框实现单选的效果,则多个单选框的name属性值必须一样。 2. 一般会给每一个单选框提供value属性,指定其被选中后提交的值 3. checked属性,可以指定默认值 * checkbox:复选框 * 注意: 1. 一般会给每一个单选框提供value属性,指定其被选中后提交的值 2. checked属性,可以指定默认值
全栈程序员站长
2022/09/14
2.3K0
javaWeb技术第二篇之CSS、事件和案例
<!--内联式 CSS (层叠样式表) 编辑 层叠样式表(英文全称:Cascading Style Sheets) CSS不仅可以静态地修饰网页,还可以配合各种脚本语言动态地对网页各元素进行格式化。 就是网页的美化技术。 入门:如何在html里面使用css html里面的外观命名跟css外观命名会有所有不同。但效果一致 css属性: 属性1:值1;属性2:值2;属性3:值3;... 内联式:对每个元素都进行style进行样式添加. 内部式:在当前html的head的style标签里面添加 <head> <
海仔
2019/08/15
1.2K0
JavaScript详细解析
我们之前的操作都是基于原生 JavaScript 的,比较繁琐。 JQuery 是一个前端框架技术,针对 JavaScript 进行了一系列的封装,使得操作变得非常简单! 期待吧……
全栈程序员站长
2022/09/09
1.6K0
HTML5+CSS3+JavaScript从入门到精通-20
HTML5+CSS3+JavaScript从入门到精通 作者:王征,李晓波 第二十章 JavaScript的DOM编程 案例 20-01 HTML文档的节点属性 <!DOCTYPE html> <!--web20-01--> <!-- 文档对象模型(DOM)是指W3C定义的标准的文档对象模型。 利用DOM中的对象,开发人员可对文档(如HTML)进行读取、搜索、修改、添加和删除等操作. DOM将整个文档展现为内存中的一棵树,每个元素、属性都是树上的一个节点。 --> <ht
qiqi_fu
2021/12/06
6730
HTML5+CSS3+JavaScript从入门到精通-20
用JavaScript制作页面特效
setTimeout和setInterval两者区别:setTimeout是定时程序,在什么时间做什么事情,setInterval是表示间隔一定时间反复执行某操作。
全栈程序员站长
2022/09/06
1.9K0
用JavaScript制作页面特效
HTML5+CSS3+JavaScript从入门到精通-18
HTML5+CSS3+JavaScript从入门到精通 作者:王征,李晓波 第十八章 JavaScript的网页特效 案例 18-01 文字的跑马灯效果 <!DOCTYPE html> <!--web18-01--> <!--跑马灯这段逻辑要好好看一下,包括position++和substring那里--> <html> <head> <meta charset="utf-8" /> <title>文字的跑马灯效果</title> <script type="text/javas
qiqi_fu
2021/12/06
2K0
HTML5+CSS3+JavaScript从入门到精通-18
第85节:Java中的JavaScript
后代选择器: 选择器1 选择器2 子元素选择器:选择器1 > 选择器2 选择器分组: 选择器1,选择器2,选择器3{} 属性选择器:选择器[属性名称='属性值']
达达前端
2019/07/03
2.7K0
第85节:Java中的JavaScript
【java web 01】3小时快速学习前端知识(收藏备用)
编辑好demo,选择右下角的Go live会自动跑一个小型服务器,就可以很方便的看你的html解析效果喽。
半旧518
2024/07/09
3360
【java web 01】3小时快速学习前端知识(收藏备用)
JavaWeb——JavaScript精讲之DOM、BOM对象与案例实战(动态添加删除表格)
上一博文种讲解了JavaScript基础的ECMAScript,包括基本语法和部分对象,本文中继续讲解JavaScript中比较重要的两部分内容BOM、DOM及事件,后文中有对应的实战练习。
Winter_world
2020/09/25
2.3K0
JavaWeb——JavaScript精讲之DOM、BOM对象与案例实战(动态添加删除表格)
HTML5+CSS3+JavaScript从入门到精通-17
HTML5+CSS3+JavaScript从入门到精通 17-01 用户登录界面! <!--web17-01--> <!-- 与第四章的表单呼应 --> <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>用户登录界面!</title> <script type="text/javascript"> function alert_info() { //win
qiqi_fu
2021/12/06
1.4K0
HTML5+CSS3+JavaScript从入门到精通-17
JavaScript基本入门教程
                必须以字母或下划线开头,中间可以是数字、字符或下划线
itlemon
2020/04/03
4.1K0
JavaScript 前端笔记总结(精简)
JavaScript 一种直译式脚本语言,是一种动态类型、弱类型、基于原型的语言,内置支持类型,属于网络的脚本语言,现在已经被广泛用于Web应用开发,常用来为网页添加各式各样的动态功能,为用户提供更流畅美观的浏览效果,现在随着node.js引擎的出现,使得JavaScript逐步成为了一种全栈开发语言了.
王瑞MVP
2022/12/28
7.7K0
Web前端开发JQuery框架笔记
ID选择器: 通过使用简单的$(#id)标识前缀,实现快速匹配指定ID的元素对象,具体用法如下.
王瑞MVP
2022/12/28
12K0
我们一起学JavaScript之面向对象
​ 在 Java 中我们学习过面向对象,核心思想是万物皆对象。在 JavaScript 中同样也有面向对象。思想类似。
楠羽
2022/11/18
3700
我们一起学JavaScript之面向对象
03 . 前端之JavaScipt
语法: splice(index,howmany,item1,.....,itemX)
iginkgo18
2020/09/27
1.5K0
03 . 前端之JavaScipt
WEB入门之十三 jQuery选择器
上一章我初步接触了jQuery,并能够编写一些简单的jQuery代码,其中重点是jQuery基本选择器。jQuery的选择器非常强大,它是jQuery的根基,基本上任何操作都要依赖于选择器。本章重点学习jQuery选择器,包括层次选择器、属性选择器、表单选择器、内容选择器和过滤选择器等。
张哥编程
2024/12/17
2450
WEB入门之十三  jQuery选择器
Web前端三剑客学习笔记
一直没有系统的学习HTML,CSS,JS都是东学一点,西学一点,想着暑假得空,便系统的学习下吧,故于此记录之。
小简
2022/12/29
2.3K0
Web前端三剑客学习笔记
jQuery开发补充笔记
[TOC] 0x00 前言简介 什么JQuery? jQuery是一个快速、简洁的JavaScript框架,是继Prototype之后又一个优秀的JavaScript代码库(或JavaScript框架
全栈工程师修炼指南
2022/09/29
1.6K0
jQuery开发补充笔记
jQuery开发补充笔记
[TOC] 0x00 前言简介 什么JQuery? jQuery是一个快速、简洁的JavaScript框架,是继Prototype之后又一个优秀的JavaScript代码库(或JavaScript框架
全栈工程师修炼指南
2020/10/23
4.7K0
jQuery开发补充笔记
Python爬虫基础:常用HTML标签和Javascript入门
大部分HTML标签是闭合的,由开始标签和结束标签构成,二者之间是要显示的内容,例如:<title>网页标题</title>。也有的HTML标签是没有结束标签的,例如:<br />和<hr>。
Python小屋屋主
2018/09/20
1.8K0
相关推荐
再来利用java学学javaweb——–html+css+ JavaScript[通俗易懂]
更多 >
目录
  • 点击上方↑↑↑“量子发烧友”关注我
  • Bernstein-Vazirani算法及实践
    • 1.Bernstein-Vazirani算法
    • 2.Bernstein-Vazirani问题
      • 2.1经典方式求解
      • 2.2量子方式求解
    • 3.Bernstein-Vazirani算法的实现
      • 3.1Bernstein-Vazirani算法——以QuTrunk为例
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档