Grover探索の高速化を支えるノイズ条件:量子ビット数と反復回数で考える

紫の円形の溝に沿って、透明から曇りへ変わる緑の三日月形を並べ、桃色の球を添えた抽象画。

Grover(グローバー)探索は、並び順などの手掛かりがない候補の中から正解を探す量子アルゴリズムです。理想的には、候補がN個あるとき、正解かどうかを調べる操作の回数をNの平方根に比例する程度まで減らせます。ただし、候補が増えるほど量子回路を長く動かす必要があり、その間にノイズも積み重なります。

パキスタンのラホール経営科学大学に所属するImama Tul Birrah KhanとMuhammad Faryadは、2026年11月12日投稿のプレプリントで、この関係を複数のノイズモデルから解析しました。焦点は、正解の確率が下がることだけでなく、やり直しを含めた探索の費用がどう変わるかです。実機の速度測定ではなく、Grover探索の回路とノイズの置き方を定めた理論研究として読みます。

簡単にまとめると?

  • ノイズがあると、理想的な回数まで探索を続けるより、早めに止めてやり直す方が有利になる場合があります。
  • 量子ビットごとに独立した誤りが起きるモデルでは、回路が長くなることに加え、誤りの起こり得る量子ビットが増えることも負担になります。
  • 論文の「高速化」は主に正解判定の呼び出し回数の話です。データの読み込みや誤り訂正を含む実際の処理時間とは区別する必要があります。

一回の成功率より、やり直しを含めた費用を見る

Grover探索は、正解の状態と、それ以外を均等に重ね合わせた状態が作る二次元の平面で理解できます。正解に印を付けるオラクルと、振幅を平均のまわりで反転させる拡散操作を組み合わせ、状態を少しずつ正解の方向へ回します。この繰り返しが、正解を測定する確率を高めます。

ただし、回し続ければよいわけではありません。理想的な場合にも、正解の方向を通り過ぎると成功率は再び下がります。さらに、ノイズがある場合は反復を増やすほど状態が損なわれるため、止め時の判断が変わります。

論文は、r回のオラクル呼び出しを行った一回の探索が、確率Pで成功するとき、やり直しを含む期待呼び出し回数をr/Pとして評価しています。例えば、20回呼び出して成功率が0.8なら平均25回、30回呼び出して成功率が0.9なら約33回です。後者は一回あたりの成功率が高くても、呼び出し回数では割高です。この数字は考え方を説明する例で、論文の実験値ではありません。

正解かどうかを最後に確認する追加の呼び出しは、論文の費用式では省かれています。また、オラクルを実際にどれだけのゲートや時間で実装できるかも別に検討する必要があります。まず何を費用として数えているかをそろえることが、比較の出発点になります。

全体を一度に乱すモデルでは、回転の重みが減る

最初に解析するのは、量子ビットの集まり全体が、一定の確率で完全に混ざった状態になる「全体の脱分極ノイズ」です。これは各量子ビットが独立に誤る場合と同じではありません。数学的に厳密に解ける参照モデルとして使われています。

このモデルでは、完全に混ざった状態は量子ゲートを通しても変わりません。そのため、ノイズのある状態を、理想的なGrover探索をしている部分と、情報を失った部分に分けられます。理想的な部分が正解へ向かって回る速さは変わらず、その部分の重みが回路の深さとともに減ります。

論文の回路では、最初に一層、その後は一反復あたり三層のノイズを入れるので、r回の反復には3r+1回のノイズ機会があります。一層あたりの脱分極確率をpgとすると、理想的な部分の重みは(1−pg)3r+1です。「ノイズで回転が遅くなるから長く待つ」という説明では、この仕組みを捉えられません。

ノイズが増えると、より多く回して成功率を上げる利点より、重みを失う不利が早く大きくなり、最適な停止回数は少ない側へ移ります。全体のノイズ確率と√Nの積が小さい範囲では、平方根に比例する呼び出し回数の利点が保たれます。一方、この積が大きい領域では、固定したノイズ率に対する費用はNに比例する形へ近づきます。古典探索より定数倍だけ有利な場合は残っても、規模が増えるほど広がる平方根の優位とは異なります。

量子ビットごとの誤りでは、二つの負担が重なる

より細かく、各量子ビットが独立に誤る場合を考えると、状態の一部はGrover探索の二次元平面から外へ出ます。理想的なGrover操作は、外へ出た成分を正解へ向かって増幅せず、平面へ戻しもしません。後の誤りで戻る可能性はありますが、論文の大きなNに対する近似では、そのような再流入などを省いて解析しています。

量子ビット数をn、候補数をN = 2nとすると、誤りの機会は回路の長さだけでなくnにも比例して増えます。このモデルの主要な尺度では、一量子ビット・一層あたりに許容できる誤り率は、おおむね1/(n√N)の形で小さくする必要があります。比例係数はビット反転、位相反転、脱分極など、ノイズの種類と評価条件に依存します。

同じ負担の尺度を保つ比較 10量子ビット 12量子ビット
候補数N 1,024 4,096
理想的な反復回数の尺度√N 32 64
全体ノイズの許容率の相対値 1 約0.5
独立した局所ノイズの許容率の相対値 1 約0.42
1/√Nと1/(n√N)という論文の主要な尺度から計算した説明用の比較。反復回数の定数係数は省略。実機の許容誤り率や、有限サイズでの厳密な性能保証を示す表ではありません。

量子ビットを二つ増やすと、候補は四倍、必要な反復の尺度は二倍になります。局所ノイズでは、さらに10個から12個へと誤る場所も増えるため、許容率の相対値は10/(12×2)、つまり約0.42です。量子ビットを増やせることと、その増加を探索性能につなげられることの間には、この負担があります。

同じ一回の誤りでも、起きる場所と時点が違う

論文は、探索平面から見た位相反転とビット反転で、傷みやすい時点が異なることも示しています。位相反転は探索の初期に、ビット反転は正解へ振幅が集まった後期に大きく効きます。二つを組み合わせた誤りでは、どの時点でも大きな成分が探索平面から失われます。

ただし、物理回路での「位相反転なら常に初期が悪い」と単純化はできません。途中のアダマールゲートをまたぐと、ビット反転と位相反転の役割が入れ替わるからです。どのゲートの間に誤りを置くかまで決めて初めて、探索平面での意味が定まります。異なる研究や装置の誤り率を比べるときも、名称と数字だけでなく、誤りを数える位置を確認する必要があります。

校正のずれは、ランダムな混合とは別に積み上がる

もう一つのモデルは、操作する角度が少しずれるコヒーレント誤差です。状態をランダムに混ぜる代わりに、狙いより少し多く、あるいは少なく回してしまいます。ずれが毎回同じ向きなら、反復回数に比例して角度のずれが蓄積します。

論文は一回の操作で許す角度のずれに上限を置き、反復後に状態が入り得る角度の範囲を求めています。これは最悪の場合を含む範囲の評価であり、平均的な実機ノイズの分布を測定したものではありません。誤差が独立で平均ゼロのランダムな符号を持つ場合には、典型的な広がり方が異なるため、系統的なずれと同じ条件として扱えません。

小さな回路では、理想的な整数回数の反復がわずかに正解を通り過ぎることがあります。そのとき少し少なく回るずれが、偶然その行き過ぎを打ち消す例も示されています。しかし、それは誤差一般が探索を改善するという意味ではありません。取り得る成功率の幅と、ずれの符号まで含めて見る必要があります。

装置への適用では、何を追加で確かめるか

この研究は、既に知られていたノイズによる探索の制約を、全体の混合、探索平面からの漏れ、角度のずれという見方で整理したものです。全体の脱分極モデルの厳密な式と、局所ノイズの大きなN・低い誤り率を用いた近似は区別する必要があります。本記事では証明や数値図の独立再現までは行っていません。

実装を判断するには、オラクルや拡散操作を基本ゲートへ分解したときの深さ、相関した誤り、データの準備、測定とやり直し、誤り訂正の費用まで確かめる必要があります。論文が定めたノイズ層の数を、そのまま任意の装置の基本ゲート数とみなすことはできません。Grover探索の平方根の利点は、その実現に必要な長さの回路を、十分な精度で動かせる条件と一緒に評価するものなのです。

出典

  • Imama Tul Birrah Khan、Muhammad Faryad「Loss of the quadratic speedup in Grover search under local and coherent noise」、arXiv:2611.16398v1、2026年11月12日投稿。本文全13ページ、図1〜9、表Iを確認。PDF内の日付は11月13日。本文のノイズモデル・適用条件・式(30)、(35)、(49)、(58)を中心に参照したプレプリントの解説です。