Qiskit汉化3.3-Bernstein-Vazirani Algorithm

Dora Dōjo
1

Bernstein-Vazirani算法

在本节中，我们首先介绍Bernstein-Vazirani问题，它的经典解决方案，以及解决它的量子算法。然后我们使用Qiskit实现量子算法，并在模拟器和设备上运行它。

[toc]

1. Bernstein-Vazirani算法

在[1]中首次引入的Bernstein-Vazirani算法可以看作是上一节中介绍的Deutsch-Jozsa算法的扩展。它表明，使用量子计算机作为计算工具来解决比Deutsch-Jozsa问题更复杂的问题可能具有优势。

1.1 Bernstein-Vazirani问题

我们再次得到一个黑盒函数 f ，它接受一个比特串( x )作为输入，并返回 0 或 1 ，即:

f(\{x_0,x_1,x_2,...\}) \rightarrow 0 \textrm{ or } 1 \textrm{ where } x_n \textrm{ is }0 \textrm{ or } 1

不同于Deutsch-Jozsa问题中的平衡或常量函数，现在该函数保证返回输入与某个字符串的按位乘积， s 。换句话说，给定输入 x ， f(x) = s \cdot x \ \text{(mod 2)} 。我们期望找到 s 。作为一个经典的可逆电路，Bernstein-Vazirani oracle看起来像这样:

1

1.2 经典解决方案

经典方案，oracle会返回:

f_s(x) = s \cdot x \mod 2

给定输入 x 。因此，可以通过输入序列查询oracle来发现隐藏的位字符串 s :

Input(x)
100…0
010…0
001…0
000…1

其中每个查询显示 s 的不同位(位 s_i )。例如，使用x = 1000…0可以获得 s 的最低有效位，` x = 0100…我们可以找到下一个最低有效位，以此类推。这意味着我们需要调用函数 f_s(x)，n 次。

1.3 量子解决方案

使用量子计算机，我们只需调用函数 f(x) 一次，就可以100%地解决这个问题。寻找隐藏比特串的量子Bernstein-Vazirani算法非常简单:

  1. 将输入量子位初始化为 |0\rangle^{\otimes n} 状态，输出量子位为 |{-}\rangle
  2. 对输入寄存器应用哈达玛门
  3. 查询oracle
  4. 对输入寄存器应用哈达玛门
  5. 测量

2

为了解释算法，让我们更仔细地看看当我们对每个量子比特应用H门时会发生什么。如果我们有一个 n -量子比特状态。 |a\rangle ，并应用H门，我们将看到转换:

|a\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} (-1)^{a\cdot x}|x\rangle.
解释等式（点击此处扩展）

我们记得哈达玛对一个量子比特执行以下转换:

H|0\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \\\\ H|1\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle)

使用求和表示法，我们可以这样重写:

H|a\rangle = \frac{1}{\sqrt{2}}\sum_{x\in \{0,1\}} (-1)^{a\cdot x}|x\rangle.

对于两个量子比特，对每个量子比特应用哈达玛变换如下:

H^{\otimes 2}|00\rangle = \tfrac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle) \\\\ H^{\otimes 2}|01\rangle = \tfrac{1}{2}(|00\rangle - |01\rangle + |10\rangle - |11\rangle)\\\\ H^{\otimes 2}|10\rangle = \tfrac{1}{2}(|00\rangle + |01\rangle - |10\rangle - |11\rangle)\\\\ H^{\otimes 2}|11\rangle = \tfrac{1}{2}(|00\rangle - |01\rangle - |10\rangle + |11\rangle)

我们可以用下面的求和来表示:

H^{\otimes 2}|a\rangle = \frac{1}{2}\sum_{x\in \{0,1\}^2} (-1)^{a\cdot x}|x\rangle

希望你现在看到我们是如何得到上面的方程的。

特别是，当我们从量子寄存器开始 |00\dots 0\rangle ,对其应用 n 哈达玛门，我们就有了熟悉的量子叠加:

|00\dots 0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} |x\rangle

在这种情况下，相位项 (-1)^{a\cdot x} 消失了，因为 a=0 ，因此 (-1)^{a\cdot x} = 1

经典的oracle f_s 对于任何输入 x ( s \cdot x\mod 2 = 1 )返回 1 ，否则返回 0 。如果我们使用来自Deutsch-Jozsa算法的相同相位反冲技巧，并作用于状态 |{-}\rangle 的量子比特，我们得到以下转换:

|x \rangle \xrightarrow{f_s} (-1)^{s\cdot x} |x \rangle

通过对 |00\dots 0\rangle 进行哈达玛变换得到量子叠加态，然后对量子oracle f_s 进行查询，即可得到隐藏的比特串。也就是说,

|00\dots 0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} |x\rangle \xrightarrow{f_a} \frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} (-1)^{a\cdot x}|x\rangle

因为 n 哈达玛门的倒数仍然是 n 哈达玛门，我们可以用

\frac{1}{\sqrt{2^n}} \sum_{x\in \{0,1\}^n} (-1)^{a\cdot x}|x\rangle \xrightarrow{H^{\otimes n}} |a\rangle

2.样例

让我们来看一个具体的例子， n=2 量子比特和一个秘密字符串 s=11 。请注意，我们遵循参考[2]中的公式，该公式仅使用一个寄存器为Bernstein-Vazirani量子oracle生成电路。

  1. 两个量子比特的寄存器初始化为零:
\lvert \psi_0 \rangle = \lvert 0 0 \rangle
  1. 对两个量子比特应用哈达玛门：
\lvert \psi_1 \rangle = \frac{1}{2} \left( \lvert 0 0 \rangle + \lvert 0 1 \rangle + \lvert 1 0 \rangle + \lvert 1 1 \rangle \right)
  1. 对于字符串 s=11 ，量子oracle执行以下操作:
|x \rangle \xrightarrow{f_s} (-1)^{x\cdot 11} |x \rangle.\\\\ \lvert \psi_2 \rangle = \frac{1}{2} \left( (-1)^{00\cdot 11}|00\rangle + (-1)^{01\cdot 11}|01\rangle + (-1)^{10\cdot 11}|10\rangle + (-1)^{11\cdot 11}|11\rangle \right)\\\\ \lvert \psi_2 \rangle = \frac{1}{2} \left( \lvert 0 0 \rangle - \lvert 0 1 \rangle - \lvert 1 0 \rangle + \lvert 1 1 \rangle \right)
  1. 对两个量子比特应用哈达玛门：
\lvert \psi_3 \rangle = \lvert 1 1 \rangle
  1. 测量以找到秘密字符串 s=11

使用下面的widget bv_widget。按下按钮应用不同的步骤，并尝试遵循算法。你可以通过前两个位置参数改变输入量子比特的数量和秘密字符串的值。

from qiskit_textbook.widgets import bv_widget
bv_widget(2, "11")

3.Qiskit实现

现在，我们来看一下Bernstein-Vazirani算法在Qiskit中的实现，其中 s=011 为3位函数。

# initialization
import matplotlib.pyplot as plt
import numpy as np

# importing Qiskit
from qiskit import IBMQ, Aer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, transpile, assemble

# import basic plot tools
from qiskit.visualization import plot_histogram

首先设置实验中使用的量子比特数，算法要发现的隐藏比特串 s ;隐藏的位串 s 决定了量子oracle的电路。

n = 3 # number of qubits used to represent s
s = '011'   # the hidden binary string

然后，我们使用Qiskit对Bernstein-Vazirani算法进行编程。

# We need a circuit with n qubits, plus one auxiliary qubit
# Also need n classical bits to write the output to
bv_circuit = QuantumCircuit(n+1, n)

# put auxiliary in state |->
bv_circuit.h(n)
bv_circuit.z(n)

# Apply Hadamard gates before querying the oracle
for i in range(n):
    bv_circuit.h(i)
    
# Apply barrier 
bv_circuit.barrier()

# Apply the inner-product oracle
s = s[::-1] # reverse s to fit qiskit's qubit ordering
for q in range(n):
    if s[q] == '0':
        bv_circuit.i(q)
    else:
        bv_circuit.cx(q, n)
        
# Apply barrier 
bv_circuit.barrier()

#Apply Hadamard gates after querying the oracle
for i in range(n):
    bv_circuit.h(i)

# Measurement
for i in range(n):
    bv_circuit.measure(i, i)

bv_circuit.draw()

3

3a.使用模拟器进行实验

我们可以在模拟器上运行上述电路。

# use local simulator
aer_sim = Aer.get_backend('aer_simulator')
shots = 1024
qobj = assemble(bv_circuit)
results = aer_sim.run(qobj).result()
answer = results.get_counts()

plot_histogram(answer)

4

我们可以看到测量的结果是隐藏的字符串011。

3b.使用真实设备进行实验

我们可以在真实的设备上运行电路，如下所示。

该单元使用量子硬件。要在浏览器中运行它，请点击这里进入IBM Quantum体验。

# Load our saved IBMQ accounts and get the least busy backend device with less than or equal to 5 qubits
IBMQ.load_account()
provider = IBMQ.get_provider(hub='ibm-q')
provider.backends()
backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits <= 5 and
                                   x.configuration().n_qubits >= 2 and
                                   not x.configuration().simulator and x.status().operational==True))
print("least busy backend: ", backend)

该单元使用量子硬件。要在浏览器中运行它，请点击这里进入IBM Quantum体验。

# Run our circuit on the least busy backend. Monitor the execution of the job in the queue
from qiskit.tools.monitor import job_monitor

shots = 1024
transpiled_bv_circuit = transpile(bv_circuit, backend)
job = backend.run(transpiled_bv_circuit, shots=shots)

job_monitor(job, interval=2)

该单元使用量子硬件。要在浏览器中运行它，请点击这里进入IBM Quantum体验。

# Get the results from the computation
results = job.result()
answer = results.get_counts()

plot_histogram(answer)

可以看到，大多数结果是011。其他结果是由于量子计算中的误差。

4.练习

  1. 使用下面的小部件来查看Bernstein-Vazirani算法在不同oracle上的运行情况:
from qiskit_textbook.widgets import bv_widget
bv_widget(3, "011", hide_oracle=False)
  1. 上面Bernstein-Vazirani的实现是为了一个秘密的位字符串 s=011 。修改秘密字符串 s=011 的实现。结果和你预期的一样吗?解释一下。
  2. 上面Bernstein-Vazirani的实现是为了一个秘密的位字符串 s=011 。修改秘密字符串 s = 11101101 的实现。结果和你预期的一样吗?解释一下。

5.参考文献

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

2.Jiangfeng Du, Mingjun Shi, Jihui Wu, Xianyi Zhou, Yangmei Fan, BangJiao Ye, Rongdian Han (2001) “Implementation of a quantum algorithm to solve the Bernstein-Vazirani parity problem without entanglement on an ensemble quantum computer”, Phys. Rev. A 64, 042306, 10.1103/PhysRevA.64.042306, arXiv:quant-ph/0012114.

import qiskit.tools.jupyter
%qiskit_version_table