量子線形方程式ソルバーの「読み出しボトルネック」を解消する新手法、米研究チームらが実証

ジョージア工科大学、ローレンス・バークレー国立研究所などの共同研究チームは、量子線形システムソルバーの実用化を阻んでいた「読み出しボトルネック」を解消する新手法「Hadamard Random Forest（HRF）」を発表した。この手法は、実数振幅を持つ量子状態において、必要な測定回路数を指数関数的な増加から線形的な増加へと劇的に削減するものだ。IBMの超伝導量子プロセッサー「Heron r2」上で検証され、その有効性が実証されている。

■15年間未解決だった「読み出しコスト」の課題

2009年にHarrow、Hassidim、Lloydの各氏（HHL）が線形方程式を解くための初の量子アルゴリズムを発表して以来、特定の条件下で古典的アプローチに対して指数関数的な高速化が理論上可能であるとされてきた。しかし、その恩恵を享受するには、得られた解（量子状態）を効率的に読み出す必要がある。ハードウェアから解を効率的に抽出できなければ、理論上の高速化は意味をなさない。

この「読み出しコスト」の問題は15年間にわたり量子線形システムアルゴリズムの影として存在し続けてきた。今回発表されたHRFは、これらのアルゴリズムが最も一般的に生成する「実数値」のケースにおいて、実際のハードウェア上でこの課題を直接解決した初の手法となる。

■なぜ量子コンピュータの読み出しコストは指数関数的に増大するのか

量子アルゴリズムの終了後、その出力を得るには生成された量子状態を特定する「量子状態トモグラフィー」というプロセスが必要となる。一般的なN量子ビットの量子状態を特定するには、すべての量子ビットに対して3つの標準的なパウリ基底（X、Y、Z）のあらゆる組み合わせで測定を行う必要があり、3のN乗個の異なる測定設定が生じる。

例えば、10量子ビットのシステムでは5万9,049設定、20量子ビットでは34億設定を超える。圧縮センシングや古典シャドウプロトコルなど、これまでの先進的なアプローチでも特定の構造的仮定のもとでこのスケーリングを削減してきたが、一般的な状態における指数関数的な依存性を排除することはできていなかった。

量子線形システムアルゴリズムは、解を量子状態にエンコードして出力するため、状態ベクトルを再構成するコストがアルゴリズム自体の高速化効果を打ち消してしまう懸念があった。HRFは、対象を実数状態（変分量子線形システムソルバーがターゲットとするサブクラス）に限定することで、再構成の精度を落とすことなく、測定回路数を指数関数から線形へと削減することに成功した。

■実数量子状態の重要性とHRFの仕組み

一般的なN量子ビットの量子状態は、2のN乗個の計算基底状態に対して複素数（振幅と位相）を割り当てる。実数量子状態は、すべての振幅が実数であり、位相情報が「+1」または「-1」の符号のみとなる構造的な特殊例だ。Groverの探索アルゴリズムやBernstein-Vaziraniアルゴリズム、そして変分量子線形システムソルバー群が生成する状態は、すべてこの意味で実数値である。これは狭い制限ではなく、実用的な量子優位性が最も具体的に議論されているアルゴリズムのクラスそのものである。

HRF手法はこの性質を利用する。3つのパウリ基底を走査する代わりに、Z基底で振幅の大きさを回収し、個々の量子ビットにシングルアダマールゲートを適用して符号を探索する。これにより、システムサイズに関係なく、必要な回路数は合計でN+1個（大きさに1個、符号用に量子ビットあたり1個）のみとなる。

符号の回収において、HRFは「ランダムフォレスト多数決」を採用している。サンプリングノイズによる符号の誤伝播を防ぐため、幅優先探索を用いてハイパーグラフのランダムなスパニングツリーを複数生成し、それぞれで独立して符号を割り当てた上で多数決を行う。10量子ビットの状態を用いた検証では、11本のツリーを使用することで、現実的なハードウェアノイズ下でも符号エラー率を3%未満に抑えることに成功した。

■IBMの最新ハードウェア「Heron r2」による検証

研究チームは、IBMの超伝導プロセッサー「Heron r2（ibm_fez）」上でHRFの検証を行った。従来の完全量子状態トモグラフィー（FQST）との直接比較において、5量子ビットシステムではFQSTが243設定の測定に約10分を要したのに対し、HRFはわずか6設定（N+1=6）で、測定フェーズを18秒で完了した。10量子ビットでは、FQSTは現実的な時間内での実行が不可能だったが、HRFは1分未満でサンプリングを完了した。

この圧縮された測定条件下でも、再構成の忠実度（フィデリティ）は高く維持された。10量子ビットのランダムな実数状態5つにおいて、HRFは平均89%のフィデリティを達成し、より多くの測定ショット数を使用した5量子ビットのFQST（84%）を上回った。さらに、再構成された状態を用いて、量子もつれや量子マジック、状態オーバーラップなどの非線形特性を正確に計算できることも示された。

■指数関数的に残る部分と今後の展望

本論文では、HRFが突破できない境界についても慎重に言及している。それは「ポストプロセッシング（後処理）コスト」だ。2のN乗のエントリを持つ状態ベクトルを書き出すには2のN乗のストレージが必要であり、再構成を検証するには2のN乗の演算が必要となる。この指数関数的コストは量子測定そのものではなく、その後の古典計算において発生する。

ただし、期待値やもつれ度など、解の単一の特性のみを抽出することが目的である場合、この後処理の負担はさらに軽減できる可能性があり、著者らはこれを今後の課題としている。それでも、二部ハイパーキューブ構造の並列処理能力により、近年のハードウェアに関連する量子ビット数においては十分に処理可能な範囲に収まっている。

■注目ポイントQ&A

●量子状態トモグラフィーとは何ですか？なぜコストがかかるのですか？

量子状態トモグラフィーとは、複数の異なる基底で測定を行うことで、量子状態を完全に特定するプロセスのことです。N量子ビットのシステムを完全に特定するには、すべての量子ビットにわたって3つの標準的なパウリ基底のあらゆる組み合わせ（3のN乗通り）を測定する必要があるため、量子ビット数が増えると指数関数的にコストが増大します。

●HRFが適用できる「実数量子状態」を生成するアルゴリズムには何がありますか？

Groverの探索アルゴリズム、Bernstein-Vaziraniアルゴリズム、および変分量子線形システムソルバー群などが挙げられます。これらは、出力状態の振幅がすべて実数（位相情報がプラスかマイナスの符号のみ）になる特徴を持っています。

●量子線形ソルバーの優位性を阻んでいた「読み出し問題」とは何ですか？

量子線形システムアルゴリズムは、出力を古典的なビット列ではなく量子状態としてエンコードします。この出力を利用したり検証したりするには量子状態を読み出す必要がありますが、従来のトモグラフィーでは読み出しに指数関数的なコストがかかり、アルゴリズムによる高速化効果が相殺されてしまうという問題がありました。

●HRFは現在、一般のユーザーも利用できますか？

はい。研究チームはIBMのHeron r2プロセッサー（ibm_fez）を用いて検証を行っており、コードと実験データはMITライセンスのもと、GitHubのオープンソースリポジトリ（github.com/comp-physics/Quantum-HRF-Tomography）で公開されています。IBM Quantumサービスにアクセスできる研究者であれば、すぐに利用可能です。

元記事: Quantum State Tomography Breaks Exponential Barrier for Linear Solvers