量子有限オートマトン

量子コンピューティングにおいて、量子有限オートマトン( QFA ) または量子状態マシンは、確率オートマトンまたはマルコフ決定プロセスの量子アナログです。これらは、現実世界の量子コンピューターの数学的抽象化を提供します。測定 1 回オートマトンや測定多数オートマトンなど、いくつかの種類のオートマトンを定義できます。量子有限オートマトンはまた、有限タイプのサブシフトの量子化、またはマルコフ連鎖の量子化として理解することもできます。QFA は、幾何学的有限オートマトンまたは位相的有限オートマトンの特殊なケースです。

オートマトンの動作は、有限のアルファベットから有限の長さの文字列 を受け取り、各文字列に、オートマトンが受け入れ状態にある確率、つまり、オートマトンが文字列を受け入れたか拒否したかを示す確率を割り当てることによって行われます。 ${\displaystyle \sigma =(\sigma _{0},\sigma _{1},\cdots ,\sigma _{k})}$${\displaystyle \sigma_{i}}$ ${\displaystyle \Sigma }$ ${\displaystyle \operatorname {Pr} (\sigma )}$

QFA が受け入れる言語は、決定論的有限オートマトンの正規言語ではなく、確率的有限オートマトンの確率言語でもありません。これらの量子言語の研究は、現在も活発に行われています。

量子有限オートマトンを理解するには、単純で直感的な方法があります。まず、決定論的有限オートマトン(DFA) のグラフ理論的解釈から始めます。DFA は有向グラフとして表すことができ、状態はグラフのノード、矢印は状態遷移を表します。各矢印には可能な入力記号が付けられ、特定の状態と入力記号が与えられると、矢印は次の状態を指します。このようなグラフを表す 1 つの方法は、入力記号ごとに 1 つの行列を持つ隣接行列のセットを使用することです。この場合、可能な DFA 状態のリストは列ベクトルとして記述されます。隣接行列は、与えられた入力記号について、与えられた状態 (状態ベクトルの行) が次の状態にどのように遷移するかを示します。状態遷移は行列の乗算によって与えられます。

各入力シンボルは異なる遷移を引き起こす可能性があるため、各入力シンボルごとに異なる隣接行列が必要です。隣接行列のエントリは、0 と 1 でなければなりません。行列の任意の列について、非ゼロになるエントリは 1 つだけです。これは、次の (一意の) 状態遷移を示すエントリです。同様に、システムの状態は列ベクトルであり、非ゼロになるエントリは 1 つだけです。このエントリは、システムの現在の状態に対応します。入力シンボルの集合を とします。特定の入力シンボル について、DFA の次の状態への進化を記述する隣接行列 と記述します。すると、この集合は DFA の状態遷移関数を完全に記述します。DFAの可能な状態の集合をQとします。QにN個の状態がある場合、各行列はN x N次元になります。初期状態は、q ₀行目に 1 が含まれる列ベクトルに対応します。一般的な状態qは、 q'行目に 1 が含まれる列ベクトルです。表記法 の乱用により、q ₀とqもこれら 2 つのベクトルを表すものとします。次に、入力テープから入力シンボルを読み取った後、DFA の状態は次のように表されます。状態遷移は通常の行列乗算(つまり、q ₀をで乗算するなど) によって表されます。適用順序が「逆」になっているのは、線形代数の標準表記法 に従っているためです。 ${\displaystyle \Sigma }$${\displaystyle \alpha \in \Sigma }$${\displaystyle U_{\alpha}}$${\displaystyle \{U_{\alpha }|\alpha \in \Sigma \}}$${\displaystyle U_{\alpha}}$${\displaystyle q_{0}\in Q}$${\displaystyle \alpha \beta \gamma \cdots }$${\displaystyle q=\cdots U_{\gamma }U_{\beta }U_{\alpha }q_{0}.}$${\displaystyle U_{\alpha}}$

線形演算子とベクトルに関する上記の DFA の説明は、状態ベクトルq を何らかの一般的なベクトルに、行列を何らかの一般的な演算子に置き換えることによって、ほぼ一般化を必要とします。これは基本的に QFA が行うことです。つまり、q を単位ベクトルに、 をユニタリ行列に置き換えます。他の同様の一般化も明らかになります。ベクトルq は多様体上の何らかの分布になることができ、遷移行列の集合は多様体の自己同型になり、これにより位相有限オートマトンが定義されます。同様に、行列は同次空間の自己同型としてとらえることができ、これにより幾何学的有限オートマトンが定義されます。 ${\displaystyle \{U_{\alpha }\}}$${\displaystyle \{U_{\alpha }\}}$

QFA の正式な説明に進む前に、言及して理解しておくべき 2 つの注目すべき一般化があります。1 つ目は、 非決定性有限オートマトン(NFA) です。この場合、ベクトルq は、ゼロ以外の複数のエントリを持つことができるベクトルに置き換えられます。このようなベクトルは、Qのべき集合の要素を表します。これは、 Qの単なるインジケータ関数です。同様に、状態遷移行列は、特定の列に複数のゼロ以外のエントリを含めることができるように定義されます。同様に、成分ごとの行列乗算中に実行される乗算と加算の演算は、ブールの and-or 演算に置き換える必要があります。つまり、特性 2のリングで作業することになります。 ${\displaystyle \{U_{\alpha }\}}$

よく知られている定理によれば、各 DFA には同等の NFA が存在し、その逆もまた同様です。これは、DFA と NFA が認識できる言語のセットが同じであることを意味します。これらは正規言語です。QFA への一般化では、認識される言語のセットは異なります。そのセットを記述することは、QFA 理論における未解決の研究課題の 1 つです。

すぐにわかるもう 1 つの一般化は、遷移行列に確率行列を使用し、状態に確率ベクトルを使用することです。これにより、確率有限オートマトンが得られます。状態ベクトルが確率として解釈されるためには、状態ベクトルのエントリは、実数、正、および合計が 1 でなければなりません。遷移行列はこの特性を維持する必要があります。これが、遷移行列が確率的でなければならない理由です。各状態ベクトルは、単体内の点を指定するものとして想像する必要があります。したがって、これは位相オートマトンであり、単体は多様体であり、確率行列は単体のそれ自体への線形自己同型です。各遷移は (本質的に) 前の遷移から独立しているため (受け入れられた言語と拒否された言語の区別を無視する場合)、PFA は本質的に一種のマルコフ連鎖になります。

対照的に、QFA では、多様体は複素射影空間 であり、遷移行列はユニタリ行列です。 内の各点は(純粋な)量子力学的状態に対応します。ユニタリ行列は、システムの時間発展 (つまり、シュレーディンガー図)を支配するものと考えることができます。純粋状態から混合状態への一般化は簡単です。混合状態は、上の測度論的確率分布にすぎません。 ${\displaystyle \mathbb {C} P^{N}}$${\displaystyle \mathbb {C} P^{N}}$ ${\displaystyle \mathbb {C} P^{N}}$

熟考する価値のある点は、言語の入力中に多様体上に生じる分布です。オートマトンが言語を「効率的に」認識するには、その分布が「可能な限り均一」である必要があります。この均一性の必要性は、最大エントロピー法の背後にある基本原理です。これらの方法は、オートマトンが明瞭かつコンパクトに動作することを保証します。言い換えると、隠れマルコフ モデルのトレーニングに使用される機械学習方法は、QFA にも一般化されます。つまり、ビタビ アルゴリズムと順方向-逆方向アルゴリズムは、 QFA に簡単に一般化されます。

QFAの研究は1997年のコンダックスとワトラウスの研究^[1]とその後のムーアとクラッチフェルド^[2]によって普及したが、 1971年にはイオン・バイアヌによってすでに記述されていた。^{[3] [4]}

一度測定オートマトン(Measure-once Automaton)はクリス・ムーアとジェームズ・P・クラッチフィールドによって導入された。^[2]それらは以下のように正式に定義される。

通常の有限オートマトンと同様に、量子オートマトンには可能な内部状態があると考えられており、この場合は-状態量子ドットで表されます。より正確には、-状態量子ドットは-次元複素射影空間の要素であり、内積がフビニ・スタディ計量であるものです。 ${\displaystyle N}$${\displaystyle N}$ ${\displaystyle |\psi \rangle }$${\displaystyle N}$${\displaystyle |\psi \rangle \in P(\mathbb {C} ^{N})}$${\displaystyle (N-1)}$ ${\displaystyle \Vert \cdot \Vert }$

状態遷移、遷移行列、またはde Bruijn グラフは、文字ごとに 1 つのユニタリ行列を持つユニタリ行列の集合によって表されます。つまり、入力文字が与えられると、ユニタリ行列はオートマトンが現在の状態から次の状態へ遷移する様子を表します。 ${\displaystyle N\times N}$ ${\displaystyle U_{\alpha}}$${\displaystyle \alpha \in \Sigma }$${\displaystyle \alpha}$${\displaystyle |\psi \rangle }$${\displaystyle |\psi ^{\prime }\rangle }$

${\displaystyle |\psi ^{\prime }\rangle =U_{\alpha }|\psi \rangle }$

したがって、この三つ組は量子半オートマトンを形成します。 ${\displaystyle (P(\mathbb {C} ^{N}),\Sigma ,\{U_{\alpha }\;\vert \;\alpha \in \Sigma \})}$

オートマトンの受理状態は射影行列で与えられるので、次元量子状態が与えられた場合、受理状態にある 確率は${\displaystyle N\times N}$ ${\displaystyle P}$${\displaystyle N}$${\displaystyle |\psi \rangle }$${\displaystyle |\psi \rangle }$

${\displaystyle \langle \psi |P|\psi \rangle =\Vert P|\psi \rangle \Vert ^{2}}$

状態マシンが与えられた有限入力文字列を受け入れる確率は次のように与えられる。 ${\displaystyle \sigma =(\sigma _{0},\sigma _{1},\cdots ,\sigma _{k})}$

${\displaystyle \operatorname {Pr} (\sigma )=\Vert PU_{\sigma _{k}}\cdots U_{\sigma _{1}}U_{\sigma _{0}}|\psi \rangle \Vert ^{2}}$

ここで、ベクトルはオートマトンの初期状態、つまり文字列入力を受け付ける前のオートマトンの状態を表すものと理解される。空の文字列は単位行列であると理解されるので、 ${\displaystyle |\psi \rangle }$${\displaystyle \varnothing }$

${\displaystyle \operatorname {Pr} (\varnothing )=\Vert P|\psi \rangle \Vert ^{2}}$

初期状態が受け入れられた状態である確率にすぎません。

に対するの左アクションは文字列 内の文字の順序を逆にするため、文字の順序を同じに保つためだけに、 エルミート転置状態に対する右アクションを使用して QFA を定義することは珍しくありません。${\displaystyle U_{\alpha}}$${\displaystyle |\psi \rangle }$${\displaystyle \sigma}$

アルファベット上の言語は、その言語のすべての文に対して が成り立つ場合、量子有限オートマトン (および与えられた固定された初期状態 ) によって確率的に受け入れられます。 ${\displaystyle \Sigma }$${\displaystyle p}$${\displaystyle |\psi \rangle }$${\displaystyle \sigma}$${\displaystyle p\leq \operatorname {Pr} (\sigma )}$

状態遷移表によって与えられる古典的な決定論的有限オートマトンを考える。

量子状態はベクトルであり、ブラケット記法で表すと

${\displaystyle |\psi \rangle =a_{1}|S_{1}\rangle +a_{2}|S_{2}\rangle ={\begin{bmatrix}a_{1}\\a_{2}\end{bmatrix}}}$

複素数 は正規化されて ${\displaystyle a_{1},a_{2}}$

${\displaystyle {\begin{bmatrix}a_{1}^{*}\;\;a_{2}^{*}\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\end{bmatrix}}=a_{1}^{*}a_{1}+a_{2}^{*}a_{2}=1}$

ユニタリー遷移行列は

${\displaystyle U_{0}={\begin{bmatrix}0&1\\1&0\end{bmatrix}}}$

そして

${\displaystyle U_{1}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}}$

を受理状態と すると、射影行列は${\displaystyle S_{1}}$

${\displaystyle P={\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$

明らかなように、初期状態が純粋状態またはの場合、マシンを実行した結果は、古典的な決定論的有限状態マシンとまったく同じになります。特に、これらの初期状態に対して、このオートマトンによって確率 1 で受け入れられる言語があり、これは古典的な DFA の正規言語と同じであり、正規表現で与えられます。 ${\displaystyle |S_{1}\rangle }$${\displaystyle |S_{2}\rangle }$

${\displaystyle (1^{*}(01^{*}0)^{*})^{*}\,\!}$

非古典的な動作は、 と が両方ともゼロでない場合発生します。行列 とがそれほど単純でない場合、より微妙な動作が発生します。たとえば、すべての可能な有限バイナリ文字列のセットに作用する量子有限状態マシンの例として 、 de Rham 曲線を参照してください。${\displaystyle a_{1}}$${\displaystyle a_{2}}$${\displaystyle U_{0}}$${\displaystyle U_{1}}$

測定多数オートマトンが1997年にKondacsとWatrousによって導入されました。^[1]一般的なフレームワークは測定1回オートマトンに似ていますが、最後に1つの投影があるのではなく、各文字が読み取られた後に投影、つまり量子測定が実行される点が異なります。正式な定義は次のとおりです。

ヒルベルト空間は3つの 直交部分空間に分解される。${\displaystyle {\mathcal {H}}_{Q}}$

${\displaystyle {\mathcal {H}}_{Q}={\mathcal {H}}_{\text{accept}}\oplus {\mathcal {H}}_{\text{reject}}\oplus {\mathcal {H}}_{\text{non-halting}}}$

文献では、これらの直交部分空間は通常、ヒルベルト空間の直交基底ベクトルの集合によって定式化される。この基底ベクトルの集合は、 部分集合とに分割され、${\displaystyle Q}$${\displaystyle {\mathcal {H}}_{Q}}$${\displaystyle Q_{\text{acc}}\subseteq Q}$${\displaystyle Q_{\text{rej}}\subseteq Q}$

${\displaystyle {\mathcal {H}}_{\text{accept}}=\operatorname {span} \{|q\rangle :|q\rangle \in Q_{\text{acc}}\}}$

は、受け入れセット内の基底ベクトルの線形スパンです。拒否空間も同様に定義され、残りの空間は非停止部分空間と呼ばれます。それぞれの部分空間に投影される 3 つの投影行列、、 およびがあります。 ${\displaystyle P_{\text{acc}}}$${\displaystyle P_{\text{rej}}}$${\displaystyle P_{\text{non}}}$

${\displaystyle P_{\text{acc}}:{\mathcal {H}}_{Q}\to {\mathcal {H}}_{\text{accept}}}$

など。入力文字列の解析は次のように進行する。オートマトンが状態にあるとしよう。入力文字を読み取った後、オートマトンは次の状態になる。 ${\displaystyle |\psi \rangle }$${\displaystyle \alpha }$

${\displaystyle |\psi ^{\prime }\rangle =U_{\alpha }|\psi \rangle }$

この時点で、3つの可能な結果が固有空間、、を持つ測定が状態 に対して実行され、その時点でその波動関数は3つの部分空間またはまたは のいずれかに崩壊します。「受け入れ」部分空間への崩壊の確率は次のように与えられます。 ${\displaystyle {\mathcal {H}}_{\text{accept}}}$${\displaystyle {\mathcal {H}}_{\text{reject}}}$${\displaystyle {\mathcal {H}}_{\text{non-halting}}}$${\displaystyle |\psi ^{\prime }\rangle }$${\displaystyle {\mathcal {H}}_{\text{accept}}}$${\displaystyle {\mathcal {H}}_{\text{reject}}}$${\displaystyle {\mathcal {H}}_{\text{non-halting}}}$

${\displaystyle \operatorname {Pr} _{\text{acc}}(\sigma )=\Vert P_{\text{acc}}|\psi ^{\prime }\rangle \Vert ^{2},}$

他の 2 つのスペースについても同様です。

波動関数が「受け入れ」または「拒否」サブスペースのいずれかに収束した場合、それ以上の処理は停止します。それ以外の場合は、処理が続行され、入力から次の文字が読み取られ、 の固有状態であるはずのものに適用されます。処理は、文字列全体が読み取られるか、マシンが停止するまで続行されます。多くの場合、追加の記号と $ がアルファベットに付加され、文字列の左端と右端のマーカーとして機能します。 ${\displaystyle P_{\text{non}}}$${\displaystyle \kappa }$

文献では、測度多オートマトンを組 で表すことが多い。ここで、、、は上で定義したとおりである。初期状態は で表す。ユニタリ変換は写像 で表す。 ${\displaystyle (Q;\Sigma ;\delta ;q_{0};Q_{\text{acc}};Q_{\text{rej}})}$${\displaystyle Q}$${\displaystyle \Sigma }$${\displaystyle Q_{\text{acc}}}$${\displaystyle Q_{\text{rej}}}$${\displaystyle |q_{0}\rangle }$${\displaystyle \delta }$

${\displaystyle \delta :Q\times \Sigma \times Q\to \mathbb {C} }$

となることによって

${\displaystyle U_{\alpha }|q_{i}\rangle =\sum _{q_{j}\in Q}\delta (q_{i},\alpha ,q_{j})|q_{j}\rangle }$

2019 年現在、ほとんどの量子コンピュータは1 回測定の量子有限オートマトン の実装であり、それらをプログラミングするためのソフトウェア システムは、 の状態準備、測定、および制御 NOT ゲート、アダマール変換、その他の量子論理ゲートなどのユニタリ変換の選択をプログラマーに直接公開しています。 ${\displaystyle |\psi \rangle }$${\displaystyle P}$${\displaystyle U_{\alpha }}$

現実世界の量子コンピュータと上記の理論的枠組みとの主な違いは、初期状態の準備では点状の純粋状態になることはなく、ユニタリー演算子を正確に適用することもできないことです。したがって、初期状態は混合状態としてとらえなければなりません。

${\displaystyle \rho =\int p(x)|\psi _{x}\rangle dx}$

機械が望ましい初期純粋状態に近い初期状態を準備する能力を特徴付ける確率分布。この状態は安定ではなく、時間の経過とともにある程度の量子デコヒーレンスが発生する。正確な測定も不可能であり、代わりに測定プロセスを記述するために正の演算子値測定を使用する。最後に、各ユニタリ変換は単一の明確に定義された量子論理ゲートではなく、むしろ混合である。 ${\displaystyle p(x)}$${\displaystyle |\psi \rangle }$

${\displaystyle U_{\alpha ,(\rho )}=\int p_{\alpha }(x)U_{\alpha ,x}dx}$

機械がどの程度うまく目的の変換を実現できるかを表す確率分布。 ${\displaystyle p_{\alpha }(x)}$${\displaystyle U_{\alpha }}$

これらの効果の結果として、状態の実際の時間発展は、任意の鋭い変換のシーケンスによって操作される無限精度の純粋な点としてではなく、エルゴード過程、より正確には、変換を状態に連結するだけでなく、時間の経過とともに状態をぼかす 混合過程としてとらえることができます。

プッシュダウンオートマトンやスタックマシンに類似した量子マシンは存在しません。これは、クローンなし定理によるものです。つまり、マシンの現在の状態のコピーを作成し、後で参照できるようにスタックにプッシュして、そのスタックに戻ることはできません。

上記の構成は、量子有限オートマトンの概念を、任意の位相空間に一般化する方法を示しています。たとえば、 の代わりに ( N次元)リーマン対称空間を使用できます。ユニタリ行列の代わりに、リーマン多様体の等長変換、またはより一般的には、特定の位相空間に適した開関数の集合を使用します。初期状態は、空間内の点とすることができます。受理状態の集合は、位相空間の任意の部分集合とすることができます。同相写像による反復の後、点が受理集合と交差する場合、形式言語はこの位相オートマトンによって受理されると言えます。しかし、もちろん、これはM オートマトンの標準的な定義に過ぎません。位相オートマトンの動作は、位相力学の分野で研究されています。 ${\displaystyle \mathbb {C} P^{N}}$

量子オートマトンが位相オートマトンと異なるのは、2 値の結果 (反復された点が最終セット内にあるか、それとも含まれていないか) ではなく、確率を持つ点です。量子確率は、初期状態 (の 2 乗) を何らかの最終状態Pに投影したもので、つまり です。しかし、この確率振幅は、フビニ–スタディ メトリックによって与えられる距離メトリックの下で、内の点と点の間の距離の非常に単純な関数にすぎません。要約すると、言語が受け入れられる量子確率はメトリックとして解釈でき、初期状態と最終状態の間のメトリック距離がゼロの場合、受け入れ確率は 1 になり、メトリック距離がゼロでない場合、受け入れ確率は 1 未満になります。したがって、量子有限オートマトンとは、何らかのメトリック空間に一般化された幾何学オートマトンまたはメトリック オートマトンの特殊なケースにすぎず、確率測度はその空間上のメトリック の単純な関数に置き換えられます。 ${\displaystyle \mathbf {Pr} =\vert \langle P\vert \psi \rangle \vert ^{2}}$${\displaystyle \vert P\rangle }$${\displaystyle \vert \psi \rangle }$${\displaystyle \mathbb {C} P^{N}}$${\displaystyle \mathbb {C} P^{N}}$

• 量子マルコフ連鎖
• ブルーム・シューブ・スメール機械
• 本物のコンピュータ