量子チューリングマシン

量子チューリングマシン（QTM ）または汎用量子コンピュータは、量子コンピュータの効果をモデル化するために使用される抽象マシンです。これは、量子計算のすべてのパワーを捉えたシンプルなモデルを提供します。つまり、任意の量子アルゴリズムを特定の量子チューリングマシンとして形式的に表現できます。ただし、計算的に同等の量子回路の方が一般的なモデルです。^[1]^[2]^{: 2}

量子チューリングマシンは、遷移行列に基づく枠組みで古典的および確率的チューリングマシンと関連付けることができます。つまり、古典的または確率的マシンを表す行列との積が量子マシンを表す量子確率行列となるような行列を指定できます。これはランス・フォートナウによって示されました。^[3]

非公式スケッチ

物理学における未解決の問題:

汎用量子コンピュータは、任意の物理システムを効率的にシミュレートするのに十分でしょうか?

（物理学におけるさらなる未解決問題）

量子チューリングマシン（QTM）を理解する一つの方法は、量子有限オートマトン（QFA）が決定論的有限オートマトン（DFA）を一般化するのと同じように、古典的チューリングマシン（TM）を一般化することである。本質的には、古典的TMの内部状態は、ヒルベルト空間内の純粋状態または混合状態に置き換えられ、遷移関数は、ヒルベルト空間をそれ自体にマッピングするユニタリ行列の集合に置き換えられる。 ^[4]

つまり、古典的なチューリングマシンは 7組で記述されます。 $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$

3 テープ量子チューリングマシン (1 つのテープには入力が保持され、2 つ目のテープには中間計算結果が保持され、3 つ目のテープには出力が保持される) の場合:

状態の集合はヒルベルト空間に置き換えられます。 $Q$
テープのアルファベット記号も同様にヒルベルト空間 (通常は状態の集合とは異なるヒルベルト空間) に置き換えられます。 $\ガンマ$
空白記号はヒルベルト空間の要素です。 $b\in \Gamma$
入力シンボルと出力シンボルは、通常、古典システムの場合と同様に離散的なセットとして扱われます。したがって、量子マシンへの入力も出力も、量子システムそのものである必要はありません。 $\Sigma$
遷移関数は遷移モノイドの一般化であり、ヒルベルト空間の自己同型であるユニタリ行列の集合であると理解されています。 $\delta :\Sigma \times Q\otimes \Gamma \to \Sigma \times Q\otimes \Gamma \times \{L,R\}$ $Q$
初期状態は、混合状態または純粋状態のいずれかになります。 $q_{0}\in Q$
最終状態または受理状態の集合はヒルベルト空間のサブ空間です。 $F$ $Q$

上記は量子チューリングマシンの単なる概略であり、正式な定義ではありません。いくつかの重要な詳細が曖昧になっているためです。たとえば、測定が実行される頻度などです。たとえば、1 回測定の QFA と複数測定の QFA の違いを参照してください。この測定の問題は、出力テープへの書き込みが定義される方法に影響します。

歴史

1980年と1982年に、物理学者ポール・ベニオフは、チューリングマシンの量子力学モデルを初めて説明した論文^[5]^{[6]を発表しました。オックスフォード大学の物理学者}デビッド・ドイチュが1985年に書いた論文は、量子ゲートが従来のデジタルコンピューティングのバイナリロジックゲートと同様に機能する可能性があることを示唆し、量子コンピュータのアイデアをさらに発展させました。^[4]

入山、大谷、ヴォロヴィッチは線形量子チューリングマシン（LQTM）のモデルを開発した。これは混合状態を持ち、不可逆な遷移関数を可能にする古典的なQTMの一般化である。これにより、古典的な結果なしに量子測定を表現できる。^[7]

事後選択機能を備えた量子チューリングマシンはスコット・アーロンソンによって定義され、彼はそのようなマシン上の多項式時間のクラス（PostBQP ）が古典的な複雑性クラスPPに等しいことを示した。^[8]

参照

量子シミュレータ § 物理問題の解決

参考文献

^ Andrew Yao (1993).量子回路の複雑性. コンピュータサイエンスの基礎に関する第34回年次シンポジウム. pp. 352–361.
^ Abel Molina、John Watrous (2018)。「量子回路による量子チューリングマシンのシミュレーションの再検討」。Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences。475 ( 2226) 。arXiv : 1808.01701。doi : 10.1098 / rspa.2018.0767。PMC 6598068。PMID 31293355。
^ Fortnow, Lance (2003). 「ある複雑性理論家による量子コンピューティングの見方」.理論計算機科学. 292 (3): 597–610. arXiv : quant-ph/0003035 . doi :10.1016/S0304-3975(01)00377-2. S2CID 18657540.
^ ab Deutsch, David (1985 年 7 月). 「量子理論、チャーチ＝チューリング原理、そして汎用量子コンピュータ」(PDF) . Proceedings of the Royal Society A . 400 (1818): 97–117. Bibcode :1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382 . doi :10.1098/rspa.1985.0070. S2CID 1438116. 2008 年 11 月 23 日のオリジナル(PDF)からアーカイブ。
^ ベニオフ、ポール (1980)。「物理システムとしてのコンピュータ：チューリングマシンによって表されるコンピュータの微視的量子力学的ハミルトンモデル」。Journal of Statistical Physics。22 ( 5): 563–591。Bibcode : 1980JSP ....22..563B。doi : 10.1007/bf01011339。S2CID 122949592 。
^ Benioff, P. (1982). 「チューリングマシンの量子力学的ハミルトニアンモデル」. Journal of Statistical Physics . 29 (3): 515–546. Bibcode :1982JSP....29..515B. doi :10.1007/BF01342185. S2CID 14956017.
^ Simon Perdrix、Philippe Jorrand (2007-04-04)。「古典的に制御された量子計算」。Math . Struct. In Comp. Science . 16 (4): 601–620. arXiv : quant-ph/0407008 . doi :10.1017/S096012950600538X. S2CID 16142327.また、Simon Perdrix と Philippe Jorrand (2006)。「古典的に制御された量子計算」(PDF)。Math . Struct. In Comp. Science。16 ( 4 ): 601–620。arXiv : quant -ph/0407008。CiteSeerX 10.1.1.252.1823。doi : 10.1017 /S096012950600538X。S2CID 16142327 。
^ Aaronson, Scott (2005). 「量子コンピューティング、ポストセレクション、確率的多項式時間」Proceedings of the Royal Society A . 461 (2063): 3473–3482. arXiv : quant-ph/0412187 . Bibcode :2005RSPSA.461.3473A. doi :10.1098/rspa.2005.1546. S2CID 1770389.プレプリントは[1]から入手可能。

さらに読む

Molina, Abel; Watrous, John (2018). 「量子回路による量子チューリングマシンのシミュレーションの再検討」Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences . 475 (2226). arXiv : 1808.01701 . doi :10.1098/rspa.2018.0767. PMC 6598068 . PMID 31293355.
入山聡; 大谷正則; イゴールヴォロビッチ (2004)。「一般化量子チューリングマシンと SAT カオスアルゴリズムへの応用」。arXiv : quant-ph/0405191。
Deutsch, D. (1985). 「量子理論、チャーチ＝チューリング原理、そして万能量子コンピュータ」。ロンドン王立協会紀要。シリーズ A、数学および物理科学。400 (1818): 97–117。Bibcode :1985RSPSA.400...97D。CiteSeerX 10.1.1.41.2382。doi :10.1098/rspa.1985.0070。JSTOR 2397601。S2CID 1438116。

外部リンク

量子コンピュータ – 歴史

[equivalence-1] Andrew Yao (1993).量子回路の複雑性. コンピュータサイエンスの基礎に関する第34回年次シンポジウム. pp. 352–361.

[newequivalence-2] Abel Molina、John Watrous (2018)。「量子回路による量子チューリングマシンのシミュレーションの再検討」。Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences。475 ( 2226) 。arXiv : 1808.01701。doi : 10.1098 / rspa.2018.0767。PMC 6598068。PMID 31293355。

[transition-3] Fortnow, Lance (2003). 「ある複雑性理論家による量子コンピューティングの見方」.理論計算機科学. 292 (3): 597–610. arXiv : quant-ph/0003035 . doi :10.1016/S0304-3975(01)00377-2. S2CID 18657540.

[Deutsch1985-4] Deutsch, David (1985 年 7 月). 「量子理論、チャーチ＝チューリング原理、そして汎用量子コンピュータ」(PDF) . Proceedings of the Royal Society A . 400 (1818): 97–117. Bibcode :1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382 . doi :10.1098/rspa.1985.0070. S2CID 1438116. 2008 年 11 月 23 日のオリジナル(PDF)からアーカイブ。

[5] ベニオフ、ポール (1980)。「物理システムとしてのコンピュータ：チューリングマシンによって表されるコンピュータの微視的量子力学的ハミルトンモデル」。Journal of Statistical Physics。22 ( 5): 563–591。Bibcode : 1980JSP ....22..563B。doi : 10.1007/bf01011339。S2CID 122949592 。

[6] Benioff, P. (1982). 「チューリングマシンの量子力学的ハミルトニアンモデル」. Journal of Statistical Physics . 29 (3): 515–546. Bibcode :1982JSP....29..515B. doi :10.1007/BF01342185. S2CID 14956017.

[7] Simon Perdrix、Philippe Jorrand (2007-04-04)。「古典的に制御された量子計算」。Math . Struct. In Comp. Science . 16 (4): 601–620. arXiv : quant-ph/0407008 . doi :10.1017/S096012950600538X. S2CID 16142327.また、Simon Perdrix と Philippe Jorrand (2006)。「古典的に制御された量子計算」(PDF)。Math . Struct. In Comp. Science。16 ( 4 ): 601–620。arXiv : quant -ph/0407008。CiteSeerX 10.1.1.252.1823。doi : 10.1017 /S096012950600538X。S2CID 16142327 。

[8] Aaronson, Scott (2005). 「量子コンピューティング、ポストセレクション、確率的多項式時間」Proceedings of the Royal Society A . 461 (2063): 3473–3482. arXiv : quant-ph/0412187 . Bibcode :2005RSPSA.461.3473A. doi :10.1098/rspa.2005.1546. S2CID 1770389.プレプリントは[1]から入手可能。