Qiskit-汉化3.9 Quantum Counting

Dora Dōjo
1

量子计算

要理解这个算法，首先理解Grover算法和量子相位估计算法是很重要的。Grover算法试图找到Oracle的解决方案，而量子计数算法告诉我们有多少个这样的解决方案。该算法结合了量子搜索和量子相位估计，非常有趣。
内容

1. 概述

1.1直觉

在量子计数中，我们简单地使用量子相位估计算法来寻找Grover搜索迭代的特征值。你会记得Grover算法 G 的迭代，以 |\omega\rangle ， |s ' \rangle 为基，将状态向量旋转 \theta :

1

搜索空间中解的百分比会影响 |s\rangle 和 |s ' \rangle 之间的差值。例如，如果解不多， |s\rangle 将非常接近 |s ' \rangle ，而 \theta 将非常小。原来Grover迭代器的特征值是 e^{\pm i\theta} ，我们可以用量子相位估计(QPE)提取这个值来估计解的个数( M )。

1.2仔细观察

在 |\omega\rangle ， |s ' \rangle 基中，我们可以将Grover迭代器写成这样的矩阵:

G = \begin{pmatrix} \cos{\theta} && -\sin{\theta}\\ \sin{\theta} && \cos{\theta} \end{pmatrix}

矩阵 G 具有如下特征向量:

\begin{pmatrix} -i\\ 1 \end{pmatrix} , \begin{pmatrix} i\\ 1 \end{pmatrix}

用前面提到的特征值 e^{\pm i\theta} 。幸运的是，我们不需要在这两个状态中准备寄存器，状态 |s\rangle 在由 |\omega\rangle ， |s ' \rangle 构成的空间中，因此是两个向量的叠加。

|s\rangle = \alpha |\omega\rangle + \beta|s'\rangle

因此，QPE算法的输出将是两个相位的叠加，当我们测量寄存器时，会得到这两个值之一!然后，我们可以使用一些简单的数学来估计 M 。

2

2. 代码

2.1初始化代码

首先，让我们导入我们需要的所有东西:

import matplotlib.pyplot as plt
import numpy as np
import math

# importing Qiskit
import qiskit
from qiskit import QuantumCircuit, transpile, assemble, Aer

# import basic plot tools
from qiskit.visualization import plot_histogram

在本指南中，我们将选择对电路中的前4个量子比特“计数”(我们称计数量子比特的数量为 t ，因此 t = 4 )，并“搜索”最后4个量子比特( n = 4 )。考虑到这一点，我们可以开始创建电路的构建块。

2.2 Controlled-Grover迭代

我们已经在Grover算法一节中介绍了Grover迭代。下面是一个Oracle的例子，我们知道它有5个解( M = 5 )有16个状态( N = 2^ N = 16 )，结合扩散算子:

def example_grover_iteration():
    """Small circuit with 5/16 solutions"""
    # Do circuit
    qc = QuantumCircuit(4)
    # Oracle
    qc.h([2,3])
    qc.ccx(0,1,2)
    qc.h(2)
    qc.x(2)
    qc.ccx(0,2,3)
    qc.x(2)
    qc.h(3)
    qc.x([1,3])
    qc.h(2)
    qc.mct([0,1,3],2)
    qc.x([1,3])
    qc.h(2)
    # Diffuser
    qc.h(range(3))
    qc.x(range(3))
    qc.z(3)
    qc.mct([0,1,2],3)
    qc.x(range(3))
    qc.h(range(3))
    qc.z(3)
    return qc

注意，python函数不接受任何输入，并返回一个具有4个量子比特的量子电路对象。在过去，你创建的函数可能修改了现有的电路，但这样的函数允许我们将量子电路对象转换为我们可以控制的单个门。

我们可以使用.to_gate()和.control()从电路中创建一个受控门。我们将自己的Grover迭代器命名为grit，受控的Grover迭代器命名为cgrit:

# Create controlled-Grover
grit = example_grover_iteration().to_gate()
grit.label = "Grover"
cgrit = grit.control()

2.3逆QFT

我们现在需要创建一个逆QFT。这段代码实现了n个量子比特上的QFT:

def qft(n):
    """Creates an n-qubit QFT circuit"""
    circuit = QuantumCircuit(4)
    def swap_registers(circuit, n):
        for qubit in range(n//2):
            circuit.swap(qubit, n-qubit-1)
        return circuit
    def qft_rotations(circuit, n):
        """Performs qft on the first n qubits in circuit (without swaps)"""
        if n == 0:
            return circuit
        n -= 1
        circuit.h(n)
        for qubit in range(n):
            circuit.cp(np.pi/2**(n-qubit), qubit, n)
        qft_rotations(circuit, n)
    
    qft_rotations(circuit, n)
    swap_registers(circuit, n)
    return circuit

再次注意，我们选择返回另一个量子电路对象，这样我们就可以轻松地反转门。我们创建了t = 4个量子比特的门，因为这是我们在本指南中选择的计数量子比特的数量:

qft_dagger = qft(4).to_gate().inverse()
qft_dagger.label = "QFT†"

2.4整合

现在我们有了完成整个电路所需的一切!让我们把它放在一起。

首先，我们需要将所有量子比特放入 |+\rangle 状态:

# Create QuantumCircuit
t = 4   # no. of counting qubits
n = 4   # no. of searching qubits
qc = QuantumCircuit(n+t, t) # Circuit with n+t qubits and t classical bits

# Initialize all qubits to |+>
for qubit in range(t+n):
    qc.h(qubit)

# Begin controlled Grover iterations
iterations = 1
for qubit in range(t):
    for i in range(iterations):
        qc.append(cgrit, [qubit] + [*range(t, n+t)])
    iterations *= 2
    
# Do inverse QFT on counting qubits
qc.append(qft_dagger, range(t))

# Measure counting qubits
qc.measure(range(t), range(t))

# Display the circuit
qc.draw()

3
3694×503 22.5 KB

太棒了!现在让我们看看结果。

3.模拟

# Execute and see results
aer_sim = Aer.get_backend('aer_simulator')
transpiled_qc = transpile(qc, aer_sim)
qobj = assemble(transpiled_qc)
job = aer_sim.run(qobj)
hist = job.result().get_counts()
plot_histogram(hist)

4

我们可以看到有两个值非常突出，它们的测量概率比其他值高得多。这两个值分别对应 e^{i\theta} 和 e^{-i\theta} ，但我们还不知道解的个数。我们需要更多的处理来获取这些信息，所以首先让我们将输出转换为可以使用的东西(int)。

我们将从输出数据中得到最可能的结果字符串:

measured_str = max(hist, key=hist.get)

现在我们将其存储为整数:

measured_int = int(measured_str,2)
print("Register Output = %i" % measured_int)

寄存器输出= 11

4. 求解的个数(M)

我们将创建一个函数calculate_M()，它将我们寄存器的十进制整数输出、计数量子比特的数量( t )和搜索量子比特的数量( n )作为输入。
首先，我们想从measured_int中获取 \theta 。你应该还记得，QPE从特征值 e^{2\pi i\phi} 得到测量值 \text{value} = 2^n \phi ，所以要得到 \theta ，我们需要:

\theta = \text{value}\times\frac{2\pi}{2^t}

或者，在代码中:

theta = (measured_int/(2**t))*math.pi*2
print("Theta = %.5f" % theta)

\theta = 4.31969

你可能还记得，角 \theta/2 可以由 |s\rangle 和 |s’\rangle 的内积得到:

5

\langle s'|s\rangle = \cos{\tfrac{\theta}{2}}

而 |s\rangle (计算基态的均匀叠加)可以写成 |\omega\rangle 和 |s'\rangle ，如下:

|s\rangle = \sqrt{\tfrac{M}{N}}|\omega\rangle + \sqrt{\tfrac{N-M}{N}}|s'\rangle

|s\rangle 和 |s'\rangle 的内积为:

\langle s'|s\rangle = \sqrt{\frac{N-M}{N}} = \cos{\tfrac{\theta}{2}}

由此，我们可以使用一些三角函数和代数来表示:

N\sin^2{\frac{\theta}{2}} = M

在Grover的算法章节中，你会记得创建扩散算子 U_s 的常用方法实际上是实现 −U_s 。此实现在本章提供的Grover迭代中使用。在普通的Grover搜索中，这个阶段是全局的，可以忽略，但现在我们可以控制Grover的迭代，这个阶段确实有影响。结果是，我们已经有效地搜索了不是解的状态，我们的量子计数算法将告诉我们有多少状态不是解。为了解决这个问题，我们只需计算 N-M 。

在代码中：

N = 2**n
M = N * (math.sin(theta/2)**2)
print("No. of Solutions = %.1f" % (N-M))

解决方案数量 = 4.9

我们可以看到，我们(大约)得到了正确答案!我们可以使用以下方法粗略计算此答案中的误差:

m = t - 1 # Upper bound: Will be less than this 
err = (math.sqrt(2*M*N) + N/(2**(m+1)))*(2**(-m))
print("Error < %.2f" % err)

误差< 2.48
解释误差计算超出了本文的范围，但可以在[1]中找到解释。

最后，完成的函数calculate_M()如下所示:

def calculate_M(measured_int, t, n):
    """For Processing Output of Quantum Counting"""
    # Calculate Theta
    theta = (measured_int/(2**t))*math.pi*2
    print("Theta = %.5f" % theta)
    # Calculate No. of Solutions
    N = 2**n
    M = N * (math.sin(theta/2)**2)
    print("No. of Solutions = %.1f" % (N-M))
    # Calculate Upper Error Bound
    m = t - 1 #Will be less than this (out of scope) 
    err = (math.sqrt(2*M*N) + N/(2**(m+1)))*(2**(-m))
    print("Error < %.2f" % err)

5. 练习

  1. 你可以用不同数量的解决方案创建一个oracle吗?量子计数算法的精度如何变化?

  2. 你能调整电路以使用更多或更少的计数量子比特来获得不同的结果精度吗?

6. 参考文献

[1] Michael A. Nielsen and Isaac L. Chuang. 2011. Quantum Computation and Quantum Information: 10th Anniversary Edition (10th ed.). Cambridge University Press, New York, NY, USA.

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:46:06 2021 BST