【AIで量子アプリ】第5回 シフト表をQAOAで解く―的中率が半分になった原因は量子ではなかった

連載の第5回です。ここまでの4回はコインを投げるだけの、動くけれど役に立たないアプリでした。今回は業務でそのまま出てくる形の問題を解きます。シフト表の割り当てです。

そして今回は、私が一度しくじった話も一緒に書きます。同じ穴に落ちる人が多いと思うからです。

何を解くのか

4人のアルバイトがいて、出られる時間帯が決まっているとします。

条件は2つです。なるべく多くの人を採用したい。ただし同じ枠に2人以上入れてはいけない。採用1人につき-1点、枠が重なるたびに+3点として、合計がいちばん小さくなる組み合わせを探します。

4人なので16通りしかなく、総当たりで答えが出ます。先に正解を出しておいて、量子側がそこに辿り着けるかを見るという進め方にします。

総当たりの最小費用: -2
最適な割当: [(0, 1, 0, 1), (1, 0, 1, 0)]
でたらめに選んだ場合の的中率: 12.5%

AさんとCさん、またはBさんとDさんの2人を採用する形が最適でした。4人全員を入れると枠が全部かぶるので、かえって悪くなります。

QAOAで解く

QAOAは、こういう「組み合わせの中から良いものを選ぶ」問題に量子回路を当てる方法です。やることは3つです。

1. 全部の組み合わせを同時に持たせる。 4人ぶんの量子ビットにHゲートを掛けると、16通りが同時に乗った状態になります。

2. 良い組み合わせに印を付ける。 費用の式をそのまま回路にします。採用1人につき-1点はその量子ビットへの回転、枠がかぶる組への+3点は2つの量子ビットをつないだ回転になります。

3. 印の付いたほうへ寄せる。 ミキサーと呼ばれる別の回転を掛けると、良い組み合わせの出る確率が上がります。

def 実行(gamma, beta, shots):
    c = Circuit(4)
    for q in range(4):
        c.h[q]
    for q in range(4):
        c.rz(-1 * gamma)[q]
    for i, j in itertools.combinations(range(4), 2):
        if set(出られる[i]) & set(出られる[j]):
            c.cx[i, j].rz(3 * gamma)[j].cx[i, j]
    for q in range(4):
        c.rx(2 * beta)[q]
    return c.m[:].run(shots=shots)

費用の式が、そのまま回路の形になっているのが要点です。「採用は-1点」が rz(-1 \* gamma)、「枠が重なると+3点」が rz(3 \* gamma) です。問題を変えたければ、この数字を変えるだけです。

しくじった話

gammaとbetaという2つのつまみがあり、これを調整しないと当たりません。ここは量子ではなく普通の計算で探します。私は12×12の格子で総当たりし、1点あたり200回まわして良し悪しを判定しました。

最初の結果は的中率45.6%でした。でたらめの12.5%に対して3.6倍です。良い結果が出たので、そのまま記事にしようとしました。

念のためもう一度まわしたところ、27.2%でした。次は24.8%。同じコード、同じ問題です。

1回の結果を代表値として書くところでした。

揺れの正体

そこで、つまみの探し方を変えて測り直しました。1点あたりの回数を200回と2,000回にして、それぞれ見つけたつまみで5回ずつまわします。

つまみを決めたあとの5回は、どれも揺れていません。200回のときも25.0〜26.8%の中に収まっています。

揺れていたのはつまみを探す工程のほうでした。1点200回では良し悪しの判定が雑になり、たまたま悪いつまみを掴みます。そのまま本番をまわすと、的中率が半分になります。2,000回にすると、2回とも同じところに着きました。

⚠️ 「量子だから結果がばらつく」のではありません。ばらついていたのは、量子を呼ぶ前の普通の計算のほうでした。測定回数が足りないと判定を誤るという、統計としては当たり前の話です。

結果

安定したつまみでの的中率は約47%です。でたらめの12.5%に対して3.8倍になります。

ただしQAOAは「必ず正解を出す」ものではありません。47%というのは、裏を返せば半分は正解でないものが出ているということです。

使い方はこうなります。何度か回して、出てきた候補を普通の計算で採点し、いちばん良いものを採る。16通りを全部調べる代わりに、上位数通りを調べれば済みます。

問題が大きくなると、この差が効いてきます。人数がnのとき組み合わせは2のn乗で、20人なら約100万通り、30人なら約10億通りです。全部を調べるのは現実的ではありません。候補を絞り込む道具として使うのが、いまの量子コンピュータの現実的な立ち位置です。

今回やらなかったこと

実機には投げていません。シミュレータでの結果です。第3回と第4回で見たとおり、実機ではノイズで結果がずれます。今回の回路は第2回より深く、rz と cx が何度も入るので、実機ではもっと崩れます。ここは次回に確かめます。

測定結果の並びを、コードでは左から読んでいます。blueqat が返す文字列は右端が0番目の量子ビットなので、左から読むと人の順番が逆になります。今回は最適解が左右対称な2つ（0101 と 1010）だったため答えは変わりませんが、対称でない問題では取り違えます。次回は並びを明示して書きます。

つまみ探しは格子の総当たりのままにしています。実務では最適化ライブラリを使うところですが、上のしくじりが見えなくなるので、あえて残しました。

コードは全体で50行ほどです。費用の式を書き換えれば、シフト表以外の割り当て問題にもそのまま使えます。

測った環境

この記事の数字は blueqat 2.1.3・numpy 2.2.6・シミュレータで測りました。版が違うと数字も変わります。とくに blueqat 2.0.4 では測定結果の並びが逆（左端が0番目の量子ビット）になるため、上のコードをそのまま動かすと人の対応がずれます。お手元の版は次の1行で分かります。

python3 -c "import blueqat; print(blueqat.__version__)"

2.0.4 だった場合は run(shots=...) に backend="numpy" を足してください（2.1.3 以降では逆に、その指定があると動きません）。