このアルゴリズムを理解するためには、最初にグローバーのアルゴリズムと量子位相推定アルゴリズムの両方を理解することは大切なことです。グローバーアルゴリズムがオラクルの解を見つけようとするのに対し、量子数え上げのアルゴリズムは、この問題の解の数を見つけます。このアルゴリズムは量子探索アルゴリズムと量子位相推定アルゴリズムの両方を結びつけるので、大変興味深いものです。
目次
- 概要
1.1 知識
1.2 より詳しく見る - コード
2.1 コードの初期化
2.2 制御グローバ探索の反復
2.3 逆量子フーリエ変換
2.4 合わせてみましょう！ - シミュレーション
- 解の数(M)を見つける
- 練習問題
- 参考文献
グローバー探索の反復の固有値を見つけるために量子位相推定アルゴリズムを使います。グローバー探索の反復演算$G$は、$|\omega\rangle$、$|s'\rangle$基底で、状態ベクトルを$\theta$回転させるものであることを覚えているでしょう。：
探索空間の解の数の割合は$|s\rangle$と$|s’\rangle$の違いに依存します。例えば、もしたくさんの解がないならば、基底$|s\rangle$は基底$|s’\rangle$に近く、そして角度$\theta$ はとても小さいでしょう。グローバーの反復の固有値は$e^{\pm i\theta}$であることが分かり、量子位相推定を使って、解の数($M$)を推定します。
$|\omega\rangle$、$|s'\rangle$ 基底で、グローバー反復演算は以下の行列で書き表せます。：
$$ 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$は以下のように２つのベクトルの重ね合わせとなります。
$$ |s\rangle = \alpha |\omega\rangle + \beta|s'\rangle $$その結果、QPEアルゴリズムの出力は2つの位相の重ね合わせになり、レジスターを測定すると、これら2つの値のいずれかが得られます！次に、いくつかの簡単な数学を使用して、$𝑀$の推定値を取得できます。
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$)。これを使って、回路の構成ブロックを作ります。
グローバーのアルゴリズムの章で、既に「グローバー反復」を扱いました。これは、拡散オペレーターが組み込まれた、16の状態($N = 2^n = 16$)のうち５つの解($M = 5$) をもつオラクルの例です。：
def example_grover_iteration():
"""Small circuit with 5/16 solutions"""
# 回路を作る
qc = QuantumCircuit(4)
# オラクル
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)
# 拡散
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量子ビットのQuantumCircuitオブジェクトを返すことに注意してください。過去にあなたが作った関数は既存の回路を変更するものだったかもしれませんが、この関数は QuantumCircuitオブジェクトを単一制御ゲートに変えることができます。
回路から制御ゲートを作り出すために.to_gate()と.control()を使います。私たちはグローバー反復演算をgritと呼び、制御グローバー反復演算をcgritと呼びます。
# 制御されたグローバーの作成
grit = example_grover_iteration().to_gate()
grit.label = "Grover"
cgrit = grit.control()
def qft(n):
#n量子ビットのQFT回路を作成
"""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):
#swapゲートなしで回路で最初にn量子ビットのQFTを実装する
"""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
ここでも、別のQuantumCircuitオブジェクトを返すことを選んだことに注意してください。これは、ゲートを簡単に反転できるようにするためです。
このガイドで選択したカウント量子ビット数である、$t = 4$量子ビットでゲートを作成します。
qft_dagger = qft(4).to_gate().inverse()
qft_dagger.label = "QFT†"
# 量子回路の作成
t = 4 # カウントする量子ビットの数
n = 4 # 探索する量子ビットの数
qc = QuantumCircuit(n+t, t) # 古典ビットとn+t量子ビットの回路
# 全ての量子ビットを |+>に初期化する
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()
素晴らしい！結果をいくつか確かめましょう。
# 実行してみましょう。そして結果を確かめてみましょう。
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)
他の測定値より測定確率が高い2つの値(0101と1011)をシミュレーションから確認することができます。これら２つの値は$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)
theta = (measured_int/(2**t))*math.pi*2
print("Theta = %.5f" % theta)
$|s\rangle$と$|s’\rangle$の内積から角度$\theta/2$を得ることができることを覚えているかもしれません。：
このベクトルの内積は：
$$ \langle s'|s\rangle = \sqrt{\frac{N-M}{N}} $$これらの方程式を組み合わせて、三角法と代数を使用して次のことを示すことができます。
$$ N\sin^2{\frac{\theta}{2}} = M $$グローバーのアルゴリズムの章から、拡散演算子 $U_s$を作成する一般的な方法は、実際は$-U_s$を実装することを覚えているでしょう。 この実装は、この章で提供されるグローバー反復で使用されます。通常のグローバー探索では、この位相はグローバルであり、無視できますが、グローバー反復を制御ゲートとして使っているため、この位相には意味があり、そのため、解ではない状態が探索されます。量子数え上げアルゴリズムにより、解ではない状態の数がわかります。 これを修正するには、$N-M$を計算するだけです。
以下、コード：
N = 2**n
M = N * (math.sin(theta/2)**2)
print("No. of Solutions = %.1f" % (N-M))
おおよそ、正しい解を得ることができました!この解のエラーは以下で概算できます。
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)
誤差の計算の説明はこの節の範囲外です。 しかし、説明は[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)
import qiskit.tools.jupyter
%qiskit_version_table