量子計算の操作をもう1回繰り返せば、よい答えが出る確率はさらに高くなるのでしょうか。量子振幅増幅では、そうとは限りません。うまく止めれば成功確率を大きくできる一方、同じ操作を続けると、いったん高くなった確率が下がることがあります。
鍵になるのは、確率を少しずつ足しているのではなく、量子状態を回転させていることです。ここでは4候補から条件を満たす1個を探す説明用の例を使い、25%だった成功確率が1回の反復で100%、もう1回で25%になる過程を追います。実機の測定結果ではなく、誤差のない理想的な演算から計算した値です。[1]
簡単にまとめると？
- 量子振幅増幅は、条件を満たす状態の位相を変える操作と、準備した状態を基準にする操作を組み合わせます。位相を変えるだけでは、測定確率は変わりません。
- 成功確率は反復回数に対して振動します。4候補中1個が正解の理想例では、0回・1回・2回で25%・100%・25%となり、反復のしすぎが逆効果になります。
- 初期の成功確率が未知なら、反復回数の選び方も必要です。理論上の呼び出し回数の削減と、装置で答えが得られるまでの時間は分けて評価します。
探したい答えを、判定できる条件として用意する
候補は作れるものの、そのうち条件を満たすものが少ない場面を考えます。候補を出す手続きをA、出てきた候補が条件を満たすかを調べる判定をχとします。χは、合格なら1、不合格なら0を返す関数です。「合格」を判断する基準は、問題の側で与えておきます。
たとえば、制約を満たす組合せを探すなら、制約に違反していないかを計算できる必要があります。判定できることと、合格する候補を最初から知っていることは別です。ただし、その判定を量子回路の中で使える形にする費用まで無料になるわけではありません。
量子振幅増幅で使うAは、途中で測定を行わず、逆向きの操作A−1も実行できる状態準備です。Aを1回実行して測定したとき、合格する候補が出る確率をaと呼びます。初期状態が合格する候補をまったく含まずa＝0なら、以下で扱う標準の振幅増幅を繰り返しても、その候補の確率は増えません。[1]
符号を変えてから、干渉で測定確率を変える
説明用に、00・01・10・11の4候補が同じ重みで並び、11だけが合格する場合を使います。それぞれの振幅は1/2です。振幅は確率そのものではなく、確率を決める数で、一般には複素数になります。この例では実数だけで計算でき、各候補の測定確率は振幅の二乗、つまり1/4です。
最初に、合格する11の振幅だけを1/2から−1/2へ変えます。これは位相をπだけ変える操作です。二乗するとどちらも1/4なので、この段階では、11を測定する確率はまだ25%です。符号の違いは、次の操作で振幅を干渉させたときに効いてきます。
一様な重ね合わせから始めたこの例では、続く操作は「各振幅を平均値の反対側へ移す」と計算できます。符号を変えた後の平均振幅は、(1/2＋1/2＋1/2−1/2)÷4＝1/4です。新しい振幅を「平均の2倍−元の振幅」で求めると、不合格の3候補は0、合格の11は1になります。
| 段階 | 00・01・10の各振幅 | 11の振幅 |
|---|---|---|
| 最初の状態準備 | 1/2 | 1/2 |
| 11の符号を反転 | 1/2 | −1/2 |
| 平均を基準に反転 | 0 | 1 |
この2つの操作を合わせた1回の反復をQと書きます。一般の状態準備Aでは、単純な候補ごとの平均値ではなく、Aが準備した状態を基準にした反射を使います。したがって、この「平均の反対側」という計算を、一様でない状態にそのまま当てはめることはできません。Grover探索は、一様な重ね合わせを使う振幅増幅の代表例です。[1]
正解に集中した後も、同じ操作は止まってくれない
ここで測定すれば、理想的には11が必ず出ます。ところが測定せずに、もう1回Qを実行するとどうなるでしょうか。11の振幅1が−1になり、他の3候補は0のままです。平均は−1/4になるので、平均を基準に反転した後は、不合格の3候補がそれぞれ−1/2、合格の11が1/2になります。
振幅の符号は最初と異なりますが、二乗した確率はすべて1/4です。せっかく11に集中した状態が、測定確率の上ではまた4候補へ広がったことになります。成功確率が下がるのは、実機の雑音が原因でなくても起こります。理想的な量子演算そのものが、同じ向きへ進み続けるためです。
この動きをまとめるには、合格側と不合格側の2方向で状態を考えると見通しがよくなります。初期の成功確率をa＝sin2θと表すと、Qをk回繰り返した後の成功確率は次の式になります。ここで0≦θ≦π/2です。[1]
P(k)＝sin2((2k＋1)θ)
初期の角度θから、1回ごとに2θずつ進みます。合格側に近づく間は確率が上がりますが、通り過ぎれば下がります。今回のa＝1/4ではθ＝π/6、つまり30度です。0回・1回・2回は30度・90度・150度に対応し、確率は25%・100%・25%となります。
なお、すべてのaでちょうど100%に届くとは限りません。kは整数なので、合格側を最も向く角度の前後で止めることになります。また、ここで示した振動は、同じ標準のQを反復する方法についての説明です。異なる位相の選び方を使う改良まで、すべて同じ振る舞いと決めつけるものではありません。
「成功確率が高い」と「安く答えが出る」を分ける
反復を増やすほど、状態を保ったまま実行する回路も長くなります。標準のQは、条件付きの位相反転に加え、AとA−1をそれぞれ1回使います。初期のAも含めれば、Qをk回行う1試行は、AとA−1を合計2k＋1回呼び出します。[1]
今回の例で、毎回同じkを使い、測定して不合格なら初期状態から独立にやり直すとします。1試行の成功確率をP(k)とすると、最初の合格までの平均試行数は1/P(k)です。そこへ1試行の呼び出し回数を掛けると、次の比較になります。
| Qの反復 | 成功確率 | 1試行のA・A−1呼び出し | 合格までの平均呼び出し |
|---|---|---|---|
| 0回 | 25% | 1回 | 4回 |
| 1回 | 100% | 3回 | 3回 |
| 2回 | 25% | 5回 | 20回 |
2回まで反復した場合は、1試行が長くなったうえに成功確率が下がり、やり直しも必要になります。一方で「4回が3回になったから、実際の所要時間も4分の3」とは言えません。Aと逆操作の実装、合格判定の回路、測定・再準備の時間が異なるからです。この小さな例は反復の選び方を示すもので、装置の優位性を実証した比較ではありません。
原論文の平方根の改善も、基本的にはこうした呼び出し回数の議論です。小さいaに対し、候補をそのまま作って調べる方法は平均1/a回の試行を要しますが、条件を満たす振幅増幅では、AとA−1の利用回数を1/√aに比例する規模へ減らせます。入力の準備や判定が重い場合は、その中身を含む比較が必要です。[1]
初期の成功確率が分からなければ、止め方も工夫する
aが分かればθを求め、成功確率が高くなる整数kを選べます。しかし、合格する候補がどのくらいあるか分からない問題では、そのままでは適切な反復回数も分かりません。未知のaを既知として、理想的な止めどころだけを比較すると、実際の探索に必要な手間を落としてしまいます。
原論文のQSearchは、反復回数を固定せずに選ぶ方法です。まず増幅しない状態でも候補を測り、合格なら終了します。合格しなければ新しく状態を準備し、1からMまでの整数を一様に選んで、その回数だけQを反復します。それでも合格しなければ、Mの範囲を段階的に広げて再試行します。[1]
同じ回数で毎回行き過ぎることを避け、まだ分からない適切な反復規模を探す考え方です。ここでも、測定で得た候補が合格かどうかを判定できなければ、成功した時点で止められません。原論文はa＞0のもとで期待呼び出し回数が1/√aに比例することを示していますが、a＝0なら、この手順は停止しません。「見つからない」と「存在しない」の判定まで自動的に解決する手続きではありません。
そのため、振幅増幅の比較では、初期の成功確率を既知とするのか、未知のまま探すのか、条件を満たす候補の存在を保証するのかを揃えることが大切です。同じ反復回数でも、初期状態と合格条件が違えば、成功確率も止めるべき位置も変わります。
確率の山だけでなく、1試行の長さまで見る
振幅増幅を使う説明や実装を見るときは、まず「何を合格とし、それをどう判定するか」を確かめます。次に、状態準備Aを逆向きにも実行できるか、反復回数を何から決めたかを見ます。最後に、成功確率だけでなく、1試行の回路と、失敗後のやり直しを含む費用を比べます。
今回の4候補では、1回で止めることに意味がありました。量子振幅増幅の強みは、操作を長く続ければ確率が積み上がることではありません。干渉で状態の向きを変え、求める候補が出やすいところで測定することにあります。その止めどころを、与えられた知識と費用の範囲で選ぶのが、アルゴリズムを使う際の大切な部分です。
参考資料
- Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp「Quantum Amplitude Amplification and Estimation」（2000年5月15日公開、arXiv:quant-ph/0005055v1）。§2、式(1)・(5)・(8)、定理2・3とQSearch、PDF pp.5–9を参照。本文の4候補・反復回数の表とグラフは、この理論式に基づく独自の説明例です。