量子超越性
線形光学ネットワークを介して送信された同一の光子に基づくこの計算パラダイムは、古典アルゴリズムが(ガウス行列のパーマネントの計算が#P-Hardであり、 多項式階層が潰れないと言う、計算複雑性理論上の予想の下で)解くことが出来ない、特定のサンプリング及び検索問題を解くことができる。ただし、十分に大きな損失とノイズがあるシステムでのボソンサンプリングは、効率的にシミュレーションできることが示されている。
これまでのボソンサンプリングの最大の実験では、6つのモードがあり、一度に最大6つの光子を処理できた。時間内にボソンサンプリングの実行をシミュレートするための最善の古典アルゴリズムは、n個の 光子とm個の出力モードを持つシステムの場合、 O ( n 2 n + m n 2 ) {\displaystyle O(n2^{n}+mn^{2})} 時間で動作する。BosonSamplingはRでのオープンソース実装である。このアルゴリズムによると、ボソンサンプリングで量子優位性を実証するためには、50個の光子が必要であると推定される。
計算複雑性理論は、問題を解決するために必要なリソース(通常は時間またはメモリ )の量が、入力のサイズに対してどのように増加するかを論じる。 古典的な計算複雑性理論の拡張として、 量子計算複雑性理論は、物理的な量子コンピュータの構築の難しさやデコヒーレンスとノイズの影響を必ずしも考慮せずに、理論的な汎用量子コンピュータに何ができるかを議論する。量子情報は古典的な情報を一般化したものであるため 、 量子コンピュータはあらゆる古典的なアルゴリズムをシミュレートできる 。
複雑度クラスBQP (有界誤差量子多項式時間)は、 汎用量子コンピュータによって多項式時間で解くことができる決定問題のクラスである。重要な古典的複雑性クラスの階層に関連付けらる P ⊆ B P P ⊆ B Q P ⊆ P S P A C E {\displaystyle P\subseteq BPP\subseteq BQP\subseteq PSPACE} 。