量子チューリングマシン

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

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

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

つまり、古典的なチューリングマシンは7タプルで記述される。${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$このタプルに含まれる各要素についてより深く理解するには、チューリングマシンの正式な定義を参照してください。

3本のテープを使用する量子チューリングマシン（1本目のテープには入力、2本目のテープには中間計算結果、3本目のテープには出力が格納される）の場合：

• 状態の集合${\displaystyle Q}$はヒルベルト空間に置き換えられます。
• テープのアルファベット記号${\displaystyle \Gamma }$同様に、ヒルベルト空間（通常は状態の集合とは異なるヒルベルト空間）に置き換えられます。
• 空白の記号${\displaystyle b\in \Gamma }$はヒルベルト空間の要素である。
• 入力記号と出力記号${\displaystyle \Sigma }$これらは通常、古典システムと同様に離散的な集合として扱われるため、量子マシンへの入力も出力も、それ自体が量子システムである必要はない。
• 遷移関数${\displaystyle \delta$ \Sigma \times Q\otimes \Gamma \to \Sigma \times Q\otimes \Gamma \times \{L,R\}} は 半​​オートマトンを一般化したものでヒルベルト空間の自己同型であるユニタリ行列の集合として理解される。${\displaystyle Q}$。
• 初期状態${\displaystyle q_{0}\in Q}$混合状態または純粋状態のいずれかである可能性がある。
• セット${\displaystyle F}$最終状態または受理状態の空間は、ヒルベルト空間の線形部分空間である。${\displaystyle Q}$。

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

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

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

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

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

• 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). "量子論、チャーチ＝チューリング原理、および汎用量子コンピュータ". Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences . 400 (1818): 97–117 . Bibcode : 1985RSPSA.400...97D . CiteSeerX 10.1.1.41.2382 . doi : 10.1098/rspa.1985.0070 . JSTOR 2397601 . S2CID 1438116 .   

• 量子コンピュータの歴史