量子コンピューターが得意とする問題とは？

Olivia Lanes による量子コンピューティングの応用に関する動画をご覧ください。または YouTube で別ウィンドウで動画を開くこともできます。

はじめに

前回のレッスンでは、QUBO 定式化を使った最大カット最適化問題という一つの問題を深く掘り下げました。今回は異なるアプローチをとり、近い将来に実現可能なアプリケーションについてより広く議論します。まず、量子ソリューションが有益と思われる問題の種類をどのように選定するかについてお伝えします。次に、コミュニティで最近行われた研究事例をいくつか見ていきます。これにより、量子コンピューティング問題のさまざまなタイプと、それらへのアプローチ方法に対する直感を養い始めることができるでしょう。

古典的難しさと量子的難しさ

事例に入る前に、まずさまざまな問題の難しさをどのように研究・分類するかについて説明します。古典コンピューターで簡単に解ける問題もあれば、量子コンピューターでなければ解けないほど非常に難しい問題もあります。有名な例として、巨大な整数の素因数を見つける問題があります。RSA 暗号はこの問題の難しさを利用しており、Shor のアルゴリズムはこれを量子コンピューターで解くために設計されました。もう一つの例は、ソートされていないデータセット内で解を見つける問題で、これは Grover のアルゴリズムとして知られる量子アルゴリズムによって理論的に解くことができます。ただし、ほとんどの専門家は、これらのアルゴリズムには誤り訂正の実装が必要であり、技術がまだそこまで到達していないと考えています。

つまり、非常に簡単な問題と非常に難しい問題の間のスイートスポットに位置する問題——今日の量子コンピューターでは解けるが、古典コンピューターでは苦労する問題——を探しているのです。

複雑性クラス

これらの問題の難しさは、計算複雑性理論と呼ばれるコンピューターサイエンスの分野で分類・分析されます。古典コンピューティングには非常に多くの複雑性クラスがありますが、最も基本的なものはいくつかあります。

• P: 問題の規模が大きくなっても多項式時間で解ける問題。解くのが容易です。
• NP: 非決定性多項式（nondeterministic polynomial）の略。必ずしも多項式時間で解けるとは限りませんが、答えの検証は多項式時間で行えます。
• NP 完全: NP の中で最も難しい問題であり、既知の多項式時間解法は存在しません。巡回セールスマン問題や数独のような有名な問題がここに属します。
• BPP（有界誤りを持つ多項式時間問題）: 確率的な古典コンピューターが多項式時間内に一定の誤り範囲で解ける問題です。

量子コンピューティングの概念が発明されると、人々はこの新しいタイプのコンピューターがどのクラスの問題を効率的に解けるかを理解するために多大な努力を払いました。そして新しいクラスの問題が考案されました。

• BQP（有界誤りを持つ量子多項式問題）: BPP の量子版です。小さな誤りの確率のもとで、量子コンピューターが多項式時間で解ける決定問題のクラスです。

これらのクラスはすべて、PSPACE と呼ばれるより大きなクラスの中に含まれています。上の図は複雑性クラス間で予想される関係を示していますが、これを数学的に決定的に証明することは非常に困難です。BQP は必ずしも NP 完全と重なるわけではないことに気づくでしょう。しかし、NP 完全の問題を解くことを目標とした量子コンピューティングのアプローチが依然としてあるのを見たことがあるかもしれません。

よくある誤解の一つは、量子スピードアップの数学的証明が見つかっていない問題については量子ソリューションを探る意味がない、というものです。しかし、量子アルゴリズムが古典的な対応物より速いことを数学的に証明するのは困難です。Shor のアルゴリズムと Grover のアルゴリズムは、これまでに実現されたわずかな例の一つです。実際、P と NP が異なることを厳密に証明することは、直感的にはそうであるはずなのに、数学全体で最も難しい未解決問題の一つです。

しかし、問題のスケールが大きくなるにつれてアルゴリズムがどのように拡張するか——これが複雑性クラスに反映されることですが——は、アルゴリズムの最も関連性の高い特徴とは限りません。このスケーリングはしばしば最悪ケースを示しています。実際には最悪ケースが最もよく遭遇するものではない可能性は十分にあります。

難しさの証明が難しいからといって進歩できないわけではありません。ここでヒューリスティック解という考え方を紹介します。実験家の方であれば、このタイプの解法に馴染みがあるかもしれません。ヒューリスティックとは、実用的ではあるが必ずしも最適ではない問題解決のアプローチのことです。解は有用であるために最適である必要はないからです。例えば、金融への応用を考えてみてください。量子コンピューターが利用できるほとんどの金融アルゴリズムで指数的なスピードアップはまだ見つかっていませんが、最適な解である必要はありません。金融では、わずか 0.1% 効率が上がる解でさえ、数十億ドルの利益に相当する可能性があります。

今日の量子コンピューターとその限界

では、今まさに量子コンピューティングに適したユースケースや問題をどのように見極めるのでしょうか？量子ユーティリティ、あるいは量子優位性が今または近い将来に実現できると信じる十分な理由はあるでしょうか？

まず、問題が確実に持つべきでないものを挙げる方が簡単かもしれません。大量の量子ビットを必要とすることはできません。数千から数百万の量子ビットを持つプロセッサーはまだ利用可能ではありません。それが Shor のアルゴリズムなどが実現からほど遠い主な理由の一つです。回路の深さも深すぎてはいけません。回路深度の制限は多くの要因に依存しますが、一般的に、実験が文献でまだ達成されていない深度を必要とする場合、おそらく機能しないでしょう。そして最後に、誤り訂正が必要とわかっているアルゴリズムは現時点ではまだ実行できません。

これらの制限はすべて IBM Quantum® ロードマップ で取り上げられており、2030 年代初頭に誤り訂正を達成することが期待されています。しかし現時点では、特定の QPU で現在利用可能な量子ビットのほとんどを活用する実験を探す必要があります。また、エラー緩和と抑制の重要性も強調されています。そして最後に、社会にとって重要な将来のアプリケーションへの明確な拡張性があり、最終的に量子優位性につながるものが見えるべきです。

アプリケーション領域とユースケース

では、ユースケースの例をいくつか見ていきましょう。近い将来から中期的に有望な結果が期待できるとして特定された、3 つの主要なカテゴリーに分けられます。

1. 自然シミュレーション。現在の古典的な原子・分子シミュレーション手法は、原子構造の非効率な数学的記述によって制限されています。古典コンピューターでは量子状態を保存・操作するために指数的に多くのリソースが必要ですが、量子コンピューターでは効率的に行えます。これにより、二酸化炭素の固定化、代替電池の開発、新薬の発明などの進歩につながる可能性があります。この分野で特に関連するアルゴリズムは、材料の平衡状態や最低エネルギー状態などの特性を推定するために使われる変分量子固有値ソルバー（VQE）、材料の応答関数やスペクトル特性を推定するために使われる時間発展シミュレーション（TDS）アルゴリズム、そして近い将来さらに注目が集まると思われる新参者のサンプルベース量子対角化（SQD）です。

2. 最適化。この分野はコンピューティング全般に広く存在するため、ユースケースは多様です。よく聞くいくつかの例として、金融でのポートフォリオ最適化、産業デザイン、流通・サプライチェーンがあります。金融に関連してよく耳にするアルゴリズムは、すでにある程度詳しく取り上げた量子近似最適化アルゴリズム（QAOA）です。

3. 量子機械学習（QML）。この分野はここ数年で大きな注目を集めていますが、シミュレーションほど早くには有用にならないかもしれません。しかし、非常に重要なユースケースに対応するための印象的なアルゴリズムが開発されています。可能性のあるユースケースには、自然言語処理、ネットワークトラフィック分析、金融取引における不正検出などがあります。この分野の関連アルゴリズムは、量子サポートベクターマシン（QSVM）、量子ニューラルネットワーク（QNN）、量子生成的敵対的ネットワークなどです。

これらの広いアプリケーション領域の中で、コミュニティはより具体的なトピックに焦点を当てたグループが協力することに価値を見出しています。IBM® は、ヘルスケアとライフサイエンス、材料と高性能コンピューティング（HPC）、高エネルギー物理学、最適化という 4 つの特定分野でコラボレーターが出会い、生産的な相乗効果を生み出せるようにする「ワーキンググループ」というイニシアチブを主導しました。最近では、サステナビリティに関する 5 番目のワーキンググループも設立されました。

これからこれらのワーキンググループのいくつかが最近取り組んだ問題を詳しく見ていきます。ここでの主な目標は、実験のすべての詳細を理解することではありません——これは、論文が自分の専門分野から少し外れている場合、専門家でも難しいことがあります。目標は単に、量子コンピューターが得意な問題の種類とそのアプローチ方法についての直感を養うことです。興味があれば、論文全文を読むことをお勧めします。

ユースケース 1：ハドロン動力学のシミュレーション

まず、ワシントン大学の Martin Savage グループによる論文 Quantum Simulations of Hadron Dynamics in the Schwinger Model Using 112 Qubits を取り上げます。

高エネルギー物理学の専門家でなくても、「ハドロン」という言葉はご存知かもしれません。大型ハドロン衝突型加速器（LHC）としてです。LHC は円周 27 km の巨大な粒子加速器で、ついにヒッグス粒子の観測を可能にしました。ハドロンとは、クォークと呼ばれる他の小さな粒子から成る亜原子複合粒子です。ハドロンの例としては、中性子や陽子があります。

少し背景を説明すると、LHC は超高エネルギーで粒子を衝突させることによって基礎物理学の研究を可能にするために建設されました。LHC によって科学者たちは、初期宇宙と自然の基本法則についてさらに理解を深めることを目指しています。原理的には、十分強力な量子コンピューターがあれば、これらの粒子の相互作用を最初から最後までシミュレートできます。まだそこには達していませんが、着実に進歩しています。

Schwinger モデルは、これらの動力学の一部をシミュレートするために使われる人気のある単純なモデルです。これは、1+1 次元（時間と 1 つの空間次元）で光子を介して相互作用する電子と陽電子の振る舞いを記述するモデルです。このモデルはクォークとハドロンの相互作用を記述する量子色力学（QCD）との多くの類似点を持っていますが、QCD は非常にシミュレートが難しいです。そのため、Schwinger モデルは、両者に共通するいくつかの現象を調査するためのトイモデルとしてよく使われます。

この問題に取り組んだ理由を理解するために、一連の質問をしてみましょう。

まず、量子コンピューターでのシミュレーションがうまくいくと信じる理由はなんでしょうか？ この場合、Schwinger モデルの電子と陽電子にはスクリーニング効果があり、遠くにあるフェルミオン間の相関が距離の増加に伴って指数的に減衰します。これは、チップの一方から他方への量子ビット間の長距離相互作用があまり必要ないことを意味します。そのような相互作用はエラーが非常に起きやすいことがわかっています。そのため、現在利用可能なハードウェアに非常に適しています。

次に、なぜこのトピックが興味深いのでしょうか？ 高エネルギー物理学は一般的に非常に関心の高い分野です。LHC の建設には数十億ドルが投じられ、世界中の何千人もの科学者や技術者がこの分野にキャリアを捧げています。Schwinger モデルは単純化されており、3 つの空間次元をカバーするように設計されていませんが、それでも完全な理論の有用な近似となっています。

最後に、この研究はどのように行われたのか、あるいはこの研究を継続する場合はどのようにアプローチするのでしょうか？ シミュレーション型実験では、VQE が最も一般的なアプローチの一つであり、最初のステップはほとんど常に同じです：基底状態を準備します。この場合は真空状態です。この実験では、SC-ADAPT-VQE（Scalable Circuits - Adaptive Derivative-Assembled Pseudo-Trotter ansatz-VQE の略）と呼ばれる VQE の新しいバージョンを使って、この真空上で基底状態とハドロン波束の両方を準備します。次のステップは、ハドロンを時間発展させることです。最後に、測定したい観測量を特定して測定します。

これらのステップは、ハドロン波束の部分を除いて、前回のレッスンで取り上げた QAOA の例と非常に似ています。なじみのある状態（ここでは真空状態）から始め、指数化されたハミルトニアンの系列で時間発展させます。多くの変分アルゴリズムがこの一般的なアプローチに従います。ただし、ここでの大きな違いは、時間発展を開始する前に回路の中心にハドロンの波束を作成することです。

では、波束はどのように作成するのでしょうか？ 真空上では、隣接するサイトにフェルミオン-反フェルミオン対を作成することでハドロンを励起できます。異なる位置にあるこのようなハドロンの重ね合わせを準備することで、任意の波束を準備できます。著者たちは境界に達することなく発展を観察するために、回路の中央に波束を配置しました。

ただし覚えておいてください：ノイズの多い QPU を扱う際のポイントは、回路深度を管理可能な範囲に保つことです。このために、SC-ADAPT-VQE プロトコルは対称性と長さスケールの階層構造を使って、状態準備のための低深度量子回路を決定します。これにより、パラメーター数が少なく、したがって浅い深度のアンザッツが作成されます。

実験は IBM Quantum Heron デバイスで実行され、動的デカップリング、ゼロノイズ外挿、Pauli ツイリング、そして最近開発された演算子デコヒーレンス繰り込みと呼ばれる技術など、いくつかの異なるタイプのエラー緩和と抑制が含まれていました。

上の図は、この実験で注目する観測量であるカイラル凝縮体（ハドロンの超流体相のようなもの）を示した論文の図です。この実験に使用されたサイトの中心に波束があることがわかります。黒線は（計算コストの高い）古典シミュレーションのエラーのない結果で、誤差棒付きの点は 133 量子ビットの IBM 量子コンピューター Torino の結果です。

波束発展の 2 つの異なる時間ステップが示されています。時刻 $t=1$ では、カイラル凝縮体が狭く局在しており、古典シミュレーションとよく一致していることがわかります。$t=14$ では、はるかに広がっています。シミュレーターとの比較は以前ほど完璧ではありませんが、それでも理論とデータの間に非常に良い一致が見られ、これは励みになります。

まとめると、これは量子コンピューティングを適用しようとは最初は思わないかもしれない種類のシミュレーション研究の非常に優れた例ですが、真の可能性を示しています。完璧ではありませんが、素粒子物理学の専門家でなくても、量子コンピューターが波束の外向きへの伝播を正確に予測していることがわかります。これはまさに期待される結果です。この分野での将来の研究が続き、高エネルギー物理学者たちが量子コンピューティングを研究フローに組み込む方法を見つけ続けることが期待されます。目標は、困難な理論的問題をより精確に解き、実験を使って理論を受け入れたり棄却したりすることで、新しい物理を発見し、改良された検出器を開発し、自然の最も根本的なレベルをより深く理解することです。

ユースケース 2：イジングスピングラスの最適化

次の例は最適化に焦点を当て、スペインのバスク大学と Kipu Quantum チームのメンバーによる論文 Bias-Field Digitized Counterdiabatic Quantum Optimization を深く掘り下げます。

この論文で著者たちは新しい最適化手法を開発し、イジングスピングラスの基底状態を求めることに適用しました。前述のように、多くの組み合わせ最適化問題はイジングハミルトニアンの低エネルギー状態を求める問題として定式化できます。イジングモデルは微視的スピンの配列の相互作用を記述します。いくつかの条件下では、このモデルはスピンが「凍結温度」と呼ばれる温度以上で磁気モーメントが無秩序になるガラスのように振る舞うことを予測します。

最初は前と同様に、いくつかの定義から始めましょう。最初は「反断熱的（counterdiabatic）」という用語で、これはそのプロセスがどれほど速く起こるかに関わらず、系が経験する非断熱的効果を抑制する一種の発展です。前回のエピソードで学んだ断熱定理を思い出してください——系を基底状態にとどまらせたい場合、通常は非常にゆっくり発展させる必要があります。これは大きな問題です。発展をゆっくりにすればするほど、エラーが発生する時間が長くなるからです。反断熱駆動（CD）は、これらの望ましくない励起を打ち消す項を加えることでこれに対処することを目指します。主なアイデアは、望ましくない遷移を引き起こす可能性のある励起を抑制することで実験全体をスピードアップし、量子回路深度を削減することです。

次はタイトルにあるもう一つの専門用語：バイアスフィールドです。VQE のような他の反復アルゴリズムは、古典的なパラメーターを状態に取り込み、固定ハミルトニアンの最小期待値をもたらすパラメーターのセットを多次元パラメーター空間で探索するために古典オプティマイザーを使います。この場合、代わりにハミルトニアン自体を毎回変化させ、既知の場合から興味のある場合に向けて断熱的に移行します。ハミルトニアンを変化させるために、一つの反復からの Pauli-Z 期待値を次の反復のハミルトニアンへのバイアスフィールドとして直接適用します。このようにして、古典オプティマイザーを必要とせずに実際の解に向かってダイナミクスを誘導します。

では、この実験はなぜ興味深いのでしょうか？ イジングスピングラスは物理学において基本的な関心事ですが、この新しいアプローチはそれ以上に一般的です。多くの最適化問題に適用できるため、論文は幅広い関心を集めています。

そして、なぜこれがうまくいくと思ったのでしょうか？ 彼らが提案するアルゴリズムは発展をスピードアップして回路深度を削減し、同時に非断熱的遷移を抑制します。さらに、不毛な高原や局所最小値への収束という問題を引き起こす可能性のある古典最適化サブルーチンに依存しません。最後に、著者たちは問題ハミルトニアンの相互作用が実際の QPU のハードウェア接続性に合うようにしており、これは常に非常に重要です。

では、この手法はどのように機能するのでしょうか？ 繰り返しになりますが、他のほとんどの反復量子アルゴリズムとは異なり、古典オプティマイザーを使いません。代わりに、各反復の解を次の反復の入力に与えることで、バイアスフィールドデジタル化量子最適化アルゴリズムは基底状態を段階的に精練し、最終的な発展状態にどんどん近づけていきます。そして反断熱プロトコルと組み合わせることで、ノイズの多いハードウェアでもスムーズに実行できるはずの短深度量子回路でこれを行えます。

実験が行われた際、著者たちは 127 量子ビットの IBM Quantum コンピューター Brisbane でアルゴリズムを実行することを選びました。以下は、100 量子ビット上のランダムに生成された最近傍スピングラスインスタンスに対する最適化アルゴリズムの第 8 反復を示す図です。DCQO と BF-DCQO の理想化された古典シミュレーション結果、および量子コンピューターで実行された実験結果を比較しています。参考として、Gurobi という古典ソルバーの結果も示されています。わずか 10 回の反復で、BF-DCQO は DCQO と比較して劇的な改善をもたらしています。実験結果はノイズのために理想的な結果とは多少異なりますが、それでも理想的な DCQO よりも優れたパフォーマンスを示しています。これは、量子最適化に関して依然として多くの優れた進歩がなされており、初めて 100 量子ビット以上で良い結果が報告されていることを示しています。

ユースケース 3：mRNA 二次構造予測

最後に、Moderna Pharmaceuticals による論文 mRNA Secondary Structure Prediction Using Utility-Scale Quantum Computers について説明します。

まず、mRNA について簡単におさらいします。メッセンジャー RNA はタンパク質合成に関与する RNA の一種です。基本的に DNA によって与えられた指示を読み取ります。mRNA の二次構造は、以下の図に示すようにチェーンがどのように折り畳まれているかです。RNA 二次構造予測問題とは、RNA を構成する塩基やヌクレオチドの配列の最も安定した折り畳み——アデニン（A）、シトシン（C）、ウラシル（U）、グアニン（G）——を見つける問題です。以下の画像は mRNA に見られる一般的な折り畳み構造を示しており、各色は異なる種類の二次構造を表しています。どの構造が他の構造より有利なのかはよく理解されておらず、できることは、どの構造が未折り畳み状態と比較して最も低い自由エネルギーを生み出すかを計算することだけです。そこに量子コンピューターの出番があります。

では、mRNA 二次構造はなぜ重要なのでしょうか？ その正確な予測は、DNA や遺伝子を理解するためだけでなく、COVID-19 ワクチンのような RNA ベースの治療薬を設計するためにも重要です。

これは可能な構成の数が膨大なため、古典コンピューターにとって手強い最適化問題であることは以前から知られていました。いくつかの構成では、NP 完全問題であることが知られています。しかし、量子コンピューター上では、二次構造予測を二値最適化問題として定式化できます——これは私たちが対処方法を知っている種類の問題です。さらに、小規模な量子デバイスと量子シミュレーターでの正確な RNA 予測の証拠が文献にすでに存在していました。しかし、これはより大型のハードウェアでも機能するのでしょうか？

この実験は、従来の VQE アルゴリズムの改良版であり、より良い収束性を達成することが期待される条件付きバリュー・アット・リスク変分量子固有値ソルバー（CVaR-VQE）を使って実行されました。

上のプロットは、42 ヌクレオチド、80 量子ビットのインスタンスに対するサンプリングされたビット文字列の測定確率の分布と対応するエネルギーを示しています。ここで、ビット文字列はヌクレオチドのペアリングを象徴しています。量子コンピューターが見つけた最低エネルギーのビット文字列が比較用古典ソルバーのものと一致していることが示されており、これは素晴らしいことです。また、量子コンピューターが見つけた最低エネルギービット文字列に基づく、そのヌクレオチド鎖の最適な折り畳み構造も示されています。

まとめ

これらの 3 つのユースケースが、現在の最先端の研究がどのようなものかを理解する十分な文脈を提供し、これまでは試みなかったかもしれない新しい量子実験に挑戦する自信を与えてくれることを願っています。

覚えておいてください：量子コンピューティングはすべての問題に適しているわけではありません。そして実際、これは私たちが古典コンピューティングにどれほど長けるようになったかの証でもあります。量子コンピューティングをある問題に適用できると思っても、それが興味深い結果をもたらすとは限りません。スケーリングを考慮する必要があります。

回路深度は諸刃の剣です。古典コンピューターではできない興味深い研究を行うには回路深度がある程度大きい必要がありますが、現時点では深度を増やしすぎるとハードウェアノイズによって忠実度が低下します。あのスイートスポットを見つけ、それが動く標的であることを知ることが重要です。では、次のレッスンまでの間に、自分の研究で出会った問題と、これまでに学んだことでどのようにアプローチするかを考えてみてください。そして、解決策がうまくいかなくても、それで構いません。それが研究というものです。