量子ウォーク探索

量子コンピューティングの文脈では、量子ウォーク探索はグラフ内のマークされたノードを見つけるための量子アルゴリズムです。 ^[1]

量子ウォークの概念は、グラフや格子上を歩行者がランダムに移動する古典的なランダムウォークにヒントを得たものです。古典的なランダムウォークでは、歩行者の位置はグラフの異なるノード上の確率分布を使用して記述できます。一方、量子ウォークでは、歩行者は量子状態によって表され、同時に複数の位置の重ね合わせ状態になることができます。 ^[1]

量子ウォークに基づく探索アルゴリズムは、最適化、機械学習、暗号化、ネットワーク分析など、さまざまな分野で応用できる可能性があります。^[2]量子ウォーク探索の効率と成功確率は、探索空間の構造に大きく依存します。一般に、量子ウォーク探索アルゴリズムは、グローバーのアルゴリズムと同様の漸近的な二次の高速化を提供します。^{[3] [4]}

量子ウォークを探索問題に応用した最初の研究の一つは、ニール・シェンヴィ、ジュリア・ケンペ、K・ビルギッタ・ホエリーによって提案された。^[5]

探索空間とマークされた要素を含むサブセットが与えられた場合、確率的探索アルゴリズムは、からマークされた要素が見つかるまで、各ステップで要素を均一にランダムにサンプリングします。をマークされた要素の割合として定義すると、マークされた要素を見つけるには、その種の手順を 回繰り返す必要があります。^[6]${\displaystyle X}$${\displaystyle M\subseteq X}$${\displaystyle x\in X}$${\displaystyle M}$${\displaystyle \epsilon =|M|/|N|}$${\displaystyle O(1/\epsilon )}$

の構造に関する情報があれば、それをグラフとしてモデル化することができます。ここで、各頂点はの探索空間からのサンプルを表し、辺は現在のサンプルから始まって次の要素をサンプリングする条件付き確率を表します。^[6]${\displaystyle X}$${\displaystyle G(V,E)}$${\displaystyle V=\{v_{1},\dots ,v_{n}\}}$${\displaystyle |X|=n}$

ランダムな頂点から始めて検索を実行し、それが に属していない場合は、に接続されている頂点の中から次の頂点をサンプリングします。この手順はランダムウォーク検索として知られています。マークされたノードを見つける確率を に近づけるには、グラフ上で漸近的にステップを踏む必要があります 。ここで、パラメータはグラフの確率行列に関連付けられたスペクトルギャップです。 ^[7]${\displaystyle v_{1}}$${\displaystyle M}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle 1}$${\displaystyle O(1/\epsilon \delta )}$${\displaystyle \delta}$ ${\displaystyle P}$

ランダムウォークアルゴリズムの計算コストを評価するには、通常、手順をセットアップ、チェック、更新などの3つのサブフェーズに分割し、それぞれのコストを分析します。^[6]

設定

セットアップコストはグラフの頂点上の定常分布の初期化を指します。 ^[6]${\displaystyle S}$

アップデート

更新コストは、グラフ上の遷移を^[6]で定義された遷移確率に従ってシミュレートするためのコストである。${\displaystyle U}$${\displaystyle P}$

チェック

チェックコストは、現在の要素が集合に属しているかどうかを確認するためのコストである。^[6]${\displaystyle C}$${\displaystyle M}$

ランダムウォーク探索アルゴリズムの総コストは です。グラフ上の各ステップの後にチェックを実行するアルゴリズムの貪欲バージョンの複雑度は です。コスト定式化におけるスペクトルギャップ項の存在は、ウォーカーが定常分布に到達するために実行する必要がある最小ステップ数と考えることができます。この量は混合時間とも呼ばれます。^[8]${\displaystyle S+{\frac {1}{\epsilon }}{\biggl (}{\frac {1}{\delta }}U+C{\biggr )}}$${\displaystyle S+{\frac {1}{\epsilon \delta }}{\biggl (}U+C{\biggr )}}$${\displaystyle \delta}$

量子ウォーク探索アルゴリズムは、Magniezら^[7]によって最初に提案され、MNRSアルゴリズムとしても知られ、Mario Szegedyによって提案された量子ウォーク定式化に基づいています。ウォークはグラフの有向辺上で実行されるため、探索空間に関連付けられた量子状態を表すには、からへの辺に対応する2つの量子レジスタが 必要です。動作を簡単に理解するために、アルゴリズムは幾何学的解釈によって説明できます。まず、を の近傍上の均一な重ね合わせとして定義します。さらに、マークされた状態とマークされていない状態（多くの場合、良い状態と悪い状態と呼ばれる）の重ね合わせを次のように定義します。 ${\displaystyle |i\rangle |j\rangle }$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle |p_{i}\rangle =\sum _{j}{\sqrt {P_{ij}}}|j\rangle }$${\displaystyle |i\rangle}$

${\displaystyle |G\rangle ={\frac {1}{\sqrt {|M|}}}\sum _{i\in M}|i\rangle |p_{i}\rangle }$そして${\displaystyle |B\rangle ={\frac {1}{\sqrt {X-|M|}}}\sum _{i\not \in M}|i\rangle |p_{i}\rangle }$

ここで、はマークされた要素の集合です。すべてのエッジにわたる均一な重ね合わせは、良い状態と悪い状態の組み合わせとして見ることができます。 ${\displaystyle M}$${\displaystyle U}$

${\displaystyle |U\rangle ={\frac {1}{\sqrt {X}}}\sum _{i\in X}|i\rangle |p_{i}\rangle =\sin(\theta )|G\rangle +\cos(\theta )|B\rangle }$と。^[9]${\displaystyle \theta =\arcsin({\sqrt {\epsilon }})}$

アルゴリズムは次のステップで構成されています。

1. 量子状態を で初期化します。これは通常、何らかの状態準備ルーチンによって行われます。${\displaystyle |U\rangle}$
2. 以下を繰り返します: ${\displaystyle O(1/{\sqrt {\epsilon }})}$
   • 反省する${\displaystyle |B\rangle }$
   • 反省する${\displaystyle |U\rangle}$
3. 最初の量子レジスタを測定し、マークされているかどうかを確認します

アルゴリズムがマークされた要素を見つける方法は振幅増幅技術に基づいているため、^[10]正しさの証明はグローバーのアルゴリズムの証明に似ています（これは、完全に接続されたグラフ 上の量子ウォークの特殊なケースと見ることもできます）。 と を通る 2 つの反射は、量子状態を良好な状態に向かって動かす効果を示します。反射を適用した後、状態は と表すことができ 、 を設定すると、高い確率で良好な状態を生み出す が得られます。 ^[9]${\displaystyle |U\rangle}$${\displaystyle |B\rangle }$${\displaystyle k}$${\displaystyle \sin((2k+1)\theta )|G\rangle +\cos((2k+1)\theta )|B\rangle }$${\displaystyle k\thickapprox {\frac {\pi }{4\theta }}=O(1/{\sqrt {\epsilon }})}$${\displaystyle \sin((2k+1)\theta )\thickapprox 1}$

最初の反省

最初の反射は、現在の頂点がマークされているかどうかを確認し、マークされている場合は に等しい位相シフトを適用する効果があります。これは、振幅増幅に基づく多くの量子アルゴリズムで一般的な手順であり、条件を検証する量子オラクル関数を通じて実現できます。^[9]${\displaystyle -1}$${\displaystyle |i\rangle \in M}$

2回目の反省

2 番目の反射は、探索しているグラフの構造を反映しているウォーク演算子上の量子位相推定で実装されます。ウォーク演算子は と定義できます。ここで、 と は、サブスペースと を通る 2 つの反射です。^[9]の固有値はの形式上にあり、演算子はによって与えられるに対応する に等しい一意の固有値を持つため、一意の固有値を見つけるために精度で位相推定を実行できます。反射の精度は、位相を推定するために使用される量子ビットの数によって異なります。 ^[9] ${\displaystyle W}$${\displaystyle W=ref({\mathcal {B}})ref({\mathcal {A}})}$${\displaystyle ref({\mathcal {B}})}$${\displaystyle ref({\mathcal {A}})}$ ${\displaystyle {\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}}$${\displaystyle {\mathcal {B}}=span\{|p_{j}\rangle ,|j\rangle \}}$${\displaystyle W}$${\displaystyle e^{\pm 2i\theta }}$${\displaystyle 1}$${\displaystyle |U\rangle}$${\displaystyle \theta =0}$${\displaystyle O(1/{\sqrt {\delta }})}$

複雑

古典的なランダムウォークアルゴリズムのコストを推定するために使用されるのと同じ形式を使用して、量子コストは次のように要約できます。

• S: 重ね合わせを初期化するためのコスト${\displaystyle |U\rangle}$
• U: 重ね合わせ、つまり反射を通してグラフ上のステップを実行するコストです。${\displaystyle |U\rangle}$
• C: 量子オラクルを実装するためのコスト、つまり反射を介して${\displaystyle |B\rangle }$

量子ウォーク探索の総コストは であり、これは古典的なバージョンと比較して2乗の速度向上をもたらす。グローバーのアルゴリズムと比較すると、量子ウォークは各量子状態に関連付けられた大規模なデータ構造がある場合に有利になる。これは、前者の場合、各反復でデータ構造が完全に再構築されるのに対し、量子ウォークでは各ステップで部分的にしか更新されないためである。^[11]${\displaystyle S+{\frac {1}{\sqrt {\epsilon }}}{\biggl (}{\frac {1}{\sqrt {\delta }}}U+C{\biggr )}}$

これはハイパーキューブグラフに量子ウォーク探索を適用する例です。^[12]

元の記述ではセゲディ量子ウォークが使われていますが、この例ではより直感的に理解しやすいように造語された量子ウォークを使用しています。いずれにせよ、2つの形式化は特定の仮定の下では同等であることがわかります。^[13]

探索空間は の-超立方体で、頂点があり、次数はです。各ノードはビットのバイナリ文字列でラベル付けでき、2 つのノードはハミング距離が である場合にエッジで接続されます。量子ウォーク探索を設定するには、ウォーカーが選択できるすべての可能な方向をエンコードするための 次元のコインレジスタと、頂点を表す次元の頂点レジスタが必要です。 ^[12]${\displaystyle n}$${\displaystyle n=4}$${\displaystyle |V|=2^{4}}$${\displaystyle 4}$${\displaystyle v_{i}}$${\displaystyle 4}$${\displaystyle 1}$${\displaystyle {\mathcal {H}}^{n}}$${\displaystyle {\mathcal {H}}^{2^{n}}}$

計算の基礎はです。 ${\displaystyle |d\rangle |v\rangle }$${\displaystyle \{d\in D=\{00,01,10,11\},v\in V=\{0000,0001,\dots ,1111\}\}}$

ウォークは 2 人のオペレーターによって実行されます。

• コイン演算子は、可能な方向の重ね合わせを作成するために使用されます。${\displaystyle C}$
• シフト演算子は、グラフを一方向に移動するために使用されます。${\displaystyle S}$

したがって、ウォーク演算子はである。^[12]${\displaystyle W=SC}$

ハイパーキューブ グラフの場合、隣接するノードの頂点のバイナリ エンコーディングが 1 ビットだけ異なるという事実を利用して、効率的なシフト演算子を構築できます。シフト演算子は次のように記述できます。

${\displaystyle S=\sum _{d=1}^{n}\sum _{v=1}^{n}|d\rangle |v\oplus e_{d}\rangle \langle d|\langle v |}$

ここで は超立方体の -基底です(基底が の場合)。コインにはグローバーコインやフーリエコインなど複数の選択肢がありますが、すべての方向で等しい重ね合わせを持つグローバーコインを選ぶことができます。^[12]${\displaystyle e_{d}}$${\displaystyle d}$${\displaystyle n=4}$${\displaystyle \{0001,0010,0100,1000\}}$

アルゴリズムは次のように動作します。

1. 繰り返し${\displaystyle O(1/{\sqrt {\epsilon }})}$
   • 重ね合わせの位相のカウントレジスタを初期化する
   • 位相推定を正確に実行する${\displaystyle W}$${\displaystyle O(1/{\sqrt {\delta }})}$
   • 推定位相が${\displaystyle {\tilde {\theta }}=0}$
   • 計算されない補助データ構造
2. 頂点レジスタを測定する

シフト演算子は効率的な量子ウォークの実装に重要な要素であるが、トロイドや格子などの特定のグラフファミリーではシフトは既知であるが、非正規グラフでは効果的なシフト演算子の設計は依然として未解決の課題である。^[14]

以下の応用はジョンソングラフ 上の量子ウォークに基づいています。^[15]${\displaystyle J(n,k)}$

要素の明確さ

上で定義された関数が与えられたとき、2つの異なる要素を見つけるように求められます。そのようなペアが存在する場合。^[16]${\displaystyle f}$${\displaystyle \{n\}}$${\displaystyle i,j\in \{n\}}$${\displaystyle f(i)=f(j)}$

マトリックス製品検証

3つの行列とが与えられたとき、 であるかどうかを検証するか、 であるようなインデックスを見つけるかという問題です。^[6]${\displaystyle n\times n}$${\displaystyle A,B}$${\displaystyle C}$${\displaystyle AB=C}$${\displaystyle i,j}$${\displaystyle (AB)_{i,j}\neq C_{i,j}}$

三角形

三角形は、無向グラフの3つの頂点上の完全な部分グラフです。グラフの隣接行列が与えられた場合、三角形が存在するかどうかを見つける問題です。^[6]${\displaystyle G}$

• グローバーのアルゴリズム
• 量子位相推定
• 量子ウォーク
• ランダムウォーク

• ニールセン、マイケル A.、チュアン、アイザック L. (2010)。量子計算と量子情報（10周年記念版）。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-1-107-00217-3。
• Lawler, Gregory F.; Limic, Vlada (2010)。ランダムウォーク：現代的入門。ケンブリッジ高等数学研究。ケンブリッジ：ケンブリッジ大学出版局。doi : 10.1017 / cbo9780511750854。ISBN 978-0-521-51918-2。
• Hidary, Jack D. (2019).量子コンピューティング: 応用アプローチ. シャム、スイス: Springer. ISBN 978-3-030-23921-3。

• 量子ウォーク
• サイクルグラフ上の量子ウォークの実装
• 近未来の量子コンピュータにおける量子ウォークの研究