全部は選べない。どの企画を開く？
量子最適化は、「条件を守りながら、よい組合せを探す」ための方法です。
あなたは学園祭の担当者。下の3企画から、開催するものを選びます。AとBは同じステージを使うので、同時には開催できません。Cは別室です。
開催する企画を選んでみよう
点数は、この教材で決めた満足度の目安。費用・準備時間・相乗効果は省いた架空の問題です。
企画を選ぶと、合計点と条件を確認できます。
今日のゴールは、「採点ルールを作る → 量子で候補を探す → 答えを確かめる」という流れを、自分の言葉で説明できることです。後半では二つの探し方を比べます。プログラミングや行列計算の予備知識は不要です。
まずは説明と図を追ってみましょう。「詳しく知りたい人向け」は飛ばしても次の章へ進めます。計算で確かめたいときに開いてください。
何を選び、何を守り、何をよくする？
コンピュータに渡す前に、人が問題をはっきりさせます。
- 変数
- 決めること。A・B・Cを開催するか。開催なら1、しないなら0。
- 制約
- 守ること。AとBを同時に選ばない。
- 目的
- よくしたいこと。選んだ企画の合計点を大きくする。
この教材の数字は、左からA・B・Cの順。101は一つの開催案です。こうした離散的な選択肢の組合せから答えを探す問題を「組合せ最適化」と呼びます。
選択を、短い式で書くと
a, b, c ∈ {0, 1}それぞれ「開催する＝1、しない＝0」
a ＋ b ≤ 1AとBを選ぶ数は、合わせて1つまで
「∈」はその集合の中から選ぶこと、「≤」は以下という意味。101なら、AとBについては1＋0＝1なので条件を満たします。
配送なら「訪問する順番・到着時刻の条件・移動距離」、勤務表なら「担当者・勤務の条件・負担の偏り」。まずこの3要素を言葉にします。
満足度の点数が現実に合わなければ、計算が正確でも期待した企画は選ばれません。何を最適化するかを決めるのも大切な仕事です。
候補が増えると、探し方が大切になる
選ぶ・選ばないが1つ増えるたび、候補の数は2倍になります。
企画数を増やしたら？
8通り
条件で候補を絞る前の数。3個なら2×2×2＝8通り、20個なら1,048,576通りです。
小さな問題なら全部を調べる
今回の8通りは簡単に比べられます。正解を確かめる物差しにもなります。
大きな問題では構造を使う
普通のコンピュータにも、無理な候補を早めに除く方法や、よい案を改良する方法があります。
量子最適化は、こうした探索に量子の性質を使う選択肢です。候補の数が多いというだけで、量子が速いとは判断できません。
古典的な最適化の例：Google OR-Tools入門
よい案ほど、低いエネルギーにする
量子で扱いやすいように、「小さいほどよい」という採点にそろえます。
ここでの「エネルギー」は、候補を比べるための数値です。消費電力ではありません。合計点にマイナスをつけると、13点の案は−13になり、8点の案より低くなります。
AとBを一緒に選んだら、何点を足す？
| ABC | 開催 | 合計点 | 条件 | エネルギー |
|---|
まず罰点を2に、次に10にして比べてください。小さすぎる罰点では、条件違反で増えた点数を打ち消せません。採点の作り方が、計算の答えを左右します。
考え方の参考：D-Waveのペナルティモデル。数値例は本教材の独自設定。
QUBO：現実の条件を、量子へ渡す式にする
難しい名前でも、この例の中身は「企画ごとの点数」と「組合せへの罰点」です。
QUBO（キューボ）は Quadratic Unconstrained Binary Optimization の略で、日本語では「制約なし二次二値最適化」。この例では、0か1で選び、企画ごとの点数と2企画の組合せへの罰点を、一つの採点式にまとめる形です。「制約なし」は、守る条件を捨てる意味ではありません。条件違反への罰点を式の中に入れます。
前の章では8候補を表に並べました。でも、企画が増えるたびに全候補の表を作るのは大変です。そこで、どんな候補にも使える採点ルールを短い式で渡します。
採点のルールを、一つの式に
E ＝ −8a − 6b − 5c＋ 10ab
abはa×bのこと。どちらかが0なら0、両方が1なら1です。
A＋C（101）：−8 − 5 ＝ −13
全部（111）：−8 − 6 − 5 ＋ 10 ＝ −9
探すのは、このEが最も小さくなる組合せ。だから、−9より低い−13のA＋Cが選ばれます。
なぜ制約が10abになる？ A・Bが00・01・10ならab＝0、違反する11だけab＝1。だから10abを足せば、違反する組合せだけ採点を悪くできます。これは今回の制約に合った罰点です。
- Q：Quadratic（二次）
- 変数の積はabのように2個まで。abcのような3個の積は、この形に直接は入れません。
- U：Unconstrained（制約なし）
- 制約を無視するのではなく、罰点として式に入れ、別の制約なしで最小化します。
- B・O：Binary Optimization（二値最適化）
- 0・1の選択から、式の値が小さくなる組合せを探します。
この式が、二つの量子解法の共通の出発点
橋渡しに使うのがイジング形式。0・1を＋1・−1に言い換えた、同じ採点です。これを量子ビットのエネルギーとして表したものを問題ハミルトニアン HEと呼びます。難しい名前ですが、役割は「候補ごとにEの値を割り当てること」です。
詳しく知りたい人向け：0・1の式が、量子ビットの式になるまで
この教材では zA＝1−2a と置きます。a＝0ならzA＝＋1、a＝1なら−1。B・Cも同様です。a＝(1−zA)/2 をQUBOへ代入して整理すると、
E＝−7＋1.5zA＋0.5zB＋2.5zC＋2.5zAzB
たとえば101は(zA, zB, zC)＝(−1,＋1,−1)なので、同じ−13になります。量子の式ではzをZという演算子に置き換えます。Zは0に＋1、1に−1を対応させる操作です。
HE＝−7I＋1.5ZA＋0.5ZB＋2.5ZC＋2.5ZAZB
Iは全候補に同じ定数を足す項。最低の候補の順位は変えません。資料によって±1の割り当てが逆の場合もあるため、係数だけで比較せず定義も確認します。
ここでできたのは「問題の表現」。答えはまだ探していません。QUBOは古典的な方法でも解けます。一般の制約を表すには、補助の変数が必要な場合もあります。
形式の参考：D-Wave：QUBOとイジング模型。図と変換例は本教材の学園祭の問題から作成。
量子で変えるのは、候補の出やすさ
1回測って得られるのは、一つの開催案です。
3量子ビットに、8候補に対応する重ね合わせを用意する。
問題に応じた操作で、測定結果の確率分布を変える。
たとえば101。A＋Cという一つの候補を得る。
「重ね合わせ」は、複数の候補に対応する成分を持つ量子状態です。それぞれの成分には、確率を決める大きさに加えて「位相」という向きのような情報があります。
量子の操作で成分を混ぜると、位相に応じて強め合い・打ち消し合いが起きます。これが干渉です。よい候補の出やすさを上げるために、この性質を使います。
重ね合わせを作るだけでは、よい答えを選び出せません。全候補の答えを一度に読み出せるわけでもありません。
量子アニーリング：仕組みを徐々に変える
準備しやすい状態から始め、解きたい問題のエネルギーへ移していきます。
量子アニーリング（Quantum Annealing、略してQA）の「アニーリング」は焼きなましのこと。この教材では、準備しやすい状態から出発し、装置の働きをゆっくり問題用に変えて、低いエネルギーの候補を探す方法として捉えましょう。
まず量子アニーリングでは、混ぜる働きと問題の採点を同時に持つ量子系を用意し、その配分を徐々に変えます。
「最低」は、その時点のHで決まる
ハミルトニアンHは、量子状態のエネルギーを決める仕組みです。そのHでエネルギーが最も低い状態を最低エネルギー状態（基底状態）と呼びます。Hを変えれば、最低になる状態も変わります。
最低状態を用意しやすい
全候補の、同じ位相・同じ大きさの重ね合わせ。
どの開催案がよいかは、まだ表していない最低状態が、探したい答え
採点Eが最も低い開催案。この例では101。
採点の式を設定し、最も低い案を探す詳しく知りたい人向け：出発点の重ね合わせと、配分を表す式
HDの最低状態は、8候補を均等に重ねた状態
ここでは HD＝−(XA＋XB＋XC) を使います。Xは0と1を入れ替える働きです。このHDでは、全候補の成分が同じ向きにそろった重ね合わせ全体が最低状態になります。
「8候補それぞれが最低」という意味ではありません。最低なのは、この重ね合わせという一つの量子状態です。
詳しく知りたい人向け：なぜこの重ね合わせが最低？ −Xで確かめる
まず量子ビット1個だけを考えます。|0⟩と|1⟩は、測るとそれぞれ0と1になる状態の書き方です。次の二つの重ね合わせを比べます。
同じ位相：|+⟩
|+⟩＝(|0⟩＋|1⟩)/√2
0と1の成分を交換しても、そのまま。
X|+⟩＝|+⟩
−X|+⟩＝−1 × |+⟩
逆の位相：|−⟩
|−⟩＝(|0⟩−|1⟩)/√2
交換すると、状態全体に−1が付く。
X|−⟩＝−|−⟩
−X|−⟩＝＋1 × |−⟩
Hを作用させた結果が「数 × 元の状態」になるとき、その数がその状態のエネルギーです。量子ビット1個の−Xでは、最低値は−1。3個なら、それぞれを|+⟩にすると合計−3になり、これより低くはできません。
HDの最低状態＝|+⟩A|+⟩B|+⟩C
＝(|000⟩＋|001⟩＋…＋|111⟩)/√8
|+⟩も|−⟩も、0・1の測定確率は半分ずつです。それでも位相が違うので、−Xのエネルギーは違います。「出る確率が均等」という情報だけでは、最低状態とは判断できません。
HDを単純な形に選んだから、この最低状態がわかります。量子アニーリングの装置では、準備用の働きを強くして低温下で初期状態を用意します。回路図のHゲートを順に実行する説明とは区別してください。実機の準備には誤差もあります。
変えるのは「二つの働きの配分」
H(s) ＝ (1−s) HD ＋ s HE
HDは準備用の「混ぜる働き」、HEはQUBOから作った「問題の採点」。sは開始0から終了1までの進行度です。s＝0なら準備用だけ、s＝1なら問題の採点だけになります。
これは考え方を表す単純なモデルです。実機では二つの係数を装置のスケジュールに従って制御し、必ずしも直線的には変えません。
やってみよう：スライダーを0% → 50% → 100%へ動かして、準備用の働きが減り、問題の採点の働きが増えることを見てください。棒は二つの働きの割合で、正解が出る確率ではありません。
出発点から、問題へ
詳しく知りたい人向け：いまの配分を式で見る
H(0.00) ＝ 1.00 H_D ＋ 0.00 H_E
準備しやすい、低エネルギーの量子状態から出発します。
操作の考え方を示す模式図。棒は説明用の直線変化で、実機の制御曲線・測定確率・成功率ではありません。
状態が変わりながら、その時々の「最低」をたどる
- ① 出発：準備する用意しやすい状態から始める
全候補を均等に重ねた状態から出発。この時点では、よい案ほど出やすいわけではありません。
- ② 途中：働きを変えるその時々の低い状態をたどる
準備用と問題用の配分を変えると、低いエネルギーになる状態も変わります。その変化についていくことを目指します。
- ③ 最後：測って確かめる問題の採点が低い候補を目指す
目標の状態に到達できれば、この例では101、つまりAとCを開く案を得ます。
装置に与えるのは、採点の係数と、Hを変えるスケジュールです。その設定に従って量子状態が変化します。採点方法を知っていることと、最高点の案を知っていることは別なので、最適解を先に入力する必要はありません。
なぜ「徐々に」変えるの？
急に変えると、量子状態が変化に追いつかず、最も低い状態から外れることがあります。理想的な条件では、十分ゆっくり変えることで、その時々の最低エネルギー状態を保つことを目指せます。
途中で最低の状態と次の状態のエネルギー差（ギャップ）が小さくなると、特に慎重な制御が必要です。「何秒なら十分か」は問題によって変わり、実機では温度や雑音も影響します。長く動かすだけで必ず解決するわけではありません。
詳しく知りたい人向け：採点ルールを装置の設定にする
QUBOの点と線は、装置では何になる？
先ほどのイジング形式の「各Zの係数」は各量子ビットへの偏り、「ZAZBの係数」はA・Bを結ぶ相互作用として設定します。こうして、同じ採点Eを装置のエネルギーへ写します。実機の接続や係数の範囲に合わせた変換は、古典側の仕事です。
詳しく知りたい人向け：実機への配置と、古典的な焼きなましとの違い
装置上で直接結べない変数同士を扱うため、一つの変数を複数の物理量子ビットへ写すことがあります。これを埋め込みと呼びます。問題の変数の数と、実機で必要な量子ビット数が同じとは限りません。
古典的な焼きなまし
普通のコンピュータ上で候補を変更します。悪化する変更も一定の確率で受け入れ、その受け入れやすさを徐々に下げます。
量子アニーリング
量子系の重ね合わせやトンネル効果などを使います。装置の変化を通じて、低エネルギーの候補を得ようとします。
古典的には越えられないエネルギーの障壁を通り抜ける量子的な現象です。ただし、どんな障壁でも簡単に通れるわけではありません。これだけで高速化や最適解は保証されません。
最後に測って得た案を、何度かの実行で集めて比較します。低いエネルギーの候補でも、元の条件を守っているかの確認は必要です。
QAOA：二つの操作を組み合わせる
点数に応じて位相を変え、成分を混ぜる。その強さを調整します。
量子アニーリングでは二つの働きの配分を徐々に変えました。次に見るQAOAでは、採点に応じて位相を変える操作と、混ぜる操作をゲートで順番に行います。
QAOA（キューエーオーエー）は Quantum Approximate Optimization Algorithm の略で、「量子近似最適化アルゴリズム」です。採点に応じて位相を変える操作と、成分を混ぜる操作を組み合わせ、よい候補が出るように強さを調整します。「近似」は、いつでも最適解が得られるとは限らないことを表しています。
- 8候補を等しく準備最初はどの候補も12.5%。
- エネルギーに応じて位相を変えるこの操作だけでは、測定の確率は変わらない。
- 成分を混ぜる干渉で確率が変わる。設定次第で、よくも悪くもなる。
- 測って、候補を採点する条件を守るかどうかも確かめる。
詳しく知りたい人向け：回路図と、位相の変化を表す式
QUBOの採点は、回路のどこに入る？
紫の箱が、先ほどの式Eを使う場所です。γ（ガンマ）は採点に応じた位相変化の強さ、β（ベータ）は混ぜる強さ。下の二つのつまみと対応しています。
エネルギーが、位相の違いになる
位相の変化量 ＝ −γE
101はE＝−13なので＋13γ、111はE＝−9なので＋9γ。候補の間に4γの位相差がつきます（角度は一周すると元に戻ります）。この段階では振幅の大きさが変わらないため、確率はどちらも12.5%のままです。
次のRXで成分が混ざると、この位相差が強め合い・打ち消し合いに関わります。低いEの候補が必ず強まるわけではなく、γとβの組合せを探す必要があります。違反する候補を回路から消す操作でもありません。
やってみよう：①最初の分布 → ②位相だけ → ③調整した一例の順に押します。②では棒の高さが変わらず、③で変わることを見てください。「採点を使う」と「混ぜる」の組合せが大切です。
二つのつまみで、分布はどう変わる？
以降は罰点10に固定。前の章の罰点スライダーとは独立です。
各棒は0〜100%。青：開催可能、紫：最適案101、斜線：条件違反。灰色の目印は最初の12.5%。
平均エネルギー
最適案101の確率
条件違反の確率
詳しく知りたい人向け：この体験の計算方法
3量子ビットの理想状態をブラウザーで古典シミュレーションしています。確率は演出用の数値ではありません。角度の単位はラジアンです。
均等な初期状態に、各候補のエネルギーEに応じた位相exp(−iγE)を付け、各量子ビットへRX(2β)を適用します。表示順はABC＝q2 q1 q0。
「調整した一例」はγの61点、βの41点、計2,501設定を比較し、平均エネルギーが最小のものを選びます。連続した全設定での最適性は保証しません。この小さな模型での改善は、量子の高速化を示すものではありません。
詳しく知りたい人向け：紫の箱を、実際のゲートで開いてみる
回路図の記号：Hゲートは Hadamard gate（アダマールゲート）で、ここでは均等な重ね合わせを準備します。RXはX軸まわりの回転（Rotation around X）、RZはZ軸まわりの回転（Rotation around Z）、RZZは2量子ビットのZ×Zに対応する回転です。HゲートのHと、エネルギーを表すハミルトニアンHは別の意味です。角度のγ（ガンマ）とβ（ベータ）は、二つのつまみの名前です。
イジング形式の「単独のZの項」はRZ、「A・Bのペアの項」はRZZというゲートになります。QUBOの係数が、回路の角度へつながります。
RZ(θ)＝exp(−iθZ/2)、RZZ(θ)＝exp(−iθZZ/2)という定義なので、1.5ZAには3γ、2.5ZAZBには5γが対応します。定数−7Iが生む全候補共通の位相は、測定確率に影響しないため省略しています。行列の計算は、この入門では不要です。
ゲートの定義：IBM：RZZGate
操作の考え方：PennyLaneのQAOA入門。今回の学園祭の問題と操作画面は独自に作成。
つまみを探すのは、普通のコンピュータ
量子回路と古典計算を往復する、ハイブリッドな方法です。
最初の設定を決め、次からは結果をもとに更新。
101、001、100…と候補を得る。
次の設定を選ぶ工程へ戻る。
よく使う目標は平均エネルギーを下げること。ただし、平均がよくなることと、最適案が出る確率が上がることは同じではありません。途中で試した設定が悪くなる場合もあります。
「平均」を、調整例で確かめる
平均エネルギー ＝ 各候補の「確率 × エネルギー」の合計
0.5 × (−13) ＋ 0.5 × (−11)
＝ −12
前の章の「調整した一例」は、A＋C（−13）とB＋C（−11）がそれぞれ50%。平均−12は、一回の測定で−12の案が出るという意味ではありません。
操作の組を繰り返す「層」を増やすと、表せる状態の幅は広がります。一方、調整するつまみや回路の長さも増え、実機では誤差の影響も受けます。
量子と古典の反復：IBMのQAOAチュートリアル
共通するのは採点。探す仕組みが違う
どちらも、問題を表し、候補を得て、古典側で結果を確かめます。
| 見る点 | 量子アニーリング | QAOA |
|---|---|---|
| 使う仕組み | 量子系のエネルギーを連続的に制御 | 量子ゲートを並べた回路 |
| 主な操作 | 準備用から問題用へ変化させる | 位相と混合の操作を重ねる |
| 調整するもの | 変化の時間やスケジュールなど | 回路の角度、層数など |
| 古典側の仕事 | 問題作成、装置への配置、結果評価 | 問題作成、角度探索、結果評価 |
| 得られるもの | 確率的に出る候補 | 確率的に出る候補 |
QUBOやイジングは問題の表し方。QAOAや量子アニーリングは候補を探す方法。この二つの役割を分けると、名前が増えても整理できます。
量子最適化にはほかの方法もあります。今日は、代表的な二つを通して全体の流れをつかむことに集中しました。
一番よい答えと、出やすい答えを分けて見る
候補のよさ、条件、計算全体の手間を確認して初めて評価できます。
QAOAの候補を20回分、取り出す
先ほどのQAOAの現在の設定を使います。押すたびに新しい20回を模擬します。
まだ測っていません。まずは上のボタンを押してください。
- 開催できる？ 条件違反の割合を調べる。
- どのくらいよい？ 開催可能な中で最良の案と、その点数を見る。
- どのくらい手間がかかった？ 準備、調整、反復、結果処理まで含めて比較する。
今回なら正解の13点と比較できます。大きな問題で正解が不明なら、強い古典手法の結果や、理論的な評価基準などと比べます。「量子を使った」だけでは有用性の証拠になりません。
量子最適化の全体像を、持ち帰ろう
問題を決める → エネルギーにする → 候補を得る → 確かめる。
- 人が「よい答え」を定義する。 変数・制約・目的を明確にする。
- よい候補ほど低いエネルギーにする。 条件を罰点で表す場合は、その大きさにも注意する。
- 量子の性質で候補の出方を変える。 量子アニーリングは装置の働きを徐々に変え、QAOAは回路と普通のコンピュータの調整を繰り返します。
- 得た候補を古典側で評価する。 最適解や高速化を最初から約束するものではない。
最後の60秒：説明できる？
① 量子で全候補を一度に読めないのはなぜ？
② QAOAで普通のコンピュータは何をする？
③ よい候補が出たら、何と比較する？