Grover探索の制約対応初期化、候補を絞る効果と準備コストを比べる

量子計算で候補から正解を探すGrover（グローバー）探索は、正解を一つずつ確かめる場合より、必要な問い合わせ回数を減らせます。ただし、最初から条件に合わない候補まで同じ重みで含めていれば、その候補にも量子状態を割り当てることになります。

韓国のETRI、KIST、慶熙大学、KISTIに所属するEunok Baeらは、問題の制約を初期状態に組み込み、探索する候補を絞る方法を調べました。2026年11月3日改訂の論文で焦点となるのは、反復が減る利益と、特別な初期状態を作る回路の負担の釣り合いです。

初期状態に条件を入れると、何が変わるのか

二値変数がn個あれば、0と1の並びは2のn乗通りあります。標準的なGrover探索では、これらを一様な重ね合わせとして準備します。ここでの一様とは、測定したときに各候補が同じ確率で得られる、という意味です。

続いて、正解を判定する回路「オラクル」で正解の位相を反転し、初期状態を基準とする反射操作を組み合わせます。この反復によって正解を測定する確率を高めます。候補数に対して正解が少ないほど、多くの反復が必要になります。

そこで、すでに分かっている条件を準備に使います。例えば四つの二値変数について、1になる変数がちょうど一つなら、許される並びは0001、0010、0100、1000の四つです。16通りすべてを含める代わりに、この四つだけを等しく重ね合わせます。一定個数の1を持つ並びを一様に重ねた状態を、Dicke（ディッケ）状態と呼びます。

大切なのは、外す候補が正解ではないと分かっていることです。初期状態に含めなかった候補は、この方法の反復では探索できません。条件を強くしすぎて正解を落とすと、反復を減らせても別の問題を解くことになります。論文は、絞り込んだ候補集合にも、元の正解がすべて含まれることを前提にしています。

準備の負担は、最初の一回で終わらない

通常の一様な初期状態は、各量子ビットへのHadamard（アダマール）ゲートで作れます。制約を満たす並びだけを重ねるには、量子ビット間を結び付ける操作などが必要です。候補が減る分だけ、準備は複雑になり得ます。

さらに、Grover探索の反射操作は、用意した初期状態に合わせて変える必要があります。論文では、状態の準備回路をV、逆向きの回路をVの逆操作として、反射を「逆準備→すべて0の状態を基準とする反射→準備」の順に実装します。したがって、各反復に準備と逆準備の両方が入ります。

論文の費用モデルを言葉にすると、全体の回路資源は初回の準備費用＋反復回数×（オラクル費用＋基準の反射費用＋準備費用の2倍）です。準備と逆準備の費用が同じというモデルで、ゲート数、二量子ビットゲート数、回路の深さをそれぞれ比較します。問い合わせ回数だけが少なくても、この合計が減るとは限りません。

初期状態で確実に満たした条件については、オラクルの判定を省ける場合もあります。ただし、それは具体的な判定回路の設計次第です。同じオラクルを使う比較と、条件の移し替えによってオラクル自体も簡単にした比較は、分けて確かめる必要があります。

重なる制約は、残す条件を慎重に選ぶ

変数を共有しない複数の条件なら、それぞれのDicke状態を別の量子ビット群に準備し、組み合わせられます。条件に使わない変数には通常の一様な重ね合わせを使います。

難しいのは、二つの条件が同じ変数を使う場合です。先に使った変数を取り除き、残りにも元の条件をそのまま課すと、正解を消すおそれがあります。例えば「三つのうち1は一つ」という条件で、一つの変数を別の群に移したなら、残り二つの1の個数は0か1です。残りにも「必ず一つ」と決めてしまうと、移した変数だけが1である正解を落としてしまいます。

論文は、このような重なりに対し、残った変数に許す個数の範囲を広げる方法を使います。絞り込みは弱くなり、一部の不適格な候補が残りますが、正解を残せます。最終的な正否はオラクルで確認します。また、どの条件を先に選ぶかには簡便な貪欲法を用いており、最も費用が小さい選び方を必ず見つける手順ではありません。

10変数の例では、1024候補が96、48へ減る

具体例は、複数の部分集合からいくつかを選び、すべての要素をちょうど一回ずつ覆う「完全被覆問題」です。論文の例には10個の選択肢があり、それぞれを選ぶかどうかを二値変数で表します。解は一つと分かっている設定です。

最初の候補数は2の10乗で1024通りです。変数を共有しない二つの条件を準備に使うと、一方の群の選び方が4通り、他方が3通り、残り三変数が8通りとなり、4×3×8＝96通りになります。さらに、重なりを整理した残り三変数に「1は0個か1個」を許すと、その部分は8通りから4通りへ減り、全体は48通りになります。

論文の表2に基づく比較です。候補数と反復回数の減少を示すもので、実行時間が25分の5になったことを意味しません。各方式で準備や反射の回路が異なるため、回路全体の費用を数える必要があります。

シミュレーションで確かめた範囲と、残る比較

研究ではIBMの量子回路開発ソフトウェアQiskitを使い、この例のシミュレーションを行っています。ノイズを入れる計算では、一量子ビット操作に10の−5乗、二量子ビット操作に10の−4乗の確率で脱分極ノイズを加えています。各条件を20回実行し、それぞれ1000回の測定に相当する試行を行った結果です。

ただし、このシミュレーションではオラクルを理想的な操作として扱い、ノイズの対象から外しています。初期化と反射に関わる回路の違いを調べる設定であり、判定回路を含む実機全体の誤り率を評価したものではありません。

論文には100量子ビットの場合の資源比較もありますが、これは回路構成から費用を数えた解析です。100量子ビットの実機実験や、その全状態を用いた同じ規模のノイズシミュレーションではありません。また、ゲートをどの基本操作へ分解するかによって数え方は変わります。

最適反復回数の評価では、正解の個数を既知としています。実際の課題で個数が分からなければ、推定や反復回数を調節する仕組みの負担も必要になります。費用が下がることを保証する論文の十分条件も、扱う制約、候補と正解の数の関係、オラクル費用などに依存します。あらゆる制約を追加すれば必ず速くなる、という保証ではありません。

この方法を比較するときは、まず正解を落とさず候補を絞れているかを確かめ、次に準備・逆準備を含む各反復の費用を数えます。そのうえで、オラクルの扱い、正解数の前提、ノイズの対象をそろえる。制約を利用する価値は、候補の少なさと、そこへ探索を限定するための回路の両方から判断できます。

Qiskitを開発する企業の事業や量子計算への取り組みは、CyclewaveのIBMの企業解説で紹介しています。

出典

• Eunok Bae、Jeonghyeon Shin、Minjin Choi「Reducing Circuit Resources in Grover’s Algorithm via Constraint-Aware Initialization」、arXiv:2601.17725v2、2026年11月3日改訂。
• 同論文のPDF。初期状態と反射：2〜7ページ、費用の条件と解析：7〜12ページ、完全被覆の例・ノイズ設定・表2：13〜15ページ。本記事はこの19ページのarXiv版を対象としています。