南カリフォルニア大学の研究者が指数関数的な量子スケーリングの高速化を実証

アルゴリズムの発見は新しい時代に突入しました。 IBM量子ハードウェア/ソフトウェアの最新の性能向上により、量子優位性に近づくためのアルゴリズムの開発・改善が一層容易になっています。

最近、南カリフォルニア大学（USC）の Daniel Lidar博士が率いるチームの研究者は、サイモンの問題の修正版に対するアルゴリズムの指数関数的な高速化をIBMの量子コンピューターを使用して実証した結果をPhysical Review Xに発表しました。この論文は、古典手法の限界に関して未証明な仮定に依存することのない量子スケーリングの高速化の、一つの世界初の証明です。

簡単に言えば、このチームは、ノイズのある量子ハードウェアで最大126量子ビットの量子回路を実行し、問題サイズの増加に対して量子コンピューターによる速度向上が指数関数的に増大することを実証しました。しかし、59量子ビット以上では今日の量子コンピューター特有のノイズによって、古典コンピューターが優位となりました。

アルゴリズム開発の重要な部分は、量子が古典手法よりも高速化できる問題を特定し、どのような高速化が期待されるかを決定することです。この取り組みは、今日の、ノイズのある量子デバイス上での新規な戦略を必要とします。
「量子コンピューティングの究極の目標は、量子アルゴリズムを指数関数的な速度向上で実行できることを実証することです。」とLidar氏は述べています。指数関数的な速度向上とは、変数の追加によって問題のサイズが大きくなるにつれて、量子と古典のパフォーマンスの差が拡大し続け、量子が優位になることを意味します。

これまでに量子ハードウェアで実証されたのは、多項式的加速など、より小規模な高速化のみでした。多項式的加速の例としては、2023年の Physical Review Letters の論文で Lidar と Bibek Pokharel が示した Bernstein-Vazirani アルゴリズムがあります。

サイモンの問題はオラクルに基づくゲームです。このゲームでプレイヤーは、オラクルだけが知っている（言い換えればブラックボックスに入っている）隠れたビット文字列（b）を、できるだけ少ないクエリで正しく推測します。Lidar氏のチームは回路の複雑さを限定するためにゲームをわずかに変更し、ハミング・ウェイト、すなわちビット・ストリングに実質的に含まれる1の数を制限しました。このバージョンでのサイモンの問題のルールは次のようになります。

秘密のビットストリング b∈0,1 n を先に設定します。このビット文字列は決まったハミング・ウェイトwを持っています。言い換えると、そのビット文字列には正確に w個の 1が含まれています。

未知の関数 fは、x=y または x=y+b の場合にのみ、f(x)=f(y) となるように定義されています。つまり、ある出力値は、隠れたビット文字列 bによってオフセットされた、二つの入力値のみによって共有されています。一対のビット文字列の組み合わせをうまく見つけ、その間隔が隠されたビット文字列にちょうどなっていると、関数の値が同じになり、隠されたビット文字列がわかります。

プレイヤーは、この関数の内容を知ることはできません。アクセスできるのはオラクルだけであり、任意の入力 x∈0,1 nについてクエリを実行し、f(x) を取得できます。オラクルにクエリを実行するには、古典コンピューターまたは量子コンピューターを使用できます。ただし、量子コンピューターを使用すると、重ね合わせをクエリに利用できます。つまり、測定されるまでは、クエリは二つの状態の複素線形結合にすることができます。

古典コンピューターでこの隠されたビット文字列を見つけるのは、そのビット文字列のビット数に対して指数的に困難であることが証明されています。1994年、Daniel Simonは、この問題を理想的なノイズのない量子コンピューターで実行した場合、量子オラクルへのわずかなクエリで解決できるという理論的な証明を持ったアルゴリズムを開発しました。このアルゴリズムは最良の確率的古典アルゴリズムに対する指数関数的な優位性をもたらします。

サイモンの問題に対する実用的な応用は知られていませんが、オラクルに依存しない、ショアの周期発見問題への足がかりとなります。どちらもアーベル群の隠れ部分群問題の例であり、群内の要素の可換性を利用して、グループにある隠れた構造を解明します。ここで可換性とは、演算の順序が結果に影響を及ぼさないという性質です。

Lidar氏とチームは、サイモンのアルゴリズムによる指数関数的な高速化を理論から実機にもたらすために、フォールト・トレランスがまだ実現していない今日の量子ハードウェアでこれを実証し、最終的には2台の 127量子ビットの IBM Quantum Eagleプロセッサー (ibm_brisbane と ibm_sherbrooke) で実験を行いました。

スケーリングを測定するために、研究者たちはNTS（Number of Oracle Queries to Solution、解に到達するまでのオラクル・クエリ数）と呼ばれる評価尺度を定義しました。古典を用いたプレーヤーでは、平均して約 Ω(nw/2) クエリを必要としました。すなわち、問題サイズが nの場合、古典デバイスは下限（Ω）、つまりベスト・ケースのパフォーマンスで Ω(n w/2) クエリを必要とします。一方、理想的な（ノイズのない）量子を用いたプレーヤーは、この問題を解決するためにたかだかO(w log n)クエリのみを必要とします。量子プレーヤーが一貫して少ないクエリで問題を解決するということは、このオラクル・モデルで量子加速があるということを表しています。

短期的将来のデバイスで実験的に高速化を達成するために、研究者はいくつかの重要なテクニックを用いる手法を開発しました。

回路の最適化

ノイズが蓄積されすぎないように、回路の深さを抑える必要がありました。したがって、彼らは理論的なサイモンの回路を、より浅い回路にトランスパイルする際に、必要な量子論理演算の数を減らしました。「私たちは Qiskitで利用可能な機能にかなり助けられました」と Lidar氏は言います。「結果を改善するために私たちが行ったことはすべて、Qiskitの既存機能の上に築かれました。」

ダイナミック・デカップリング

また、研究者たちは、回路内のノイズを抑制するためにダイナミック・デカップリングを導入しましたが、これはおそらくワークフローの最も重要な変更点です。多くの場合、特定のアルゴリズムの実行に必要な回路で、一部の量子ビットにオペレーションが行われるのを待っている間、他の量子ビットはアイドル状態になります。この間、アイドル状態の量子ビットにはデフェージング・ノイズが発生して、結果としてデコヒーレンスになってしまう可能性があります。

ダイナミック・デカップリングでは、環境と量子ビットの不要な相互作用や、量子ビット間の不要な相互作用（クロストークとも呼ばれる）の両方から生じるノイズの影響を打ち消すために、マイクロ波パルス列を加えます。これによって実機を用いた実験結果は大幅に改善され、理想的な (ノイズのない)結果に非常に近いスケーリング曲線が得られています。

測定エラーの緩和

そして研究者たちは測定エラー緩和を適用して、ダイナミック・デカップリング後の測定プロセス中に発生するエラーを検出して修正しました。

これらの最適化とノイズ抑制の取り組みを通じて、研究者たちは、量子プレーヤーがどんな古典プレーヤーよりも指数的に速く勝つことができることを示すことができました。彼らは、w=7までのハミング・ウェイトについて、最大58量子ビットの問題サイズで高速化を観測しました。ただしハミング・ウェイトが w=8 と w=9 の場合、量子アルゴリズムは回路の深さが増加したため、優位性を示さなくなりました。

 原文ブログに掲載しているグラフは、'ibm_sherbrooke' と 'ibm_brisbane' で観測された、サイモンの問題に対するアルゴリズム的量子加速を示しています。X軸は、対数スケールで表示された問題サイズ、すなわち隠されたビット列のハミング・ウェイトが最大 wまでとしたときに可能なビット文字列の数を表します。Y軸は、正しい答えを取得するために必要なオラクルへのクエリ数を表します。黄色の点線は古典手法のスケーリングを示していますが、これは本質的に指数的に増加しています。灰色の線は理想的な (ノイズのない) 量子曲線を表し、青い線はダイナミック・デカップリングなしの量子結果を、赤い線はダイナミック・デカップリングが適用された量子結果を示します。これらの曲線から明らかなように、ダイナミック・デカップリングは量子プロセッサーの傾きを浅くし、理想的な結果をより忠実に反映します。実線は多項式スケーリングを表し、破線は対数スケーリングに表します。後者の方が優れており、古典のスケーリングよりも指数的に改善されていることを証明しています。

チームは、量子ハードウェアが成熟を続ければ、ここで示されたような高速化を、オラクルを用いるのではない量子アルゴリズムに拡張できると期待しています。特に、彼らは、古典的な限界に関する仮定に依存せず量子的優位性の検証ができる問題に関心を持っています。

「私たちは今日の量子コンピューターがすでに量子の優位性に近づいていることを、根拠を持って示しています」とLidar氏は説明します。「ここで重要なのは、他の、もっと実用的な大規模の実験結果に、より強固な基盤を与えることです。」

この研究は、短期的将来の量子ハードウェアから価値を引き出すためにアルゴリズムの発見が果たす役割の重要な例であり、量子コミュニティーに新たな推進力を与え、量子優位性を近づけるためのアルゴリズムを実験するきっかけとなっています。

この記事は英語版IBM Researchブログ「Researchers at USC demonstrate exponential quantum scaling speedup」（2025年7月16日公開、Jennifer Janechek著）を翻訳し一部更新したものです。