数値積分の量子アルゴリズム (量子振幅推定による)

お断り

ここで紹介する「積分の量子状態埋め込み」の方法は、あくまで一例(下記論文の方法)で、他にもいろいろな方法があります。
Practical numerical integration on NISQ devices
特に上記論文ではNISQで実行するために埋め込みを単純化しています。
ただ、積分値を振幅に埋め込んで、振幅推定で出すという流れは変わりません。

本題

さて、単位区間 $[0,1]$ 上の1変数関数 $f(x)$ の積分を求めたいとします。

積分とは $x$ 軸と $f(x)$ で囲まれる部分（緑色部分）の面積に等しいです。

いま、緑色部分を含む1辺1の正方形上に、ランダムに点を打ちます。例えば、8個打ちます。

そして、緑色部分に入ったものを"hit"とみなします。この例では6個の点が"hit"しました。

積分とは $x$ 軸と $f(x)$ で囲まれる部分（緑色部分）の面積に等しい

という事実から、ランダムに打った点が"hit"する割合は積分値に一致するはずです。
積分値を $a$ 、打った点の数を $N$ ,hitした点の数を $N_{hit}$ とすると、

a = \int f(x) dx = \frac{N_{hit}}{N} = \frac{6}{8}

と計算できます。

この古典的なアイデアをベースに、 $N_{hit}/N$ を効率的に計算する量子アルゴリズムを考えます。
補助量子ビットを1つ持ってきて、ヒルベルト空間を2つに割ります。

そして、点がhitであったかどうかに応じて、点を”仕分け”していきます。ここで点を量子状態に対応させています。

ここで、各点に2進数で名前をつけました。点は全部で8個あったので、ラベルは3量子ビットで足りることになります。

仕分けされた量子状態は、
$$
| \psi \rangle = \frac{1}{\sqrt{8}}{ (|000 \rangle + |101 \rangle) \otimes |0 \rangle + (|001 \rangle + |010 \rangle ... + |111 \rangle) \otimes |1 \rangle }
$$

このように書けます。
この仕分け操作は実際には量子ゲート演算 $A$ で書かれている必要があります。

ここで以下のようなベクトルを定義します。

| \psi_{0} \rangle = \frac{1}{\sqrt{2}} (|000 \rangle + |101 \rangle) \otimes |0 \rangle )

| \psi_{1} \rangle = \frac{1}{\sqrt{6}} (|001 \rangle + |010 \rangle ... + |111 \rangle) \otimes |1 \rangle )

特に、これら2つのベクトルは正規直交です。

すると、仕分けされた量子状態 $|\psi \rangle$ は、これらの和になっていて、

| \psi \rangle = \frac{1}{\sqrt{8}} (\sqrt{2}|\psi_{0} \rangle + \sqrt{6}|\psi_{1} \rangle )

このように書けます。
$|\psi_{1} \rangle$ の振幅が、求めたい積分値 $a$ (の平方根 $\sqrt{a}$ )になっていることがわかります。

これで、積分計算を量子状態の振幅を求める問題にすり替えることができました。

量子状態の振幅を効率的に計算するアルゴリズムとして、量子振幅推定(Quantum amplitude estimation: QAE)があります。
QAEを用いると、仕分け操作 $A$ を呼び出す回数が（愚直な方法に比べて）平方根になるそうです。

量子振幅推定(Quantum amplitude estimation: QAE)

QAEでは、まず問題に依存した演算 $Q$ というものを作ります。
$Q$ を作るには、およそ以下の2つが必要です。

仕分けをする演算子 $A$
$|\psi_{1} \rangle$ だけの符号を反転させる演算 $O$

$A$ はよいとして、 $O$ はどうすればよいでしょうか。
今回の例では $|\psi_{1} \rangle$ は補助量子ビットが $|1 \rangle$ の状態として条件付けられていますので、
補助量子ビットに $Z$ 演算子を作用させれば $O$ の役割が果たせます。

$Q$ を用意（量子ゲートの組み合わせになります）したあと、 $Q$ の固有値に着目します。
$Q$ は量子ゲートの組み合わせ、すなわちユニタリ演算ですので、固有値の絶対値は1であり、 $e^{j\theta}$ と書けます。
実は、 $|\psi_{1} \rangle$ の振幅を $\sin\phi$ とおくと、振幅と固有値の位相の間に $\phi = \frac{\theta}{2}$ という関係が成り立っています。
この関係式は、線形代数をすれば証明可能です。

これで、振幅推定をユニタリ行列の固有値の位相推定にすり替えることができました。
ユニタリ行列の固有値の位相であれば、効率的に推定する方法があります。
量子位相推定です。

量子位相推定(Quantum Phase estimation: QPE)

QPEについては、手前味噌ですが、
量子位相推定(blueqat blog)
にまとめています。

QPEを行うと、固有値の位相が2進小数 $n$ 桁精度で求まります。
$n$ はQPEで使う補助量子ビット数に比例します。

QPEで位相がわかれば、求めたかった確率振幅がわかりますので、積分値もわかることになります。
ただし、QPEはゲートの深さが長くなりやすいアルゴリズムですので、NISQでの実行は困難とされています。
振幅推定だけであれば、QPEを使わなければいけないわけではなく、他にも色々と方法が提案されています。

実装例

$N=4$ として、 $N_{hit}=1$ ( $01$ がhit) であったとします。
積分 $a=1/4=0.25$ 　であることが明らかですが、量子アルゴリズムでやってみます。

先程と同様に、”仕分けられた量子状態”は

| \psi_{0} \rangle = \frac{1}{\sqrt{3}} (|00 \rangle + |10 \rangle + |11 \rangle) \otimes |0 \rangle )

| \psi_{1} \rangle = \frac{1}{\sqrt{1}} |01 \rangle\otimes |1 \rangle )

| \psi \rangle = \frac{1}{\sqrt{4}} (\sqrt{3}|\psi_{0} \rangle + \sqrt{1}|\psi_{1} \rangle )

となります。
$|\psi_{1} \rangle$ の振幅 $\frac{1}{\sqrt{4}}$ が、求めたい積分 $a=\frac{1}{4}$ の平方根になっていますね。

qiskitのQAEライブラリを使って、振幅推定をしてみます。

# pip install qiskit pylatexenc
from qiskit import QuantumCircuit
from qiskit.aqua.algorithms import Grover, QPE
from qiskit import Aer, execute
from qiskit.aqua import QuantumInstance
import numpy as np

nqubit = 3
# the state we desire to find is '011'
good_state = ['011']

# specify the oracle that marks the state '011' as a good solution
oracle = QuantumCircuit(nqubit)
oracle.z(0)

state_preparation = QuantumCircuit(nqubit, name='State preparation')
state_preparation.h([1,2])
state_preparation.x(2)
state_preparation.ccx(2,1,0)
state_preparation.x(2)

# define Grover's algorithm
grover = Grover(oracle=oracle, good_state=good_state, state_preparation=state_preparation)

from qiskit.aqua.algorithms import AmplitudeEstimation
num_eval_qubits = 3
QAE = AmplitudeEstimation(num_eval_qubits, state_preparation=state_preparation, grover_operator=grover.grover_operator, quantum_instance=Aer.get_backend('qasm_simulator'))

QAE.construct_circuit().draw('mpl')

result = QAE.run()
result.a_estimation

0.1464466
積分値は0.25ですので、あまり精度は良くありません。
これはQPEで使う補助量子ビットをケチった（上記コードでは3 qubit)ためで、
補助量子ビットを増やしていくと0.25に漸近していきます。

まとめ

数値積分を計算する量子アルゴリズムが存在する
積分を確率振幅の推定に置き換え、更に位相推定に置き換えて実行。位相推定の高速性は保証されている(QPE)。
積分の数値精度はQPEで使う補助量子ビット数に影響される。また、NISQの場合は、そもそも埋め込み $A$ が複雑であると雑音が入ってくる。
QPEを使ったナイーブな方法は回路が深くなりやすく、他に様々な方法が提案されている。

量子振幅推定と数値積分

量子熊

数値積分の量子アルゴリズム (量子振幅推定による)

お断り

本題

量子振幅推定(Quantum amplitude estimation: QAE)

量子位相推定(Quantum Phase estimation: QPE)

実装例

まとめ