量子複雑性理論

量子複雑性理論は、量子力学に基づいた計算モデルである量子コンピュータを用いて定義される複雑性クラスを扱う、計算複雑性理論の下位分野である。この分野では、これらの複雑性クラスに関連する計算問題の難しさ、および量子複雑性クラスと古典的（すなわち非量子的）複雑性クラスとの関係を研究する。

量子複雑性に関する重要なクラスとして、BQPとQMAの2つが挙げられる。

複雑性クラスとは、特定の資源制約の下で計算モデルによって解決できる計算問題の集合のことです。例えば、複雑性クラスP は、（決定論的）チューリングマシンによって多項式時間で解決できる問題の集合として定義されます。同様に、量子複雑性クラスは、量子回路モデルやそれに相当する量子チューリングマシンなどの量子計算モデルを用いて定義できます。量子複雑性理論の主な目的の一つは、これらのクラスがP、NP、BPP、PSPACEなどの古典的な複雑性クラスとどのように関連しているかを明らかにすることです。

量子複雑性理論が研究されている理由の 1 つは、量子コンピューティングが現代のチャーチ・チューリングのテーゼに与える影響です。簡単に言うと、現代のチャーチ・チューリングのテーゼは、任意の計算モデルは確率的チューリングマシンで多項式時間でシミュレートできると述べています。^{[ 1 ] [ 2 ]}しかし、量子コンピューティングの文脈では、チャーチ・チューリングのテーゼに関する疑問が生じます。チャーチ・チューリングのテーゼが量子計算モデルにも当てはまるかどうかは不明です。テーゼが当てはまらないという証拠は多数あります。確率的チューリングマシンが量子計算モデルを多項式時間でシミュレートすることは不可能かもしれません。^{[ 1 ]}

量子アルゴリズムと古典アルゴリズムの両方の漸近的な計算複雑度は、しばしば漸近記法で表現されます。関数の漸近記法の一般的な形式には、次のようなものがあります。${\displaystyle O(T(n))}$、${\displaystyle \Omega (T(n))}$、 そして$\displaystyle \Theta (T(n))$。${\displaystyle O(T(n))}$何かが上から制限されていることを表す${\displaystyle cT(n)}$どこ${\displaystyle c}$は定数で、${\displaystyle c>0}$そして${\displaystyle T(n)}$は関数である${\displaystyle n}$、${\displaystyle \Omega (T(n))}$何かが下に限られていることを表す${\displaystyle cT(n)}$どこ${\displaystyle c}$は定数で、${\displaystyle c>0}$そして${\displaystyle T(n)}$は関数である${\displaystyle n}$、 そして $\displaystyle \Theta (T(n))$両方を表現する${\displaystyle O(T(n))}$そして${\displaystyle \Omega (T(n))}$[ ^{3 ]これらの表記法に}もそれぞれ名前があります。${\displaystyle O(T(n))}$ビッグオー記法と呼ばれ、${\displaystyle \Omega (T(n))}$これはビッグオメガ表記と呼ばれ、$\displaystyle \Theta (T(n))$これはビッグシータ表記と呼ばれます。

重要な複雑性クラス P、BPP、BQP、PP、および PSPACE は、プロミス問題に基づいて比較できます。プロミス問題とは、入力がすべての可能な入力文字列の集合から選択されると想定される決定問題です。プロミス問題はペアです。${\displaystyle A=(A_{\text{yes}},A_{\text{no}})}$、 どこ${\displaystyle A_{\text{はい}}}$はいインスタンスの集合であり、${\displaystyle A_{\text{no}}}$これはインスタンスが存在しない集合であり、これらの集合の共通部分は空集合である。${\displaystyle A_{\text{yes}}\cap A_{\text{no}}=\varnothing }$これまでの複雑性クラスはすべて、プロミス問題を含んでいます。^{[ 4 ]}

量子コンピュータによって効率的に解ける、誤差が限定された問題のクラスは、BQP（「限定誤差、量子、多項式時間」）と呼ばれます。より厳密に言えば、BQPは、多項式時間量子チューリングマシンによって、エラー確率が最大でも1/3以下の問題クラスです。

確率的問題のクラスとして、BQPは、確率的チューリングマシンで効率的に解ける問題クラスであるBPP （「有界誤差、確率的、多項式時間」）の量子版である。^{[ 6 ]}知られているように、${\displaystyle {\mathsf {BPP\subseteq BQP}}}$そして広く疑われているが証明されていないのは、${\displaystyle {\mathsf {BQP\nsubseteq BPP}}}$これは直感的には、量子コンピュータは時間計算量の点で古典コンピュータよりも強力であることを意味する。^{[ 7 ]} BQPはPPのサブセットである。

BQPとP、NP、PSPACEの正確な関係は不明である。しかし、${\displaystyle {\mathsf {P\subseteq BQP\subseteq PSPACE}}}$つまり、量子コンピュータで効率的に解ける問題のクラスには、決定論的な古典コンピュータで効率的に解ける問題がすべて含まれますが、多項式空間リソースを持つ古典コンピュータでは解けない問題は含まれません。さらに、BQP は P の厳密な上位集合であると推測されています。つまり、量子コンピュータで効率的に解ける問題の中には、決定論的な古典コンピュータでは効率的に解けない問題が存在するということです。例えば、整数因数分解と離散対数問題はBQP に含まれることが知られており、P には含まれないと考えられています。BQP と NP の関係については、NP の問題の一部が BQP に含まれるという事実以外にはほとんど知られていません (例えば、整数因数分解と離散対数問題はどちらも NP に含まれています)。${\displaystyle {\mathsf {NP\nsubseteq BQP}}}$つまり、量子コンピュータでは効率的に解けない、効率的にチェック可能な問題が存在すると考えられている。この考えの直接的な結果として、BQPはNP完全問題のクラスとは互いに素であるとも考えられている（もしNP完全問題がBQPに含まれるならば、NP困難性からNPのすべての問題がBQPに含まれることになる）。^{[ 8 ]}

BQPと基本的な古典的複雑性クラスとの関係は、以下のように要約できます。

${\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq PP\subseteq PSPACE}}}$

BQPは複雑性クラスに含まれることも知られている。${\displaystyle \color {Blue}{\mathsf {\#P}}}$（より正確には、関連する意思決定問題のクラスにおいて）${\displaystyle {\mathsf {P^{\#P}}}}$⁠ ) ^{[ 8 ]}はPSPACEのサブセットである。

古典コンピュータで量子計算モデルを効率的にシミュレートする方法は知られていない。つまり、古典コンピュータでは量子計算モデルを多項式時間でシミュレートすることはできない。しかし、量子回路は${\displaystyle S(n)}$量子ビット${\displaystyle T(n)}$量子ゲートは、古典回路によってシミュレートできます。${\displaystyle O(2^{S(n)}T(n)^{3})}$古典ゲート。^{[ 3 ]}この古典ゲートの数は、量子回路をシミュレートするために必要なビット操作の数を決定することによって得られます。これを行うには、まず、${\displaystyle S(n)}$量子ビットは考慮に入れなければならない。${\displaystyle S(n)}$量子ビットは、2次元の複素ベクトル、すなわち状態ベクトルで記述できます。これらの状態ベクトルは、振幅と呼ばれる係数を持つ成分ベクトルの線形結合でも記述できます。これらの振幅は、1に正規化された複素数であり、振幅の絶対値の二乗の合計が1でなければなりません。^{[ 3 ]}状態ベクトルの要素はこれらの振幅です。線形結合の記述における係数として機能する振幅は、それぞれ状態ベクトルの非ゼロ成分に対応します。これを方程式で表すと次のようになります。${\displaystyle \alpha {\begin{bmatrix}1\\0\end{bmatrix}}+\beta {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}}$または${\displaystyle \alpha \left\vert 1\right\rangle +\beta \left\vert 0\right\rangle ={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}}$ディラック記法を用いて、全体の状態は${\displaystyle S(n)}$量子ビットシステムは単一の状態ベクトルで記述できます。システム全体を記述するこの状態ベクトルは、システム内の個々の量子ビットを記述する状態ベクトルのテンソル積です。${\displaystyle S(n)}$キュービットは、単一の状態ベクトルであり、${\displaystyle 2^{S(n)}}$各基底状態または成分ベクトルに関連付けられた振幅である次元とエントリ。したがって、${\displaystyle 2^{S(n)}}$振幅は、${\displaystyle 2^{S(n)}}$次元複素ベクトル、これは状態ベクトルです${\displaystyle S(n)}$量子ビットシステム。^{[ 9 ]}量子回路をシミュレートするために必要なゲート数の上限を得るには、各量子ビットに関する情報を指定するために使用されるデータ量の十分な上限が必要です。${\displaystyle 2^{S(n)}}$振幅。これを行うには。${\displaystyle O(T(n))}$各振幅をエンコードするには、ビット精度で十分です。^{[ 3 ]}したがって、${\displaystyle O(2^{S(n)}T(n))}$古典的なビットは、${\displaystyle S(n)}$キュービットシステム。次に、${\displaystyle T(n)}$量子ゲート ${\displaystyle 2^{S(n)}}$振幅を考慮する必要がある。量子ゲートは次のように表すことができる。$2^{S(n)}\times 2^{S(n)}}$疎行列。^{[ 3 ]}したがって、それぞれの適用を考慮すると、${\displaystyle T(n)}$量子ゲートでは、状態ベクトルは$2^{S(n)}\times 2^{S(n)}}$それぞれの疎行列${\displaystyle T(n)}$量子ゲート。状態ベクトルが乗算されるたびに$2^{S(n)}\times 2^{S(n)}}$疎行列、${\displaystyle O(2^{S(n)})}$算術演算を実行する必要がある。^{[ 3 ]}したがって、${\displaystyle O(2^{S(n)}T(n)^{2})}$状態ベクトルに適用される各量子ゲートのビット演算。${\displaystyle O(2^{S(n)}T(n)^{2})}$古典的なゲートをシミュレートするには${\displaystyle S(n)}$量子ゲートが1つだけの量子ビット回路。したがって、${\displaystyle O(2^{S(n)}T(n)^{3})}$量子回路をシミュレートするには、古典的なゲートが必要です。${\displaystyle S(n)}$量子ビット${\displaystyle T(n)}$量子ゲート。^{[ 3 ]}量子コンピュータを古典コンピュータで効率的にシミュレートする方法は知られていないが、古典コンピュータを量子コンピュータで効率的にシミュレートすることは可能である。これは、${\displaystyle {\mathsf {BPP\subseteq BQP}}}$[ ^{4 ]​}

量子計算システムを古典計算システムの代わりに使う大きな利点の 1 つは、量子コンピュータは、古典的な多項式時間アルゴリズムが存在しない問題に対して多項式時間アルゴリズムを提供できる可能性があることですが、さらに重要なのは、量子コンピュータは、古典コンピュータが既に効率的に解決できる問題の計算時間を大幅に短縮できる可能性があることです。本質的に、量子コンピュータは、古典コンピュータではできない問題を解決するために必要な時間を判断できる可能性があり、特定の問題の解決に関連する計算効率を大幅に向上させることもできます。量子クエリ複雑性とは、特定の問題の解決に関連付けられたグラフに対して、問題を解決するために必要なクエリの複雑さ、つまりクエリの数を指します。クエリ複雑性についてさらに掘り下げる前に、特定の問題のグラフ解と、これらの解に関連付けられたクエリに関する背景について考えてみましょう。

物理学のさらなる進歩により、さらに高速なコンピュータが実現する可能性があると推測されている。例えば、非局所的だが信号伝達を行わない隠れ変数量子コンピュータは、 N個のアイテムからなるデータベースの検索を最大でも数秒で実行できることが示されている。${\displaystyle O({\sqrt[{3}]{N}})}$ステップ、グローバーのアルゴリズムよりわずかに高速化、${\displaystyle O({\sqrt {N}})}$手順。ただし、どちらの探索方法も量子コンピュータがNP完全問題を多項式時間で解くことを可能にするものではないことに注意してください。 ^{[ 13 ]} M理論やループ量子重力などの量子重力理論は、さらに高速なコンピュータの構築を可能にするかもしれません。しかし、これらの理論における計算の定義は、時間の問題のために未解決の問題です。つまり、これらの物理理論では、観測者がある時点でコンピュータに入力を送信し、その後の時点で出力を受け取ることが何を意味するのかを記述する明確な方法は現在ありません。^{[ 14 ] [ 15 ]}

• 量子コンピューティング
• 量子チューリングマシン
• 多項式階層（PH）

• ニールセン、マイケル；チュアン、アイザック（2000）。量子計算と量子情報。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-521-63503-5OCLC 174527496​​ 
• Arora, Sanjeev ; Barak, Boaz (2016).計算複雑性：現代的アプローチ. Cambridge University Press. pp. 201–236 . ISBN  978-0-521-42426-4。
• Watrous, John (2008). "Quantum Computational Complexity". arXiv : 0804.3401v1 [ quant-ph ].
• Watrous J. (2009)量子計算複雑性. Meyers R. (編) 複雑性とシステム科学百科事典. Springer、ニューヨーク、NY

• スコット・アーロンソンによるMIT講義