科学しよう

量子計算のプログラミングの解説をメインに、データサイエンス・機械学習について勉強したことをご紹介します

MENU

グローバーのアルゴリズム基礎(1):オラクル回路

今回からは4回のシリーズでGrover探索アルゴリズムの解説をします。 Grover探索アルゴリズムもQuantumChallenge2020に出題され、仕組みと使い方を覚えると汎用性が高いアルゴリズムです。 QuantumChallenge2020公式

GroverのアルゴリズムはDeutsch–Jozsaアルゴリズム・Shorのアルゴリズムと並んで量子コンピュータの構想初期から注目され続けている量子アルゴリズムです。 公式をはじめとして様々なところで既に解説はされているのですが、数式と実装する量子回路との対応、どうしてそのゲートを使うのかなどの理由も深堀し直して初学者の人がイチからコーディングできるように、また応用を利かせられるような解説を目指します。

次の予定でいます。

  1. ラクル回路 << 今回
  2. 位相反転増幅回路
  3. 3量子ビット以上の場合
  4. まとめと簡単な応用例

今回は「オラクル回路」という、探索する状態の選択肢の中から「これが答えだ」「これを見つけたい」という状態を見つけてマーキングする回路です。 ちなみに「オラクル(Oracle)」とは日本語で「神託(神のお告げ)」(Wikipedia)ということで、与えられた問題の答えを予め知っているから、というのが言葉の由来です。

対象とする読者

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

前提とする知識

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

バージョン情報

目次

Groverのアルゴリズムの概要

概要の説明はQuantumChallenge2020問題の前半の解説(日本語)が絵も有ってまとまっていて良いと思います。

ここでは詳細な説明は割愛しますが、要素は次の2点です。

  • 答えに対応する状態をマーキング
  • そのマーキングされた状態の確率だけを増幅

最終的に状態を測定すると探していた状態が100%に近い確率で測定される、というものです。

簡略した量子回路は下記で書かれます。

f:id:sakumadaisuke32:20210214150611p:plain
図1. Grover回路の概要(QuantumChallenge2020の問題より)

この図の意味

2量子ビットの場合は下記が実装の1例になります。

f:id:sakumadaisuke32:20210214152132p:plain
図2. 2量子ビットGroverアルゴリズムの実装例

以降ではオラクル回路をどうして上図のように実装するのか、数式と量子回路の対応を確かめます。

ラクル回路の役割と仕組み

役割と仕組み

f:id:sakumadaisuke32:20210214152640p:plain
図3. オラクル回路の役割(QuantumChallenge2020の問題より)

左右の図について説明します。

 |w>が探している状態です。

 |s>が探索する全状態の重ね合わせ状態で、下式です。

\displaystyle{
|s> = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1}{|i>}
}

 Nが状態の数です。
上式は一般式ですが、
例えば2量子ビットの場合は取りうる全状態は  |00>, |01>, |10>, |11> の 22 = 4 個、
3量子ビットの場合は  |000>, |001>, |010>, |011>, |100>, |101>, |110>, |111> の 23 = 8 個です。
上式とは  |i=0> = |00>, |i=1> = |01>, |i=2> = |10>, |i=3> = |11> という風に対応します。

左の図では、 |w>に直交する( |w>との内積がゼロになる)状態を仮に |s'>としています。
( |s>の重ね合わせの内、 |w>の係数がゼロな状態が相当)
この状態(ベクトル)を軸に反転した状態を |\psi >とします。
この結果、 |\Psi _{t'}> |s>の重ね合わせの内、 |w>の係数だけマイナスになったものです。

この |\Psi _{t'} >の状態の確率振幅を図示したのが右の図です。
状態 |w>の確率振幅だけが他と絶対値は同じで符号が反転しています。

例えば2量子ビットの場合

\displaystyle{
|s> = \frac{1}{2} (|00> + |01> + |10> + |11>)
}

 |w> = |11>の時、

\displaystyle{
|\Psi_{t'}> = \frac{1}{2} (|00> + |01> + |10> - |11>)
}

です。

というように、全状態の重ね合わせ状態 |s>から探している状態 |w>の確率振幅の符号を反転(=位相を反転)させた |\Psi_{t'}>に変換することがオラクル回路の役割です。
またこの目的の状態の位相を反転することを「マーキングする」と言うことがあります。

ラクル回路の実装例

では数学的にやりたいことはわかったので、量子回路で実装しましょう。

やりたいこと:

  • 取りうるすべての状態を生成
  • 答えの状態の位相を反転するようにゲート操作

図2に対応する実装は下記です。

qr = QuantumRegister(2, 'data')
cr = ClassicalRegister(2, 'output')
grover = QuantumCircuit(qr, cr)

grover.h(qr)
grover.cz(qr[0], qr[1])
grover.measure(qr, cr)

grover.draw(output='mpl')

f:id:sakumadaisuke32:20210214182626p:plain
図4. 図2に対応するオラクル回路

この時の状態ベクトルの確率振幅を確認しましょう。
4つ目の状態だけ符号がマイナスになっていますね!
ということで、目指した状態をこの回路で作れることは分かりました。

qr = QuantumRegister(2, 'data')
cr = ClassicalRegister(2, 'output')
grover = QuantumCircuit(qr, cr)

grover.h(qr)
grover.cz(qr[0], qr[1])

backend = Aer.get_backend('statevector_simulator')
job = execute(grover, backend=backend)
result = job.result()

state = result.get_statevector()
print(state)

>> array([ 0.5+0.j,  0.5+0.j,  0.5+0.j, -0.5+0.j])

ではこの時この回路では何が起きているのか、また |11>以外の状態の位相を反転させたいときにはどうしたらいいのか確認しましょう。

ラクル回路の中身

まずはHゲート(アダマールゲート)は取りうる全状態の重ね合わせを作ります。

qr = QuantumRegister(2, 'data')
cr = ClassicalRegister(2, 'output')
grover = QuantumCircuit(qr, cr)

grover.h(qr)

backend = Aer.get_backend('statevector_simulator')
job = execute(grover, backend=backend)
result = job.result()

state = result.get_statevector()
print(state)
grover.draw(output='mpl')

>> [0.5+0.j 0.5+0.j 0.5+0.j 0.5+0.j]

f:id:sakumadaisuke32:20210214184817p:plain
図5. 全状態の重ね合わせの生成

f:id:sakumadaisuke32:20210214190136p:plain
図6. 図5の時のBloch球

Bloch球では2つのビットとも (1 / \sqrt{2}) (|0> + |1>)になっていて、また確率振幅も等しいですね。

つまり、下記の数式の状態になっています。


\begin{aligned}
H|0>_0 \otimes H|0>_1 &= \frac{1}{\sqrt{2}} (|0>_0 + |1>_0)\otimes \frac{1}{\sqrt{2}} (|0>_1 + |1>_1) \\
&= \frac{1}{2} (|00> + |01> + |10> + |11>) \\
&\equiv |s>
\end{aligned}

これはよくやるので多分当たり前になっていますが、「全状態の重ね合わせを作りたい」という目的に対して、Hゲートで1量子ビットの重ね合わせ状態を作り、それぞれの量子ビットを相互作用させず独立にしておくことで直積(総当たりの組み合わせ)で表現できるようにすることで目的を達成させている例です。

ではこの後のCZゲートが何しているのか確認しましょう。
そもそもCZゲートは制御ビットが |1>の時に標的ビットにZゲートを掛ける(位相を反転する)というものです。

制御ビットが |0>の場合
分かりやすくするため、標的ビットにはHゲートを掛けておきます。

qr = QuantumRegister(2, 'data')
qc = QuantumCircuit(qr)

qc.h(qr[1])
qc.cz(qr[0], qr[1])

backend = Aer.get_backend('statevector_simulator')
job = execute(qc, backend=backend)
result = job.result()

state = result.get_statevector()
print(state)
qc.draw(output='mpl')
>> [ 0.70710678+0.j  0.        +0.j  0.70710678+0.j -0.        +0.j]

f:id:sakumadaisuke32:20210214191608p:plain
図7. 制御ビットが |0>の場合のCZ

f:id:sakumadaisuke32:20210214191740p:plain
図8. 図7の状態のBloch球

標的ビットの状態ベクトルに変化はないですね。
ちなみに確率振幅の配列は左から順に |00>, |10>, |01>, |11>です。
だから数式としては下記の状態になって、Zゲートがかからずそのままということです。


\begin{aligned}
|0>_0 \otimes H|0>_1 &\stackrel{\mathrm{CZ}}{\longrightarrow} |0>_0 \otimes \frac{1}{\sqrt{2}} \left\{ |0>_1 +  \exp^{i (\phi + 0 \dot \pi)}|1>_1 \right\} \\
&= \frac{1}{\sqrt{2}} (|00> + |01>)
\end{aligned}

制御ビットが |1>の場合

qr = QuantumRegister(2, 'data')
qc = QuantumCircuit(qr)

qc.x(qr[0])
qc.h(qr[1])
qc.cz(qr[0], qr[1])

backend = Aer.get_backend('statevector_simulator')
job = execute(qc, backend=backend)
result = job.result()

state = result.get_statevector()
print(state)
qc.draw(output='mpl')
>> [ 0.        +0.j  0.70710678+0.j  0.        +0.j -0.70710678+0.j]

f:id:sakumadaisuke32:20210214192456p:plain
図9. 制御ビットが |1>の時のCZ

f:id:sakumadaisuke32:20210214192559p:plain
図10. 図9の時のBloch球

標的ビットの状態ベクトルがZ軸を軸に180度回っています。
つまり、標的ビットの位相が反転したということです。
確率振幅も |11>だけ符号がマイナスになっています。


\begin{aligned}
|1>_0 \otimes H|0>_1 &\stackrel{\mathrm{CZ}}{\longrightarrow} |1>_0 \otimes \frac{1}{\sqrt{2}} \left\{ |0>_1 +  \exp^{i (\phi + 1 \dot \pi)}|1>_1 \right\} \\
&= \frac{1}{\sqrt{2}} (|10> - |11>)
\end{aligned}

そして制御ビットを重ね合わせにすると、4状態の内 |11>の符号だけ反転するということです。
ここではCZゲートの働きがやりたいことをちょうど満たしてくれているから使っているということです。

ラクル回路で符号を反転させる状態を変える

では例えば4状態の内、 |00>の符号を反転させるには?
CZゲートの後に制御ビット・標的ビットともにXゲートを掛ければ良いです。
イメージはCXゲートで制御ビットが|0>の時に標的ビットを反転させるのに近いです。

実装としてはこちらです。

qr = QuantumRegister(2, 'data')
qc = QuantumCircuit(qr)

qc.h(qr)
qc.cz(qr[0], qr[1])
qc.x(qr)

backend = Aer.get_backend('statevector_simulator')
job = execute(qc, backend=backend)
result = job.result()

state = result.get_statevector()
print(state)
qc.draw(output='mpl')
>> [-0.5+0.j  0.5+0.j  0.5+0.j  0.5+0.j]

f:id:sakumadaisuke32:20210214222108p:plain
図11.  |00>の符号を反転させるオラクル回路

数式上では


\begin{aligned}
&\frac{1}{2} \mathrm{X_0} (|0>_0 + |1>_0) \otimes \mathrm{X_1} (|0>_1 + |1>_1) = \frac{1}{2} (|0>_0 + |1>_0) \otimes (|0>_1 + |1>_1) \\
&\stackrel{\mathrm{CZ}}{\longrightarrow} \frac{1}{2} \left[|0>_0 \otimes \left\{ |0>_1 +  \exp^{i (0 \dot \pi)}|1>_1 \right\} + |1>_0 \otimes \left\{ |0>_1 +  \exp^{i (1 \dot \pi)}|1>_1 \right\}\right]\\
&= \frac{1}{2} (|00> + |01> + |10> - |11>) \\
&\stackrel{\mathrm{X^{\otimes 2}}}{\longrightarrow} (|11> + |10> + |01> - |00>)
\end{aligned}

もう一例、 |01>の符号を反転させたい場合は制御ビットだけCZの後にXゲートを掛ければ良いです。

qr = QuantumRegister(2, 'data')
qc = QuantumCircuit(qr)

qc.h(qr)
qc.cz(qr[0], qr[1])
qc.x(qr[0])

backend = Aer.get_backend('statevector_simulator')
job = execute(qc, backend=backend)
result = job.result()

state = result.get_statevector()
print(state)
qc.draw(output='mpl')
>> [ 0.5+0.j  0.5+0.j -0.5+0.j  0.5+0.j]

f:id:sakumadaisuke32:20210214222211p:plain
図12.  |01>の符号を反転させるオラクル回路

このCZゲートを使ったオラクル回路についてはデフォルトでは |11> (一般にはすべてのビットが1の状態)の符号が反転し、状態を |0>にするビットについてCZゲートの後にXゲートを掛ければよいです。

他にCXゲートを使ったオラクル回路がありますが、その解説はまたの機会に譲ります。

まとめ

今回はGroverのアルゴリズムの要素の一つであるオラクル回路の実装の一つでCZゲートを使ったものを解説しました。
CZゲートの制御ビットが1の時に標的ビットの位相を反転する性質がオラクル回路の実装に都合がいいということを示しました。
他の実装にはCXゲートを使ったものがあります、更にそれ以外があるかはわかりませんが、都合がいいゲートを組み合わせてプログラミングをしましょう。

参考

Groverのアルゴリズムの解説ページ