グローバーのアルゴリズム基礎(4)：まとめと簡単な応用例

すみません、忙しくて更新が遅くなりました。
このシリーズ最後はGroverのアルゴリズムの簡単な応用を紹介します。
(自分で考えたトイプロブレムです。)

シリーズ予定：

前回までで入力の量子ビットについて、特定の状態について振幅を増幅できるようになりました。
ただこれだけだと入力Nビットの何番目のビットが立った状態を増幅すればいいというだけなので、実行する前から答えがわかっている計算しかできません。

より実用に近づけるには、「入力Nビットについてある条件を満たすビットを知りたいのだけど、予めわからないのでGroverのアルゴリズムで探索・特定したい」という課題にアプローチできるようになる必要があります。
その一例はQuantumChallenge2020の出題の通りですが、これはQRAMとかやや複雑な数理があるので、今回は単純な問題設定にして解説します。

今回の問題設定は「a + b = 0もしくは2の解となるa, bをGroverのアルゴリズムで見つける」です。
(= 1となる解は増幅されないのでやりません。
理由はわからないのですが僕の理解が追いついていないからだと思うので、わかったらまたポストします。
もしくはご存じの方がいたらコメントください、、。)

対象とする読者

量子プログラミング・量子計算に興味を持って勉強し始めたエンジニア・高校生・大学生
Groverのアルゴリズムについて改めて知りたい方など

前提とする知識

簡単な論理演算(AND, OR, NOT)が分かること
基本的な量子ゲート(H, X, CX, CCX, Z, CZ)が分かること
線形代数(行列・ベクトルの積、直積、あとできれば線形変換)が分かること
ベクトルのブラケット記法( $|0>, |1>$ など、もしくはDirac記法ともいう)が分かること
加算器の仕組みがわかること(わからなくとも入出力の結果を納得できること)

バージョン情報

Python 3.7.3
Qiskit 0.23.1

問題設定
オラクル回路の構築
計算結果
- a + b = 0を満たす解を求める
- a + b = 2を満たす解を求める
まとめ

問題設定

問題は「a + b = 0もしくは2の解となるa, bをGroverのアルゴリズムで見つける」です。
この場合の答えはa = 0, b = 0、a = 1, b = 1で人間にとってはすぐわかりますが、これをGroverのアルゴリズムで解きます。

なお、a + b = 1の解はa = 0, b = 1もしくはa = 1, b = 0でこちらも人間にとってはすぐわかりますが、Gorverのアルゴリズムで増幅されないので今回は対象外とします。
理由はわかってないのですが、複数の解が含まれる場合は増幅されないのかもしれません。
数理的に理解ができたら改めて解説しようと思います。

オラクル回路の構築

オラクル回路の演算子の確認

オラクル回路は見つけ出したい量子状態をマークして、その状態の位相を反転する回路でした。一般に量子オラクル $U_{\omega}$ はマーキングしたい状態を $| x_i^* \gt$ とし、その個数を $M$ とすると下記のように表します。

$\displaystyle{ U_{\omega} = I - 2 \sum_{i = 1}^{M} | x_i^* \gt \lt x_i^*| }$

例えばa + b = 0を満たす入力はa = 0, b = 0なので状態としては $| 00 \gt$ を、またa + b = 2を満たす入力はa = 1, b = 1なので状態としては $| 11 \gt$ をマーキング(位相を反転)するような回路を構成できれば良いということです。

条件を満たす量子状態の振幅を反転

a + b = 0を満たす解

これを満たす入力を検出する回路は下記です。
最終的にMCTゲートで検出しています。

共通関数

def XOR(qc, control1, control2, target):
    qc.cx(control2, target)
    qc.cx(control1, target)
    return qc

def AND(qc, control1, control2, target):
    qc.ccx(control1, control2, target)
    return qc
    
def adder(qc, input1, input2, carry, summ):
    """半加算器
    """
    qc = XOR(qc, input1, input2, summ)
    qc = AND(qc, input1, input2, carry)
    return qc

inputs = QuantumRegister(2, 'input')
calcs = QuantumRegister(2, 'calculation')
oracle = QuantumRegister(1, 'oracle')
c = ClassicalRegister(3)
grover = QuantumCircuit(inputs, calcs, oracle, c)

grover.h(inputs)
grover.barrier()

grover = adder(grover, inputs[0], inputs[1], calcs[1], calcs[0]) # calcs[1]がcarry calcs[0]がsum
grover.x(calcs)
grover.mct(calcs, oracle)
grover.barrier()

grover.measure(inputs, c[:2])
grover.measure(oracle, c[2])

f:id:sakumadaisuke32:20210411170136p:plain — 図1. a + b = 0 の解を検出する場合

この測定結果は下記です。

f:id:sakumadaisuke32:20210411170308p:plain — 図2. 図1の回路の測定結果

この時点ではすべて等確率ですが、MCTでoracleビットが反転しているのは入力が00の場合(図2の一番右)のみです。

a + b = 2を満たす解

同様にこれを満たす回路は下記です。

inputs = QuantumRegister(2, 'input')
calcs = QuantumRegister(2, 'calculation')
oracle = QuantumRegister(1, 'oracle')
c = ClassicalRegister(3)
grover = QuantumCircuit(inputs, calcs, oracle, c)

grover.h(inputs)
grover.barrier()

grover = adder(grover, inputs[0], inputs[1], calcs[1], calcs[0]) # calcs[1]がcarry calcs[0]がsum
grover.x(calcs[0])
grover.mct(calcs, oracle)
grover.barrier()

grover.measure(inputs, c[:2])
grover.measure(oracle, c[2])

f:id:sakumadaisuke32:20210411165525p:plain — 図3. a + b = 2 の解を検出する場合

この測定結果は下記です。

f:id:sakumadaisuke32:20210411165633p:plain — 図4. 図3の回路の測定結果

この時点ではすべて等確率ですが、MCTでoracleビットが反転しているのは入力が11の場合(図4の一番右)のみです。

逆演算(Uncomputation)

満たす解を確認するだけだったらここまでで良いのですが、Groverのアルゴリズムを実行するには、逆演算(Uncomputation)という処理が必要です。
測定したい入力のビット(inputs)とオラクルのビット(oracle)以外のancilaとして用いたビット(ここではcaluculation)へ掛けたゲートの効果を「無かったことにする」処理です。
掛けた時と逆順にゲートを掛ければよいです。

inputs = QuantumRegister(2, 'input')
calcs = QuantumRegister(2, 'calculation')
oracle = QuantumRegister(1, 'oracle')
c = ClassicalRegister(2, 'output')

grover = QuantumCircuit(inputs, calcs, oracle, c)
grover.h(inputs)
grover.barrier()

grover = adder(grover, inputs[0], inputs[1], calcs[1], calcs[0]) # calcs[1]がcarry calcs[0]がsum
grover.x(calcs[0])
grover.mct(calcs, oracle)
grover.x(calcs[0])
grover = adder_r(grover, inputs[0], inputs[1], calcs[1], calcs[0])

f:id:sakumadaisuke32:20210411171433p:plain — 図5. 逆演算をかけた場合

逆演算そのものの数理的な解説は「量子コンピューティング量子アルゴリズムから機械学習まで(嶋田義皓著)」の2.5節を参照してください。ここでは実際に逆演算を仮にしないまま位相反転増幅した場合にうまくいかないことを示します。

計算する回路全体の構成は下記です。

inputs = QuantumRegister(2, 'input')
calcs = QuantumRegister(2, 'calculation')
oracle = QuantumRegister(1, 'oracle')
outputs = ClassicalRegister(2, 'output')
grover = QuantumCircuit(inputs, calcs, oracle, outputs)

grover.h(inputs)
grover.x(oracle)
grover.h(oracle)
grover.barrier()

grover = adder(grover, inputs[0], inputs[1], calcs[1], calcs[0]) # calcs[1]がcarry calcs[0]がsum

grover.x(calcs[0])
grover.mct(calcs, oracle)
grover.barrier()

grover.h(oracle)
grover.x(oracle)

grover.h(inputs)
grover.x(inputs)
grover.barrier(inputs)
grover.h(inputs[1])
grover.cx(inputs[0], inputs[1])
grover.h(inputs[1])
grover.barrier(inputs)
grover.x(inputs)
grover.h(inputs)

grover.measure(inputs, outputs)

f:id:sakumadaisuke32:20210417121428p:plain — 図6. 逆演算しなかった場合

図6の回路でマーキングした直後の量子状態は下記です。(計算はご自身でやってみてください。)

$\begin{aligned} |absco \gt &= \frac{1}{2} ( |00 \gt_{ab} |10 \gt_{sc} + |01 \gt_{ab} |00 \gt_{sc} + |10 \gt_{ab} |00 \gt_{sc} - |11 \gt_{ab} |11 \gt_{sc}) \\ &\otimes \frac{1}{\sqrt{2}} ( |0 \gt_{o} - |1\gt_{o}) \end{aligned}$

ここで、 $a$ はinput0, $b$ はinput1, $s$ はsum(calculation0), $c$ はcarry(calculation1), そして $o$ はoracleの各ビットを示します。求めたい入力である

$\displaystyle{ |11 \gt_{ab} |11 \gt_{sc} }$

の状態がマーキングされています。

そして、この後位相反転増幅した後の最終状態は下記です。

$\begin{aligned} |absco \gt &= \frac{1}{4} \{ (- |00 \gt_{ab} + |01 \gt_{ab} + |10 \gt_{ab} + |11 \gt_{ab}) |10 \gt_{sc} \\ &+ 2(|00 \gt_{ab} + |11 \gt_{ab}) |00 \gt_{sc} \\ &-2 |00 \gt_{ab} |11 \gt_{sc} \} \otimes |0 \gt_{o} \end{aligned}$

sumとcarryとのエンタングルメントを解除していないので、各項が分かれたままきれいにまとまらなくなってしまっています。これを $|ab \gt$ を中心に整理しなおすと

$\begin{aligned} |absco \gt &= \frac{1}{4} \{ (|00 \gt_{ab} (- |10 \gt_{sc} + 2|00 \gt_{sc} - 2 |11 \gt_{sc}) \\ &+ |01 \gt_{ab} |10 \gt_{sc} \\ &+ |10 \gt_{ab} |10 \gt_{sc}\\ &+ |11 \gt_{ab} (|10 \gt_{sc} + 2 |00 \gt_{sc}) \} \otimes |0 \gt_{o} \\ \end{aligned}$

となり、[tex: |00 \gt{ab}, |11 \gt{ab}]の確率振幅の大きさが[tex: |01 \gt{ab}, |10 \gt{ab}]のものより少し大きくなるということになります。

実際に測定すると下図となり、推測した通りの傾向になり、そして解を得ることができません。

f:id:sakumadaisuke32:20210417124847p:plain — 図7. 逆演算しなかった場合の確率分布

逆演算の必要性を理解していただけると幸いです。

計算結果

逆演算と位相反転増幅も含めた全体の回路は下記です。

a + b = 0を満たす解を求める

inputs = QuantumRegister(2, 'input')
calcs = QuantumRegister(2, 'calculation')
oracle = QuantumRegister(1, 'oracle')
outputs = ClassicalRegister(2, 'output')
grover = QuantumCircuit(inputs, calcs, oracle, outputs)

grover.h(inputs)
grover.x(oracle)
grover.h(oracle)
grover.barrier()

grover = adder(grover, inputs[0], inputs[1], calcs[1], calcs[0]) # calcs[1]がcarry calcs[0]がsum

grover.x(calcs)
grover.mct(calcs, oracle)
grover.x(calcs)

grover = adder_r(grover, inputs[0], inputs[1], calcs[1], calcs[0])
grover.barrier()

grover.h(oracle)
grover.x(oracle)

grover.h(inputs)
grover.x(inputs)
grover.barrier(inputs)
grover.h(inputs[1])
grover.cx(inputs[0], inputs[1])
grover.h(inputs[1])
grover.barrier(inputs)
grover.x(inputs)
grover.h(inputs)

grover.measure(inputs, outputs)

f:id:sakumadaisuke32:20210411172142p:plain — 図8. a + b = 0を満たす解を求める回路

この測定結果は下図で、確かに $| 00 \gt$ が増幅されています。

f:id:sakumadaisuke32:20210411172252p:plain — 図9. 図8の回路の測定結果

a + b = 2を満たす解を求める

inputs = QuantumRegister(2, 'input')
calcs = QuantumRegister(2, 'calculation')
oracle = QuantumRegister(1, 'oracle')
outputs = ClassicalRegister(2, 'output')
grover = QuantumCircuit(inputs, calcs, oracle, outputs)

grover.h(inputs)
grover.x(oracle)
grover.h(oracle)
grover.barrier()

grover = adder(grover, inputs[0], inputs[1], calcs[1], calcs[0]) # calcs[1]がcarry calcs[0]がsum

grover.x(calcs[0])
grover.mct(calcs, oracle)
grover.x(calcs[0])

grover = adder_r(grover, inputs[0], inputs[1], calcs[1], calcs[0])
grover.barrier()

grover.h(oracle)
grover.x(oracle)

grover.h(inputs)
grover.x(inputs)
grover.barrier(inputs)
grover.h(inputs[1])
grover.cx(inputs[0], inputs[1])
grover.h(inputs[1])
grover.barrier(inputs)
grover.x(inputs)
grover.h(inputs)

grover.measure(inputs, outputs)