本文将主要介绍Bernstein-Vazirani算法的基本概念、Bernstein-Vazirani问题以及该问提的经典与量子解决方式。本文对Bernstein-Vazirani算法的实现将主要使用启科量子的配套产品量子编程框架QuTrunk、可视化量子编程软件QuBranch以及启科量子自研的量子后端设备QuBox。
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的概率下给出正确判断。
假设一个函数f(x)满足₀₁₂,以x作为输入,并返回结果0或1。现在给定一个输入x,函数,其中,最终预计会找到s。因此,Bernstein-Vazirani算法目标为求解s。
采用经典方式求解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)。
关于Bernstein-Vazirani问题的经典算法中Oracle构造可以表示如下图:
而经典算法中Oracle构造可以表示为如下图:
构造步骤:
整个Bernstein-Vazirani算法过程可表示为:
from qutrunk.circuit import QCircuit
from qutrunk.circuit.gates import CNOT, X
以上调用qutrunk.circuit
实现量子线路功能,qutrunk.circuit.gates
实现量子逻辑门使用。
num_qubits = 9
secret_num = 2 ** 4 + 1
circuit = QCircuit(resource=True)
qureg = circuit.allocate(num_qubits)
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)
print(f"solution reached with probability {success_prob}")
circuit.print()
circuit.run()
circuit.show_resource()
输出统计信息如下,包括了所用量子比特数、量子逻辑门、算法运行时间、后端设备运行时间等,具体如下:
*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.
— 完 —
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有