Deutsch-Jozsa算法
在本节中，我们首先介绍Deutsch-Jozsa问题，以及求解该问题的经典算法和量子算法。然后我们使用Qiskit实现量子算法，并在模拟器和设备上运行它。
1.介绍
在参考文献[1]中首次引入的Deutsch-Jozsa算法是第一个性能优于最优经典算法的量子算法实例。它表明，使用量子计算机作为特定问题的计算工具可能有优势。
1.1 Deutsch-Jozsa问题
我们得到了一个隐藏的布尔函数 f ，它接受一个比特字符串作为输入，并返回 0 或 1 ，即:
给定布尔函数的性质是保证它要么是平衡的，要么是常数的。常数函数对于任何输入返回全 0 或全 1 ，而平衡函数对于所有输入的一半返回 0 ，另一半返回 1 。我们的任务是确定给定的函数是平衡的还是常数的。
注意，Deutsch-Jozsa问题是单个Deutsch问题的 n 比特扩展。
1.2 经典解决方法
通常，在最好的情况下，对oracle进行两次查询就可以确定隐藏的布尔函数 f(x) 是平衡的：如果我们同时得到 f(0,0,0，…)\rightarrow 0 和 f(1,0,0，…)\rightarrow 1 ，那么我们就知道函数是平衡的，因为我们得到了两个不同的输出。
在最坏的情况下，如果我们尝试的每个输入都看到相同的输出，我们将必须检查所有可能输入的正好一半加上1，以确定 f(x) 是常数。由于可能的输入总数是 2^n ，这意味着我们需要 2^{n-1} + 1 试验输入，以确保 f(x) 在最坏情况下是常数。例如，对于一个 4 位字符串，如果我们检查了 16 可能的组合中的 8 ，得到所有 0 ，仍然有可能 9^{th} 输入返回 1 ，并且 f(x) 是平衡的。从概率上讲，这是一个非常不可能的事件。事实上，如果我们连续地得到相同的结果，我们可以把一个 k 输入的函数是常数函数的概率表示为：
实际上，如果置信度超过x%，我们可以选择提前截断经典算法。但如果我们想要100%确定，就需要检查 2^{n-1}+1个 输入。
1.3量子解决方案
使用量子计算机，只要调用一次函数 f(x) ，我们就可以100%地解决这个问题，只要我们将函数 f 实现为量子oracle，它将状态 \vert x\rangle \vert y\rangle 映射到 \vert x\rangle \vert y\ oplus f(x)\rangle , 其中 \oplus 是对 2 求模的加法。下面是Deutsch-Jozsa算法的通用电路。
现在，让我们看一下算法的步骤:
1.准备两个量子寄存器。第一个是初始化为 |0⟩ 的 n -量子比特寄存器，第二个是初始化为 |1⟩ 的单量子比特寄存器:
2.对每个量子比特应用哈达玛门:
3.应用量子oracle \vert x\rangle \vert y\rangle 到 \vert x\rangle \vert y\ oplus f(x)\rangle:
因为对于每个 x,f(x) 要么是 0 ，要么是 1 。
4.此时，第二个单量子比特寄存器可以被忽略。对第一个寄存器中的每个量子比特应用哈达玛门:
其中 x \cdot y = x_0y_0 \oplus x_1y_1 \oplus \ldots \oplus x_{n-1}y_{n-1} 是按位积的和。
5.测量第一个寄存器。请注意，计算 \vert 0 \rangle ^{\otimes n} = \lvert \frac{1}{2^n}\sum_{x=0}^{2^n-1}(-1)^{f(x)} \rvert^2 的概率，如果 f(x) 是常数，则计算为 1 ;如果 f(x) 是平衡的，则计算为 0 。
1.4 为什么会这样呢?
- 常数Oracle
当oracle是常量时，它对输入的量子比特没有影响(直到一个全局相位)，并且查询oracle前后的量子态是相同的。由于H门是它自己的逆，在步骤4中，我们反转步骤2以在第一个寄存器中获得 |00\dots 0\rangle 的初始量子态。
- 平衡Oracle
在第2步之后，我们的输入寄存器是所有状态在计算基础上的平等叠加。当oracle是平衡的时候，相位反冲正好给这些状态的一半增加了一个负相位：
查询oracle后的量子态与查询oracle前的量子态正交。因此，在步骤4中，当应用H门时，我们必须最终得到一个与 |00\dots 0\rangle 正交的量子态。这意味着我们永远不应该测量全零状态。
2. 举例
让我们看一个2比特平衡函数的具体例子:
考虑一个2比特函数 f(x_0,x_1)=x_0 \oplus x_1 ，使得
对应的两比特位的相位oracle是
我们现在将通过一个示例状态来检查此oracle是否按预期工作
- 两个量子比特的第一个寄存器初始化为 |00⟩ ，第二个寄存器量子比特初始化为 |1⟩ (注意，我们使用下标0、1和2来索引量子比特。下标“01”表示包含量子比特0和1的寄存器的状态)
- 对所有量子比特应用哈达玛
- oracle函数可以实现为 \text{Q}_f = CX_{02}CX_{12}
- 简化后，我们得到以下结果:
- 在第一个寄存器上应用哈达玛
- 测量前两个量子比特将得到非零值 11 ，表明函数是平衡的。
你可以使用下面的小部件尝试类似的例子。按下按钮添加H门和oracle，重新运行单元格和/或设置case="constant"以尝试不同的oracle。
from qiskit_textbook.widgets import dj_widget
dj_widget(size="small", case="balanced")
3.创造量子Oracles
让我们看看创建量子Oracle的不同方法。
常量函数很简单:
-
如果f(x) = 0，则将 I 门应用于寄存器2中的量子比特。
-
如果f(x) = 1，则将 X 门应用于寄存器2中的量子比特。
对于平衡函数，我们可以创建许多不同的电路。我们保证电路平衡的方法之一是对寄存器1中的每个量子比特执行CNOT，以寄存器2中的量子比特为目标。例如:
在上图中，前三个量子比特构成输入寄存器，底部量子比特是输出寄存器。在下面的表中，我们可以看到哪些输入状态给出了哪些输出:
| Input states that output 0 | Input States that output 1 |
|---|---|
| 000 | 001 |
| 011 | 100 |
| 101 | 010 |
| 110 | 111 |
我们可以通过将选定的控件包装在X门中来改变结果，同时保持它们的平衡。例如，请看下面的电路及其结果表:
| Input states that output 0 | Input states that output 1 |
|---|---|
| 001 | 000 |
| 010 | 011 |
| 100 | 101 |
| 111 | 110 |
4. Qiskit实现
我们现在为3位函数实现Deutsch-Jozsa算法，使用常量和平衡oracles。首先进行导入:
# initialization
import numpy as np
# importing Qiskit
from qiskit import IBMQ, Aer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, assemble, transpile
# import basic plot tools
from qiskit.visualization import plot_histogram
接下来，设置oracle输入寄存器的大小:
# set the length of the n-bit input string.
n = 3
4.1 常数Oracle
让我们从创建一个常量oracle开始，在这种情况下，输入对输出没有影响，所以我们只是随机设置输出量子比特为0或1:
# set the length of the n-bit input string.
n = 3
const_oracle = QuantumCircuit(n+1)
output = np.random.randint(2)
if output == 1:
const_oracle.x(n)
const_oracle.draw()
4.2 平衡Oracle
balanced_oracle = QuantumCircuit(n+1)
接下来，我们创建一个平衡的oracle。正如我们在1b节中看到的，我们可以通过执行CNOTs，将每个输入量子比特作为控制，将输出比特作为目标来创建一个平衡oracle。我们可以通过将一些控制包在X门中来改变给出0或1的输入状态。让我们首先选择一个长度为n的二进制字符串，指定要包装哪些控件:
b_str = "101"
现在我们有了这个字符串，我们可以用它作为放置X门的键。对于电路中的每个量子比特，如果b_str中对应的数字为1，则放置一个X门，如果数字为0，则不执行任何操作。
balanced_oracle = QuantumCircuit(n+1)
b_str = "101"
# Place X-gates
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
balanced_oracle.x(qubit)
balanced_oracle.draw()
接下来，我们进行受控非门，将每个输入量子比特作为控制，输出量子比特作为目标:
balanced_oracle = QuantumCircuit(n+1)
b_str = "101"
# Place X-gates
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
balanced_oracle.x(qubit)
# Use barrier as divider
balanced_oracle.barrier()
# Controlled-NOT gates
for qubit in range(n):
balanced_oracle.cx(qubit, n)
balanced_oracle.barrier()
balanced_oracle.draw()
最后，我们重复两个单元格的代码，以完成X门中的控件包装:
balanced_oracle = QuantumCircuit(n+1)
b_str = "101"
# Place X-gates
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
balanced_oracle.x(qubit)
# Use barrier as divider
balanced_oracle.barrier()
# Controlled-NOT gates
for qubit in range(n):
balanced_oracle.cx(qubit, n)
balanced_oracle.barrier()
# Place X-gates
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
balanced_oracle.x(qubit)
# Show oracle
balanced_oracle.draw()
我们刚刚创造了一个平衡的oracle!剩下要做的就是看看Deutsch-Jozsa算法能否解决这个问题。
4.3 完整算法
现在让我们把所有东西放在一起。算法中的第一步是初始化状态 |+⟩ 中的输入量子比特和状态 |−⟩ 中的输出量子比特:
dj_circuit = QuantumCircuit(n+1, n)
# Apply H-gates
for qubit in range(n):
dj_circuit.h(qubit)
# Put qubit in state |->
dj_circuit.x(n)
dj_circuit.h(n)
dj_circuit.draw()
接下来，让我们应用oracle。这里我们应用上面创建的balanced_oracle:
dj_circuit = QuantumCircuit(n+1, n)
# Apply H-gates
for qubit in range(n):
dj_circuit.h(qubit)
# Put qubit in state |->
dj_circuit.x(n)
dj_circuit.h(n)
# Add oracle
dj_circuit += balanced_oracle
dj_circuit.draw()
最后，我们对 n 个输入量子比特执行H门，并测量我们的输入寄存器:
dj_circuit = QuantumCircuit(n+1, n)
# Apply H-gates
for qubit in range(n):
dj_circuit.h(qubit)
# Put qubit in state |->
dj_circuit.x(n)
dj_circuit.h(n)
# Add oracle
dj_circuit += balanced_oracle
# Repeat H-gates
for qubit in range(n):
dj_circuit.h(qubit)
dj_circuit.barrier()
# Measure
for i in range(n):
dj_circuit.measure(i, i)
# Display circuit
dj_circuit.draw()
让我们看看输出:
# use local simulator
aer_sim = Aer.get_backend('aer_simulator')
qobj = assemble(dj_circuit, aer_sim)
results = aer_sim.run(qobj).result()
answer = results.get_counts()
plot_histogram(answer)
从上面的结果可以看出，测量000的可能性为0%。这正确地预测了函数是平衡的。
4.4 广义电路
下面，我们提供一个通用函数，创建Deutsch-Jozsa oracle并将其转换为量子门。它接受这样的情况(balanced 或 constant），以及输入寄存器的大小n:
def dj_oracle(case, n):
# We need to make a QuantumCircuit object to return
# This circuit has n+1 qubits: the size of the input,
# plus one output qubit
oracle_qc = QuantumCircuit(n+1)
# First, let's deal with the case in which oracle is balanced
if case == "balanced":
# First generate a random number that tells us which CNOTs to
# wrap in X-gates:
b = np.random.randint(1,2**n)
# Next, format 'b' as a binary string of length 'n', padded with zeros:
b_str = format(b, '0'+str(n)+'b')
# Next, we place the first X-gates. Each digit in our binary string
# corresponds to a qubit, if the digit is 0, we do nothing, if it's 1
# we apply an X-gate to that qubit:
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
oracle_qc.x(qubit)
# Do the controlled-NOT gates for each qubit, using the output qubit
# as the target:
for qubit in range(n):
oracle_qc.cx(qubit, n)
# Next, place the final X-gates
for qubit in range(len(b_str)):
if b_str[qubit] == '1':
oracle_qc.x(qubit)
# Case in which oracle is constant
if case == "constant":
# First decide what the fixed output of the oracle will be
# (either always 0 or always 1)
output = np.random.randint(2)
if output == 1:
oracle_qc.x(n)
oracle_gate = oracle_qc.to_gate()
oracle_gate.name = "Oracle" # To show when we display the circuit
return oracle_gate
让我们创建一个函数，接收这个oracle门并对其执行Deutsch-Jozsa算法:
def dj_algorithm(oracle, n):
dj_circuit = QuantumCircuit(n+1, n)
# Set up the output qubit:
dj_circuit.x(n)
dj_circuit.h(n)
# And set up the input register:
for qubit in range(n):
dj_circuit.h(qubit)
# Let's append the oracle gate to our circuit:
dj_circuit.append(oracle, range(n+1))
# Finally, perform the H-gates again and measure:
for qubit in range(n):
dj_circuit.h(qubit)
for i in range(n):
dj_circuit.measure(i, i)
return dj_circuit
最后，让我们使用这些函数来玩转算法:
n = 4
oracle_gate = dj_oracle('balanced', n)
dj_circuit = dj_algorithm(oracle_gate, n)
dj_circuit.draw()
看看运行这个电路的结果:
transpiled_dj_circuit = transpile(dj_circuit, aer_sim)
qobj = assemble(transpiled_dj_circuit)
results = aer_sim.run(qobj).result()
answer = results.get_counts()
plot_histogram(answer)
5.真实设备实验
我们可以在真实的设备上运行电路，如下所示。我们首先寻找能够处理电路的最不繁忙的设备。
该单元使用量子硬件。要在浏览器中运行它，请点击这里进入IBM Quantum体验。
# Load our saved IBMQ accounts and get the least busy backend device with greater than or equal to (n+1) qubits
IBMQ.load_account()
provider = IBMQ.get_provider(hub='ibm-q')
backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits >= (n+1) 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
transpiled_dj_circuit = transpile(dj_circuit, backend, optimization_level=3)
job = backend.run(transpiled_dj_circuit)
job_monitor(job, interval=2)
该单元使用量子硬件。要在浏览器中运行它，请点击这里进入IBM Quantum体验。
# Get the results of the computation
results = job.result()
answer = results.get_counts()
plot_histogram(answer)
可以看到，最可能的结果是1111。其他结果是由于量子计算中的误差。
6.问题
-
你能创造一个不同形式的平衡或常数的oracle吗?
-
函数
dj_problem_oracle(下面)以门的形式返回n = 4的Deutsch-Jozsa oracle。门接收5个量子比特作为输入，其中最后一个量子比特(q_4)是输出量子比特(如上面的oracle示例)。通过给dj_problem_oracle指定1到5之间的不同整数，可以得到不同的oracle。使用Deutsch-Jozsa算法来决定每个oracle是平衡的还是常数的(注意:强烈建议您使用aer_simulator而不是真正的设备来尝试这个例子)。
from qiskit_textbook.problems import dj_problem_oracle
oracle = dj_problem_oracle(1)
7.参考文献
-
David Deutsch and Richard Jozsa (1992). “Rapid solutions of problems by quantum computation”. Proceedings of the Royal Society of London A. 439: 553–558. doi:10.1098/rspa.1992.0167.
-
R. Cleve; A. Ekert; C. Macchiavello; M. Mosca (1998). “Quantum algorithms revisited”. Proceedings of the Royal Society of London A. 454: 339–354. doi:10.1098/rspa.1998.0164.