Qiskit汉化-3.4 Simon's Algorithm

Dora Dōjo
1

Simon算法

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

1. 简介

西蒙算法首次在参考文献[1]中提出，是第一个在解决特定问题时与最佳经典算法相比呈现指数级加速的量子算法。这启发了基于量子傅里叶变换的量子算法，其中应用最著名的量子算法是：Shor质因数分解算法。

1a. Simon问题

我们得到一个未知的黑箱函数 f ，它被保证为一对一 (1:1) 或二对一 (2:1) ，其中一对一和二对一的函数具有以下性质：

  • 一对一：对每个输入都有一个唯一的输出。一个具有4个输入的函数的例子是：
f(1) \rightarrow 1, \quad f(2) \rightarrow 2, \quad f(3) \rightarrow 3, \quad f(4) \rightarrow 4
  • 二对一：准确地将两个输入映射到每个唯一的输出。一个具有4个输入的函数的例子是：
f(1) \rightarrow 1, \quad f(2) \rightarrow 2, \quad f(3) \rightarrow 1, \quad f(4) \rightarrow 2

这种二对一的映射取决于一个隐藏的比特串b，其中：

\textrm{given }x_1,x_2: \quad f(x_1) = f(x_2) \\ \textrm{it is guaranteed }: \quad x_1 \oplus x_2 = b

给定一个黑箱 f ，我们多快可以确定 f 是一对一还是二对一？然后，如果 f 是二对一，我们多快可以确定 f ？事实证明，这两种情况都可以归结为寻找 f 的问题，其中比特串 b={000...} 代表一对一的 f 。
 

1b. Simon算法

经典解决方案

传统上，对于一个给定的 f ，如果我们想100%确定 b 是什么，我们必须检查多达 2^{n-1}+1 个输入，其中n是输入的比特数。这意味着要检查所有可能的输入的一半以上，直到我们找到输出相同的两种情况。与Deutsch-Jozsa问题一样，如果我们运气好的话，我们可以通过前两次尝试就解决这个问题。但是，如果我们碰巧得到一个一对一的 f ，或者非常不走运地得到了一个二对一的 f ，那么我们就会被困在整个 2^{n-1}+1 。目前有一些已知算法，其下限为 \Omega(2^{n/2}) (见下方参考文献2)，但一般来说，复杂度会随着n的增加呈指数级增长。

量子解决方案

实现Simon算法的量子电路如下图所示。

1
1680×573 20.2 KB

其中的查询函数 Q_f 对两个量子寄存器的作用为：

\ket{x} \ket{a} \rightarrow \ket{x} \ket{a \oplus f(x)}

在第二个寄存器处于状态 \ket{0} = \ket{00\dots0} 的特定情况下，我们有：

\ket{x} \ket{0} \rightarrow \ket{x} \ket{f(x)}

该算法包括以下步骤。

  1. 两个 n 量子比特输入寄存器初始化为0状态：
\ket{\psi_1} = \ket{0}^{\otimes n} \ket{0}^{\otimes n}
  1. 对第一个寄存器应用Hadamard变换：
\ket{\psi_2} = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^{n} } \ket{x}\ket{0}^{\otimes n}
  1. 应用查询函数 Q_f ：
\ket{\psi_3} = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^{n} } \ket{x}\ket{f(x)}

  1. 测量第二个寄存器。将观察到 f(x) 的某个值。由于问题的设定，观测值 f(x) 可能对应于两种可能的输入： x 和 y=x⊕b 。因此，第一个寄存器变为：

    \ket{\psi_4} = \frac{1}{\sqrt{2}} \left( \ket{x} + \ket{y} \right)

    我们省略了第二个寄存器，因为它已经被测量过了。

  2. 对第一个寄存器应用Hadamard：

\ket{\psi_5} = \frac{1}{\sqrt{2^{n+1}}} \sum_{z \in \{0,1\}^{n} } \left[ (-1)^{x \cdot z} + (-1)^{y \cdot z} \right] \ket{z}

  1. 测量第一个寄存器只有在以下情况下才会有输出：

    (-1)^{x \cdot z} = (-1)^{y \cdot z}

    这意味着：

    x \cdot z = y \cdot z \\ x \cdot z = \left( x \oplus b \right) \cdot z \\ x \cdot z = x \cdot z \oplus b \cdot z \\ b \cdot z = 0 \text{ (mod 2)}

    一个字符串 \ket{z} 将被测量，其与 \ket{b} 的内积等于0。因此，重复该算法大约 \ket{n} 次，我们能得到 \ket{n} 个不同的 \ket{z} 值，并可以写出以下方程组：

    \begin{cases} b \cdot z_1 = 0 \\ b \cdot z_2 = 0 \\ \quad \vdots \\ b \cdot z_n = 0 \end{cases}

    由此可以确定 \ket{b} ，例如通过高斯消元法。

因此，在这个特定的问题上，量子算法执行的步骤比经典算法少了指数级。同样，可能很难设想这种算法的应用（尽管它启发了Shor创造的最著名的算法），但它首次证明了使用量子计算机在解决一个特定问题时相较于经典计算机可以有指数级的加速。

2. 实例

让我们看看2个量子比特的Simon算法的例子，秘密字符串 b=11 ，因此，如果 y=x⊕b ，则 f(x)=f(y) 。解决该问题的量子电路如下：

2
2835×465 21.6 KB

  1. 两个 2 -量子比特输入寄存器初始化为0状态：
\ket{\psi_1} = \ket{00}_1 \ket{00}_2
  1. 对第一个寄存器中的量子比特应用Hadamard门：
\ket{\psi_2} = \frac{1}{2} \left( \ket{00}_1 + \ket{01}_1 + \ket{10}_1 + \ket{11}_1 \right) \ket{00}_2

  1. 对于字符串 b = 11 ，查询函数可以实现为 \text{Q}_f = CX_{1_a 2_a}CX_{1_a 2_b}CX_{1_b 2_a}CX_{1_b 2_b} (如上面的电路图所示)：

    \begin{aligned} \ket{\psi_3} = \frac{1}{2} (\; &\ket{00}_1 \ket{0 \oplus 0 \oplus 0, \quad 0 \oplus 0 \oplus 0}_2 &\\ +&\ket{01}_1 \ket{0 \oplus 0 \oplus 1, \quad 0 \oplus 0 \oplus 1}_2 &\\ +&\ket{10}_1 \ket{0 \oplus 1 \oplus 0, \quad 0 \oplus 1 \oplus 0}_2 &\\ +&\ket{11}_1 \ket{0 \oplus 1 \oplus 1, \quad 0 \oplus 1 \oplus 1}_2 \;) \end{aligned}

    因此：

    \begin{aligned} \ket{\psi_3} = \frac{1}{2} (\; &\ket{00}_1 \ket{00}_2 &\\ +&\ket{01}_1 \ket{11}_2 &\\ +&\ket{10}_1 \ket{11}_2 &\\ +&\ket{11}_1 \ket{00}_2 \;) \end{aligned}

  2. 我们测量第二个寄存器。有 50\% 的概率，我们将看到 \ket{00}_2 或 \ket{11}_2 。为了举例，让我们假设我们看到 \ket{11}_2 。那么系统的状态是

    \ket{\psi_4} = \frac{1}{\sqrt{2}} \left( \ket{01}_1 + \ket{10}_1 \right)

    我们省略了第二个寄存器，因为它已经被测量过了。

  3. 对第一个寄存器应用Hadamard：

\ket{\psi_5} = \frac{1}{2\sqrt{2}} \left[ \left( \ket{0} + \ket{1} \right) \otimes \left( \ket{0} - \ket{1} \right) + \left( \ket{0} - \ket{1} \right) \otimes \left( \ket{0} + \ket{1} \right) \right] \\ = \frac{1}{2\sqrt{2}} \left[ \ket{00} - \ket{01} + \ket{10} - \ket{11} + \ket{00} + \ket{01}- \ket{10} - \ket{11} \right] \\ = \frac{1}{\sqrt{2}} \left( \ket{00} - \ket{11} \right)

  1. 测量第一个寄存器将以相同的概率给出 \ket{00} 或 \ket{11} 。

  2. 如果我们得到 \ket{11} ，那么：

    b \cdot 11 = 0

    这告诉我们， b≠01 或 10 ，剩下的两个可能的解是 b=00 或 b=11 。注意， b=00 总是我们的联立方程的一个平凡解。如果我们多次重复步骤1-6，我们将只测量 \ket{00} 或 \ket{11} ，因为

    b \cdot 11 = 0 \\ b \cdot 00 = 0

    是唯一满足 b=11 的方程。我们可以通过挑选一个随机输入 (x_i) 并检查 f(x_i) = f(x_i \oplus b) 来验证 b=11 。例如：

    01 \oplus b = 10 \\ f(01) = f(10) = 11

3. Qiskit实现

我们现在以 3 量子比特和 b = 110 为例实现Simon算法。

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

# import basic plot tools
from qiskit.visualization import plot_histogram
from qiskit_textbook.tools import simon_oracle

函数simon_oracle(上面导入的)为比特串b创建一个Simon oracle。这里没有给出解释，但我们将在第4节讨论该方法。

在Qiskit中，只允许在量子电路的末端进行测量。在Simon算法中，我们实际上并不关心第二个寄存器的输出，只会测量第一个寄存器。

b = '110'

n = len(b)
simon_circuit = QuantumCircuit(n*2, n)

# Apply Hadamard gates before querying the oracle
simon_circuit.h(range(n))    
    
# Apply barrier for visual separation
simon_circuit.barrier()

simon_circuit += simon_oracle(b)

# Apply barrier for visual separation
simon_circuit.barrier()

# Apply Hadamard gates to the input register
simon_circuit.h(range(n))

# Measure qubits
simon_circuit.measure(range(n), range(n))
simon_circuit.draw()

/usr/local/anaconda3/lib/python3.7/site-packages/ipykernel_launcher.py:12: DeprecationWarning: The QuantumCircuit.__iadd__() method is being deprecated. Use the compose() (potentially with the inplace=True argument) and tensor() methods which are more flexible w.r.t circuit register compatibility.
  if sys.path[0] == '':
/usr/local/anaconda3/lib/python3.7/site-packages/qiskit/circuit/quantumcircuit.py:876: DeprecationWarning: The QuantumCircuit.extend() method is being deprecated. Use the compose() (potentially with the inplace=True argument) and tensor() methods which are more flexible w.r.t circuit register compatibility.
  return self.extend(rhs)

3

3a. 用模拟器进行实验

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

# use local simulator
aer_sim = Aer.get_backend('aer_simulator')
shots = 1024
qobj = assemble(simon_circuit, shots=shots)
results = aer_sim.run(qobj).result()
counts = results.get_counts()
plot_histogram(counts)

4

由于 b 已知，我们可以验证这些结果确实满足 b\cdot z = 0 \pmod{2} :

# Calculate the dot product of the results
def bdotz(b, z):
    accum = 0
    for i in range(len(b)):
        accum += int(b[i]) * int(z[i])
    return (accum % 2)

for z in counts:
    print( '{}.{} = {} (mod 2)'.format(b, z, bdotz(b,z)) )

 110.000 = 0 (mod 2)
 110.110 = 0 (mod 2)
 110.001 = 0 (mod 2)
 110.111 = 0 (mod 2)
 

利用这些结果，我们可以通过求解这组联立方程组恢复出 b = 110 。例如，假设我们第一次测量值为001，这告诉我们：

\begin{aligned} b \cdot 001 &= 0 \\ (b_2 \cdot 0) + (b_1 \cdot 0) + (b_0 \cdot 1) & = 0 \\ (\cancel{b_2 \cdot 0}) + (\cancel{b_1 \cdot 0}) + (b_0 \cdot 1) & = 0 \\ b_0 & = 0\\ \end{aligned}

如果接下来测量值为111，则有:

\begin{aligned} b \cdot 111 &= 0 \\ (b_2 \cdot 1) + (b_1 \cdot 1) + (\cancel{0 \cdot 1}) & = 0 \\ (b_2 \cdot 1) + (b_1 \cdot 1) & = 0 \\ \end{aligned}

这告诉我们要么：

b_2 = b_1 = 0, \quad b = 000

要么：

b_2 = b_1 = 1, \quad b = 110

其中 b=110 是联立方程的非平凡解。我们可以使用高斯消元法来解决这些问题，它的运行时间为 O(n^3) 。

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

第3a节中的电路使用 2n=6 个量子比特，而在撰写本书时，许多IBM量子设备只有5个量子比特。我们将运行相同的代码，但与第二节中的示例一样使用 b=11 ，只需要4个量子比特。

b = '11'
n = len(b)
simon_circuit_2 = QuantumCircuit(n*2, n)

# Apply Hadamard gates before querying the oracle
simon_circuit_2.h(range(n))

# Query oracle
simon_circuit_2 += simon_oracle(b)

# Apply Hadamard gates to the input register
simon_circuit_2.h(range(n))

# Measure qubits
simon_circuit_2.measure(range(n), range(n))
simon_circuit_2.draw()

5

这个电路与第2节中所示的电路略有不同。输出不同，但输入碰撞是相同的，即都具有 f(x) = f(x \oplus 11) 的性质。

# 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')
backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits >= n*2 and 
                                   not x.configuration().simulator and x.status().operational==True))
print("least busy backend: ", backend)

# Execute and monitor the job
from qiskit.tools.monitor import job_monitor
shots = 1024
transpiled_simon_circuit = transpile(simon_circuit_2, backend, optimization_level=3)
qobj = assemble(transpiled_simon_circuit, shots=shots)
job = backend.run(qobj)
job_monitor(job, interval=2)

least busy backend:  ibmq_mumbai
/usr/local/anaconda3/lib/python3.7/site-packages/ipykernel_launcher.py:13: DeprecationWarning: Passing a Qobj to Backend.run is deprecated and will be removed in a future release. Please pass in circuits or pulse schedules instead.
  del sys.path[0]

Job Status: job has successfully run
 

# Get results and plot counts
device_counts = job.result().get_counts()
plot_histogram(device_counts)

6

# Calculate the dot product of the results
def bdotz(b, z):
    accum = 0
    for i in range(len(b)):
        accum += int(b[i]) * int(z[i])
    return (accum % 2)

print('b = ' + b)
for z in device_counts:
    print( '{}.{} = {} (mod 2) ({:.1f}%)'.format(b, z, bdotz(b,z), device_counts[z]*100/shots))

 b = 11
 11.00 = 0 (mod 2) (44.9%)
 11.01 = 1 (mod 2) (2.7%)
 11.10 = 1 (mod 2) (2.5%)
 11.11 = 0 (mod 2) (49.8%)
 

我们可以看到，最重要的结果是那些 b\cdot z = 0 (mod 2)的结果。其他结果是错误的，但发生的概率较低。假设我们不太可能测量到错误的结果，那么我们可以使用经典计算机通过求解线性方程组来恢复 b 的值。对于这种 n=2 的情况， b=11 。

4. Oracle

上面Simon算法的例子和实现是针对特定的 b 值的。为了将问题扩展到其他秘密比特串，我们需要更详细地讨论Simon查询函数或oracle。

Simon算法处理的是如何从oracle f_b 中寻找一个隐藏比特串 b \in \{0,1\}^n ，对于所有 x \in \{0,1\}^n ，满足 f_b(x) = f_b(y) 当且仅当 y = x \oplus b 。这里， \oplus 表示按位异或运算。因此，如果 b = 0\ldots 0 ，即全零比特串，则 f_b 是一个1对1(或者说，置换)函数。否则，如果 b \neq 0\ldots 0 ，则 f_b 是一个2对1函数。

在算法中，oracle接收 \ket{x}\ket{0} 作为输入。对于预定的 b , oracle将其输出写入第二个寄存器，从而将输入转换为 \ket{x}\ket{f_b(x)} ，使得对于所有的 x \in \{0,1\}^n ， f(x) = f(x\oplus b) 均成立。

这种黑盒功能可以通过以下程序实现。

  • 将第一个寄存器的内容复制到第二个寄存器。
\ket{x}\ket{0} \rightarrow \ket{x}\ket{x}
  • （创建1对1或2对1的映射） 如果 b 不是全零，那么有一个最小的索引 j ，使 b_j=1 。如果 x_j = 0 ，则将第二个寄存器与 b 进行异或运算。否则，不改变第二个寄存器。
\ket{x}\ket{x} \rightarrow \ket{x}\ket{x \oplus b} \text{if} ~ x_j = 0 ~ \text{for the least index j}
  • （创建随机置换） 随机置换和翻转第二个寄存器的量子比特。
\ket{x}\ket{y} \rightarrow \ket{x}\ket{f_b(y)}

5. 问题

  1. 使用Qiskit实现一个通用的Simon oracle。
  2. 在模拟器和设备上，使用秘密比特串 b=1001 测试您的通用Simon oracle。结果和你预期的一样吗？说明原因。

6. 参考文献

  1. Daniel R. Simon (1997) “On the Power of Quantum Computation” SIAM Journal on Computing, 26(5), 1474–1483, doi:10.1137/S0097539796298637
  2. Guangya Cai and Daowen Qiu. Optimal separation in exact query complexities for Simon’s problem. Journal of Computer and System Sciences 97: 83-93, 2018, https://doi.org/10.1016/j.jcss.2018.05.001 
import qiskit.tools.jupyter
%qiskit_version_table

 

版本信息

Qiskit Software Version
Qiskit 0.27.0
Terra 0.17.4
Aer 0.8.2
Ignis 0.6.0
Aqua 0.9.2
IBM Q Provider 0.14.0
System information
Python 3.7.7 (default, May 6 2020, 04:59:01) [Clang 4.0.1 (tags/RELEASE_401/final)]
OS Darwin
CPUs 8
Memory (Gb) 32.0

Wed Jun 16 09:23:57 2021 BST