Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete

エンジニアリングや物理学の世界では、システムが時間の経過とともにどのように振る舞うかを予測する必要性が常に存在します。安定した橋の設計、宇宙船の誘導、あるいは電気グリッドの制御であれ、エンジニアはシステムの総エネルギー使用量や、軌道を維持するためのコストを計算するために数学的モデルに依拠しています。単純なシステムであれば、これらの計算は容易です。しかし、システムが数百万の相互作用する部品からなる巨大なものになると、数学は非常に複雑になり、最も強力なスーパーコンピュータでさえ、合理的な時間内に答えを見つけるのに苦労します。ここで、コンピュータができることとできないことの境界線がぼやけ始めます。科学者たちは以前から、量子力学的な微粒子の奇妙な規則に従って動作する量子コンピュータが、こうした特定の種類の膨大な計算問題を、いかなる古典的なマシンよりもはるかに速く解けるのではないかと疑ってきました。しかし、この信念が単なる希望以上のものになるためには、これらの問題が単に量子コンピュータが速いからではなく、古典的なコンピュータにとって本質的に困難であるという証明が必要でした。

ウォータールー大学の研究チームは、今まさにその証明を行い、制御理論における計算の限界に関する長年の疑問に決着をつけました。彼らは2つの特定のタスクに焦向しました。それは、安定したシステムの総エネルギー出力を計算することと、無限の未来におけるシステムの最適な制御コストを決定することです。現実世界において、これらはエンジニアがシステムの効率性と安全性を確保するために必要とする数値です。研究者たちは、これらの問題を「簡潔な（succinct）」表現を用いることで、可能な限り記述を困難にしました。巨大な行列のすべての数値を列挙する代わりに（それにはテラバイト単位のメモリが必要になります）、コンピュータプログラムのようなコンパクトな論理的指示セットを使用し、必要に応じて数値を生成できるようにしました。これにより、明示的に書き出すことは不可能であるほど巨大な次元を持つシステムを、記述自体は1ページに収まるほど小さく保ったまま記述することが可能になりました。

次に、研究チームは根本的な問いを投げかけました。標準的なコンピュータは、たとえ計算を高速化するためにランダムな確率を利用したとしても、このように簡潔に記述された問題を迅速に解くことができるのか？ 彼らの答えは、明確な「ノー」でした。彼らは、これらの特定のエネルギーおよび制御問題を解くことは、あらゆる量子コンピュータをシミュレートすることと同じくらい困難であることを証明しました。コンピュータサイエンスの言葉を使えば、これらの問題は「BQP完全（BQP-complete）」であることを示したのです。これは、もし古典的なコンピュータがこれらの制御問題を効率的に解けるのであれば、そのコンピュータは量子コンピュータが解けるあらゆる問題を解くこともできることを意味します。ほとんどの専門家は古典的なコンピュータにはそれができないと考えているため、研究者たちは、いかなる巧妙なアルゴリズムやランダム化手法を用いたとしても、古典的なコンピュータがこれらの特定の制御問題を合理的な時間内で解くことはできないと結論付けました。

この結論に至るために、研究者たちは単に推測したのではなく、数学的な架け橋を築きました。彼らは、量子コンピュータが行うあらゆる計算が、これらの制御問題の一つに直接翻訳できることを実証しました。もし複雑な量子実験の結果を知りたいのであれば、その実験をシステムのエネルギーや制御コストの記述の中にエンコードすることができます。もし古典的なコンピュータがそのエネルギーに関する問いに対して迅速に答えを出せるとすれば、それは事実上、量子実験を代行して実行していることになります。研究者たちは、この翻訳があらゆる可能な量子タスクに対して成立することを示したため、制御問題の難易度は量子計算自体の難易度と全く同一であることを証明したのです。

また、この研究は、量子コンピュータがこれらの問題を効率的に解けることも示しました。この種の行列計算を扱うために設計された特定の量子アルゴリズムを使用することで、量子マシンはシステムが大きくなるにつれて緩やかに増加する時間内で答えを見つけることができます。これにより、明確な境界線が生まれます。つまり、問題は古典的なコンピュータにとっては証明可能なほど困難であり、量子コンピュータにとっては容易であるということです。これは、量子と古典の計算能力が根本的に異なるという広く受け入れられている信念に基づいています。研究者たちは単に数学を解くより速い方法を見つけたのではなく、制御問題の規模が大きくなっても難易度が上がらないような、量子力学の力を試すためのリトマス試験紙となる特定のクラスの問題を特定したのです。

この研究が重要なのは、議論を憶測から確信へと移行させた点にあります。長年、エンジニアリングにおける量子コンピューティングの約束は、量子マシンが単に線形代数において高速であるという考えに基づいてきました。この論文は、システムの安定性や制御に関する特定の重要な問いにおいて、その優位性が単なる速度の問題ではなく、能力の問題であることを裏付けました。これは、特定の、現実世界のエンジニアリング上の問いが、どれほど多くの時間やメモリを与えられたとしても、古典的なコンピュータには根本的に到達不可能であることを立証しています。研究者たちは、ジェットエンジンのための量子コントローラーや電力網のための量子コントローラーを構築したと主張しているのではなく、そのようなコントローラーの数学的基盤は、量子コンピュータだけが足を踏み入れられる領域に属することを証明したのです。

また、この研究は困難の性質を明らかにしました。これらの問題が難しいのは、数値が乱雑であったりシステムが混沌としていたりするからではありません。情報の記述方法の中に、古典的なコンピュータがプロセス全体をシミュレートすることなしには剥ぎ取ることのできない複雑さが隠されているからです。研究者たちは、システムが厳密に安定しており、かつ秩序あるものであっても、隠された情報の規模そのものが障壁を生み出すことを示しました。この障壁は、より優れたアルゴリズムの欠如による一時的なものではなく、古典的な計算における構造的な限界なのです。

結局のところ、この論文は明確な一線を画しています。それは、特定の重要なクラスの無限ホライゾン制御問題において、効率的な計算の未来は排他的に量子技術にあるということを告げています。もしエンジニアが、コンパクトな論理規則によってのみ記述できるほど膨大な規模のシステムを最適化する必要が生じた場合、彼らは量子マシンに頼らざalasを得ません。古典的なアプローチは、たとえあらゆる確率的なトリックを用いたとしても、単に壁に突き当たるだけなのです。この結果は、単に量子的な優位性のリストに新しい項目を加えただけでなく、量子的な世界が単なる選択肢ではなく、唯一の進むべき道となる新しい問題のカテゴリーを定義したのです。