小規模量子回路における量子優位性が公式に証明

IBM T. J. Watson Research Center、カナダのウォータールー大学、ドイツのミュンヘン工科大学の研究者らが、量子コンピュータが特定の問題を古典的コンピュータよりも早く解けることを理論的に証明した。彼らが考案したアルゴリズムは現在の量子計算プロセッサの制限にも適合しており、実験的な証明が間もなく実施される可能性がある。

証明したのは、正確には3名の研究者 – Sergey Bravyi、David Gosset、RobertKönigの3氏である。

一定期間内で実行される並列量子アルゴリズムは、古典的なものよりも確実に強力であり、2元2次形式に関連する、ある種の線形代数問題の解法において、証明可能な優位性を持ちます。

研究者らが示した証明は、量子定数段数で実装可能な“隠れ線形関数(hidden linear funcrtion)”問題に解答するためのアルゴリズムに基づいている。隠れ線形関数とは、完全には知られていないが、計算可能な別の関数内に“隠れている”線形関数である。例えば線形関数は、クエリ可能な量子オラクル内に隠れている可能性がある。問題となるのは、既知の関数を適用した結果に基づいて、隠れ線形関数の完全な特徴付けを行うことだ。公開鍵を反転して秘密鍵を見つけるという問題がそれに似ていると思うのであれば、驚くことはない、まさにその問題なのだ。オラクルの場合、この問題は、オラクルへのクエリ数を最小化する古典的なBernstein-Vaziraniアルゴリズムによって解決される。ここで3人の研究者らは、Bernstein-Vaziraniアルゴリズムの適用はオラクルの実質的な適用性を制限するものであるとして、2次元グリッドグラフ内部の線形関数を“隠す”方法を提案している。実際にこれが可能であることを証明した上で、研究者らは、隠れた関数を見つけ出すための量子定量段数アルゴリズムを構築した。

研究者らによる証明の残り半分では、量子回路とは対照的に、古典回路では、入力数の増加に伴ってその段数(depth)を増やす必要があることが示されている。例えば量子回路では、入力数に関わらず、多くとも10段の回路があれば問題を解くことが可能である。これに対して古典回路では、16入力の問題には10段、32入力には14段、64入力の問題には20段、といった回路が必要になる。証明のこの第2部には、哲学的な意味で興味深いものがある。量子非局所性の考え方を深く掘り下げており、結果的に重ね合わせと共に量子プロセッサの最も特異的な性質のひとつである量子もつれに関連しているからだ。すなわち、量子の優位性は、量子力学の最も本質的な性質を根源とするものとも考えられるのだ。

物理的なレベルにおいても、この成果の価値が過小評価されることはない。IBMでは、IBM QのバイスプレジデントであるBob Sutor氏が次のように記している。

今回の証明は、定量段数計算という限定的なケースではありますが、量子アルゴリズムと古典アルゴリズムの無条件分離を始めて立証したものです。

これまでの量子コンピュータが古典コンピュータよりも強力であるという考え方は、因数分解問題に基づくものだった。Shor氏は量子コンピュータが因数分解を多項式時間で実行可能であること、すなわち、既知のどの古典コンピュータのアルゴリズムよりも効率的であることを示した。興味深い結果ではあるものの、将来的により効率のよい古典的因数分解アルゴリズムが発見される可能性を否定することはできない。従って、因数分解問題に関する効率的な解法が存在しないと推測されない限り、すなわち“P ≠ NP”が実証されない限り、量子の優位性が証明されたとは言えないのだ。

前述のように、Bravyi、Gosset、König各氏のアルゴリズムは演算の定数(量子回路の段数)に依存するため、基本的には量子ビットの誤り率とコヒーレンス時間に関連して、一連のオペレーションの最大期間と総数が制限されるという、現在の量子コンピュータプロセッサの限界にうまく適合すると思われる。この制限が故に、現在の量子回路で実行可能なアプリケーションにおいては、段数の少ない回路を使うことが重要になっているのだ。提案されたアルゴリズムのこの性質により、IBMの研究者らは、IBMの量子コンピュータを使った量子優位性の実証作業をすでに始めている、とSutor氏は述べている。

証明に関する詳細に興味があれば、David Gosset氏がPerimeter理論物理研究所で行った講演と、プレゼンテーションで使用されたスライドを参照して頂きたい。