Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

量子位相推定(QPE)

タグ: algorithm primitive resource-estimation

量子位相推定(Quantum Phase Estimation; QPE)は、U∣ψ⟩=e2πiϕ∣ψ⟩U|\psi\rangle = e^{2\pi i \phi}|\psi\rangleを満たすユニタリ行列UUと固有状態∣ψ⟩|\psi\rangleから、固有位相ϕ\phiを推定するアルゴリズムです。Shorのアルゴリズムなど、ユニタリ行列の固有値に埋め込まれた位相を使うアルゴリズムで中心的なプリミティブとして使われますKitaev, 1995Cleve et al., 1998。

このノートブックでは、QPEの手順をQamomileの量子カーネルとして実装し、組み込みのqmc.qpe関数による実装と比較します。さらに、カウント用量子ビット数と推定精度、必要なゲート数の関係を確認します。

背景: 位相キックバックと量子フーリエ変換

QPEは、制御UUゲートによる位相キックバックCleve et al., 1998と、量子フーリエ変換Coppersmith, 2002を組み合わせます。

位相キックバック

位相キックバックは、ユニタリ行列UUの固有状態∣ψ⟩|\psi\rangleに制御UUゲートを適用したとき、UUの固有位相が制御量子ビットの相対位相として現れる仕組みです。次を仮定します。

U∣ψ⟩=e2πiϕ∣ψ⟩.U|\psi\rangle = e^{2\pi i\phi}|\psi\rangle.

1つの制御量子ビットを重ね合わせ状態にし、対象となる量子状態を∣ψ⟩|\psi\rangleに準備します。

∣0⟩+∣1⟩2∣ψ⟩.\frac{|0\rangle + |1\rangle}{\sqrt{2}}|\psi\rangle.

制御UUゲートは、制御量子ビットが∣1⟩|1\rangleである成分にだけUUを適用します。∣ψ⟩|\psi\rangleはUUの固有状態なので、その成分に固有位相が現れます。

∣0⟩∣ψ⟩+∣1⟩U∣ψ⟩2=∣0⟩+e2πiϕ∣1⟩2∣ψ⟩.\frac{|0\rangle|\psi\rangle + |1\rangle U|\psi\rangle}{\sqrt{2}} = \frac{|0\rangle + e^{2\pi i\phi}|1\rangle}{\sqrt{2}}|\psi\rangle.

この変換では、対象となる量子状態は∣ψ⟩|\psi\rangleのまま保たれ、固有位相は制御量子ビットの相対位相に符号化されます。QPEでは、複数の制御量子ビットに対してこの仕組みを意図的に利用します。具体的な符号化方法は「アルゴリズム」節で説明します。

量子フーリエ変換

量子フーリエ変換(QFT)は、計算基底状態を、その値に応じた相対位相を持つ重ね合わせへ写す変換です。M=2mM=2^m個の基底状態に対するQFTは次のように定義されます。

QFTM∣x⟩=1M∑y=0M−1e2πixy/M∣y⟩.\mathrm{QFT}_M|x\rangle = \frac{1}{\sqrt{M}} \sum_{y=0}^{M-1} e^{2\pi i xy/M}|y\rangle.

これは整数xxを、計算基底全体にわたる規則的な位相パターンへ写します。このように、値を各計算基底の相対位相として保持した状態を、ここでは「フーリエ符号化された状態」と呼びます。Qamomileでの応用例は、多次元QFTの記事を参照してください。逆QFT QFTM−1\mathrm{QFT}_M^{-1}は、この変換の逆操作です。ϕ=a/M\phi=a/Mがmmビットで正確に表せる場合、制御U20,U21,…,U2m−1U^{2^0}, U^{2^1}, \ldots, U^{2^{m-1}}ゲートによってカウント用量子ビットは

1M∑k=0M−1e2πiak/M∣k⟩=QFTM∣a⟩.\frac{1}{\sqrt{M}}\sum_{k=0}^{M-1} e^{2\pi i a k/M}|k\rangle = \mathrm{QFT}_M|a\rangle.

ここにQFTM−1\mathrm{QFT}_M^{-1}を適用すると∣a⟩|a\rangleが返ります。重要なことは、逆QFTによって位相の情報を計算基底のビット列に変換できることです。

1M(1e2πia/M⋮e2πia(M−1)/M)⏟位相の値のベクトル→QFTM−1∣a⟩=∣am−1⋯a0⟩⏟計算基底のビット列.\underbrace{ \frac{1}{\sqrt{M}} \begin{pmatrix} 1 \\ e^{2\pi i a/M} \\ \vdots \\ e^{2\pi i a(M-1)/M} \end{pmatrix} }_{\text{位相の値のベクトル}} \xrightarrow{\mathrm{QFT}_M^{-1}} \underbrace{|a\rangle = |a_{m-1}\cdots a_0\rangle}_{\text{計算基底のビット列}}.

アルゴリズム

QPEは、位相を読み出すためのmm個のカウント用量子ビットと、UUの固有状態∣ψ⟩|\psi\rangleを保持する対象量子ビットから構成されます。カウント用量子ビットとは、位相をmmビットの2進小数として読み出すための補助量子ビットです。対象量子ビットへの入力は、U∣ψ⟩=e2πiϕ∣ψ⟩U|\psi\rangle = e^{2\pi i\phi}|\psi\rangleを満たす固有状態∣ψ⟩|\psi\rangleとし、カウント用量子ビットは∣0⟩⊗m|0\rangle^{\otimes m}から始めます。ここでM=2mM=2^mとおきます。

ステップ1:カウント用量子ビットを重ね合わせにする

カウント用量子ビットにアダマールゲートを適用します。これにより、MM個の値の一様重ね合わせが作られます。

∣Ψ1⟩=H⊗m∣0⟩⊗m∣ψ⟩=1M∑r=0M−1∣r⟩∣ψ⟩.|\Psi_1\rangle = H^{\otimes m}|0\rangle^{\otimes m}|\psi\rangle = \frac{1}{\sqrt{M}}\sum_{r=0}^{M-1}|r\rangle|\psi\rangle.

ステップ2:制御U2kU^{2^k}ゲートを適用する

各カウント用量子ビットkkを制御量子ビットとして、制御U2kU^{2^k}ゲートを適用します。r=∑k=0m−1rk2kr=\sum_{k=0}^{m-1} r_k2^kと書くと、対象の固有状態には位相e2πiϕre^{2\pi i\phi r}が乗ります。

∣Ψ2⟩=1M∑r=0M−1e2πiϕr∣r⟩∣ψ⟩.|\Psi_2\rangle = \frac{1}{\sqrt{M}}\sum_{r=0}^{M-1} e^{2\pi i \phi r}|r\rangle|\psi\rangle.

ステップ3:逆QFTで位相情報をビット列へ変換する

ϕ=a/M\phi=a/Mが正確に表せる場合、カウント用量子ビットはQFTM∣a⟩\mathrm{QFT}_M|a\rangleになります。逆QFTを適用すると∣a⟩|a\rangleが返ります。

∣Ψ2⟩=(1M∑r=0M−1e2πiar/M∣r⟩)∣ψ⟩=QFTM∣a⟩∣ψ⟩,|\Psi_2\rangle = \left( \frac{1}{\sqrt{M}}\sum_{r=0}^{M-1} e^{2\pi i ar/M}|r\rangle \right)|\psi\rangle = \mathrm{QFT}_M|a\rangle|\psi\rangle,
∣Ψ3⟩=QFTM−1QFTM∣a⟩∣ψ⟩=∣a⟩∣ψ⟩.|\Psi_3\rangle = \mathrm{QFT}_M^{-1}\mathrm{QFT}_M|a\rangle|\psi\rangle = |a\rangle|\psi\rangle.

ステップ4:ビット列を測定し、位相を復号する

カウント用量子ビットを測定します。正確に表せる場合、測定結果はaaとなり、このビット列を復号した位相の推定値は次のようになります。

ϕ~=aM.\tilde{\phi} = \frac{a}{M}.

ϕ\phiがmmビットで正確に表せない場合、分布は最も近いmmビット近似の周辺に集中します。mmを増やすと表現できる位相の間隔1/2m1/2^mが小さくなるため、推定値を真の固有位相へ近づけられます。

カウント用量子ビット、制御Uゲート、逆QFT、測定からなる量子位相推定回路。

QPE回路の模式図です。カウント用量子ビットが制御UUゲートを通じて位相を蓄積し、逆QFTが蓄積された位相パターンを測定ビット列に変換します。

Qamomileでの実装

ここでは対角な4x4ユニタリ行列を使います。

U=(10000eiθ010000eiθ100000eiθ11).U = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & e^{i\theta_{01}} & 0 & 0 \\ 0 & 0 & e^{i\theta_{10}} & 0 \\ 0 & 0 & 0 & e^{i\theta_{11}} \end{pmatrix}.

この行列では、すべての計算基底状態が固有状態です。対象状態∣01⟩|01\rangleを準備し、推定したい位相θ01/2π\theta_{01} / 2\piを0.6に設定します。0.6は有限の2進小数では正確に表せないため、カウント用量子ビットを増やす効果が見えやすくなります。

phase fractions: [0.   0.6  0.23 0.81]
target phase fraction: 0.60000000
U =
[[ 1.   +0.j     0.   +0.j     0.   +0.j     0.   +0.j   ]
 [ 0.   +0.j    -0.809-0.588j  0.   +0.j     0.   +0.j   ]
 [ 0.   +0.j     0.   +0.j     0.125+0.992j  0.   +0.j   ]
 [ 0.   +0.j     0.   +0.j     0.   +0.j     0.368-0.93j ]]

スクラッチ実装

まず、位相を推定したい4x4ユニタリ行列を定義します。位相ゲートP(θ)P(\theta)は、量子ビットの∣1⟩|1\rangle成分にeiθe^{i\theta}を掛けます。Qamomileでは、このゲートをqmc.p(q, theta)と記述します。そのため、qmc.p(q[0], phi10)は対象量子ビットの最初のビットが1であるすべての基底状態に位相eiθ10e^{i\theta_{10}}を与え、qmc.p(q[1], phi01)は2つ目のビットが1であるすべての基底状態に位相eiθ01e^{i\theta_{01}}を与えます。この時点で∣11⟩|11\rangleにはei(θ10+θ01)e^{i(\theta_{10}+\theta_{01})}が乗っているため、制御位相シフトゲートでは補正分

θ11−θ10−θ01\theta_{11} - \theta_{10} - \theta_{01}

だけを∣11⟩|11\rangleに追加します。これにより、順序付き基底∣00⟩,∣01⟩,∣10⟩,∣11⟩|00\rangle, |01\rangle, |10\rangle, |11\rangleに対する対角成分は、ちょうどdiag⁡(1,eiθ01,eiθ10,eiθ11)\operatorname{diag}(1, e^{i\theta_{01}}, e^{i\theta_{10}}, e^{i\theta_{11}})になります。

<Figure size 678x200 with 1 Axes>

QPEの4つのステップをQamomileの基本操作で実装します。qmc.control(diagonal_4x4)で制御UUゲートを作り、power=2**kで制御U2kU^{2^k}ゲートを適用します。逆QFTの後、量子ビット列を小数部だけを持つQFixedへ変換します。qmc.measureは、この量子ビット列を測定し、得られたビット列を浮動小数点の位相推定値へ復号します。

<Figure size 3236x416 with 1 Axes>

組み込み関数: qpe

qmc.qpe関数は、スクラッチ実装で記述したアダマールゲート、制御U2kU^{2^k}ゲート、逆QFT、QFixedへの変換をまとめて適用します。qmc.qpeが返すQFixed値をqmc.measureに渡すと、量子ビット列の測定と固定小数点値への復号が行われ、浮動小数点の位相推定値が得られます。

<Figure size 3236x416 with 1 Axes>

実行結果

目標位相0.6は少ないビット数では正確に表現できないため、QPEは近いmmビット近似に対応する分布を返します。ここではカウント用量子ビット数を3から9まで変化させ、組み込みのqpe関数による推定値と厳密な位相値を比較します。

(0.625, 3610)
(0.625, 2321)
(0.59375, 3605)
(0.59375, 2399)
(0.6015625, 3596)
(0.6015625, 2332)
(0.599609375, 3571)
(0.625, 3610)
<Figure size 700x350 with 1 Axes>

リソース推定

前のセクションでは、カウント用量子ビットを増やすと精度が上がることを確認しました。ここでは、上のrun_qpe_experiment()で使ったものと同じQPE量子カーネルに、estimate_resources()を直接適用します。この推定には、アダマールゲート、qmc.qpeによる制御U2kU^{2^k}ゲート、逆QFT、最後の固定小数点測定が含まれます。 プロットでは、既定の制御演算分解モデルCLEAN_ANCILLA_TOFFOLIに基づく論理ゲート数gates.totalを使います。測定回数はmeasurements.totalに別途計上されます。エンジン向けのコンパイルや最適化によって、出力回路のゲート数は変わる場合があります。集計モデルの詳細は、リソース推定のチュートリアルを参照してください。

<Figure size 700x350 with 1 Axes>

プロットは、QPEの精度を上げるために必要なカウント用量子ビット数mmと、そのときの総ゲート数を、2m2^mに比例する参照線とともに示しています。目標とする加法誤差をϵ\epsilonとすると、表現できる位相の間隔はおおよそ

2−m≲ϵ2^{-m} \lesssim \epsilon

を満たす必要があります。そのため、必要なカウント用量子ビット数は

m=O ⁣(log⁡1ϵ)m = O\!\left(\log\frac{1}{\epsilon}\right)

です。

今回の実装では、制御U2kU^{2^k}ゲートをUUの反復として構成します。したがって、mm個のカウント用量子ビットに対するUUの適用回数は

∑k=0m−12k=2m−1=O ⁣(1ϵ)\sum_{k=0}^{m-1} 2^k = 2^m - 1 = O\!\left(\frac{1}{\epsilon}\right)

です。つまり、カウント用量子ビット数は1/ϵ1/\epsilonに対して対数的ですが、UUの適用回数はO(1/ϵ)O(1/\epsilon)で増えますNielsen & Chuang, 2012。

このような場合、ゲート数は先ほど見た通りO(1/ϵ)O(1/\epsilon)となり,高精度なQPEを実行するには効率的ではありません。より一般には、あるユニタリ行列VVを実行するために必要なゲート数をG(V)G(V)とすると、QPE本体に必要なゲート数は次のように書けます。

GQPE(m)=∑k=0m−1G ⁣(controlled-U2k)+O(m2)G_{\mathrm{QPE}}(m) = \sum_{k=0}^{m-1} G\!\left(\mathrm{controlled}\text{-}U^{2^k}\right) + O(m^2)

しかし、実際にはこの見積もりは大きく変わる可能性があります。上式はQPE本体のゲート数を表しており、初期状態の準備コストは含みません。また、各制御U2kU^{2^k}ゲートのゲート数は、その実装方法に依存します。以下では、この2点を分けて説明します。

  1. 制御UUゲートの実装コスト

    QPEは、Shorのアルゴリズムでは位数発見に、量子系のシミュレーションでは時間発展演算子の固有位相からエネルギーを推定するために使われます。Shorのアルゴリズムでは、モジュラー乗算に対応する制御U2kU^{2^k}ゲートを問題構造から構成できるため、UUを指数回反復する必要はありません。ハミルトニアンシミュレーションでも、ハミルトニアンの形やシミュレーション手法によっては、制御された時間発展を多項式程度のリソースで実装できる場合があります。そのため、QPEのリソースを見積もるときは、制御U2kU^{2^k}ゲートをUUの反復として数えるのか、直接合成した回路として数えるのか、あるいは問題固有の算術回路やシミュレーション回路として与えるのかを明示する必要があります。

  2. 初期状態の準備コスト

    QPEで特定の固有位相が得られる確率は、準備した状態と対応する固有状態との重なりの二乗で決まります。十分な重なりを持つ近似状態の準備には非自明な量子回路が必要になる場合があるため、実際の応用ではそのゲート数も別途見積もる必要があります。

まとめ

このノートブックでは、次のことを学びました。

  • QPEは、制御U2kU^{2^k}ゲートによる位相キックバックと逆QFTを使って、ユニタリ行列の固有位相を2進数として読み出します。

  • Qamomileでは、qmc.control、qmc.iqft、qmc.castを使ってQPEを構成でき、組み込みのqmc.qpeで同じ処理を簡潔に記述できます。

  • mm個のカウント用量子ビットによる位相分解能はO(2−m)O(2^{-m})ですが、必要なゲート数は制御U2kU^{2^k}ゲートの実装方法と初期状態の準備方法に依存します。

References
  1. Kitaev, A. Yu. (1995). Quantum measurements and the Abelian Stabilizer Problem. arXiv. 10.48550/ARXIV.QUANT-PH/9511026
  2. Cleve, R., Ekert, A., Macchiavello, C., & Mosca, M. (1998). Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969), 339–354. 10.1098/rspa.1998.0164
  3. Coppersmith, D. (2002). An approximate Fourier transform useful in quantum factoring. arXiv. 10.48550/ARXIV.QUANT-PH/0201067
  4. Nielsen, M. A., & Chuang, I. L. (2012). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. 10.1017/cbo9780511976667