グローバーのアルゴリズム基礎(1):オラクル回路
今回からは4回のシリーズでGrover探索アルゴリズムの解説をします。 Grover探索アルゴリズムもQuantumChallenge2020に出題され、仕組みと使い方を覚えると汎用性が高いアルゴリズムです。 QuantumChallenge2020公式
GroverのアルゴリズムはDeutsch–Jozsaアルゴリズム・Shorのアルゴリズムと並んで量子コンピュータの構想初期から注目され続けている量子アルゴリズムです。 公式をはじめとして様々なところで既に解説はされているのですが、数式と実装する量子回路との対応、どうしてそのゲートを使うのかなどの理由も深堀し直して初学者の人がイチからコーディングできるように、また応用を利かせられるような解説を目指します。
次の予定でいます。
今回は「オラクル回路」という、探索する状態の選択肢の中から「これが答えだ」「これを見つけたい」という状態を見つけてマーキングする回路です。 ちなみに「オラクル(Oracle)」とは日本語で「神託(神のお告げ)」(Wikipedia)ということで、与えられた問題の答えを予め知っているから、というのが言葉の由来です。
対象とする読者
- 量子プログラミング・量子計算に興味を持って勉強し始めたエンジニア・高校生・大学生
- Groverのアルゴリズムについて改めて知りたい方 など
前提とする知識
- 簡単な論理演算(AND, OR, NOT)が分かること
- 基本的な量子ゲート(H, X, CX, CCX, Z, CZ)が分かること
- 線形代数(行列・ベクトルの積、直積、あとできれば線形変換)が分かること
- ベクトルのブラケット記法(など、もしくはDirac記法ともいう)が分かること
バージョン情報
- Python 3.7.3
- Qiskit 0.23.1
目次
Groverのアルゴリズムの概要
概要の説明はQuantumChallenge2020問題の前半の解説(日本語)が絵も有ってまとまっていて良いと思います。
ここでは詳細な説明は割愛しますが、要素は次の2点です。
- 答えに対応する状態をマーキング
- そのマーキングされた状態の確率だけを増幅
最終的に状態を測定すると探していた状態が100%に近い確率で測定される、というものです。
簡略した量子回路は下記で書かれます。
この図の意味
2量子ビットの場合は下記が実装の1例になります。
以降ではオラクル回路をどうして上図のように実装するのか、数式と量子回路の対応を確かめます。
オラクル回路の役割と仕組み
役割と仕組み
左右の図について説明します。
が探している状態です。
が探索する全状態の重ね合わせ状態で、下式です。
が状態の数です。
上式は一般式ですが、
例えば2量子ビットの場合は取りうる全状態は の 22 = 4 個、
3量子ビットの場合は の 23 = 8 個です。
上式とは という風に対応します。
左の図では、に直交する(との内積がゼロになる)状態を仮にとしています。
(の重ね合わせの内、の係数がゼロな状態が相当)
この状態(ベクトル)を軸に反転した状態をとします。
この結果、はの重ね合わせの内、の係数だけマイナスになったものです。
このの状態の確率振幅を図示したのが右の図です。
状態の確率振幅だけが他と絶対値は同じで符号が反転しています。
例えば2量子ビットの場合
での時、
です。
というように、全状態の重ね合わせ状態から探している状態の確率振幅の符号を反転(=位相を反転)させたに変換することがオラクル回路の役割です。
またこの目的の状態の位相を反転することを「マーキングする」と言うことがあります。
オラクル回路の実装例
では数学的にやりたいことはわかったので、量子回路で実装しましょう。
やりたいこと:
- 取りうるすべての状態を生成
- 答えの状態の位相を反転するようにゲート操作
図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')
この時の状態ベクトルの確率振幅を確認しましょう。
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])
ではこの時この回路では何が起きているのか、また以外の状態の位相を反転させたいときにはどうしたらいいのか確認しましょう。
オラクル回路の中身
まずは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]
Bloch球では2つのビットともになっていて、また確率振幅も等しいですね。
つまり、下記の数式の状態になっています。
これはよくやるので多分当たり前になっていますが、「全状態の重ね合わせを作りたい」という目的に対して、Hゲートで1量子ビットの重ね合わせ状態を作り、それぞれの量子ビットを相互作用させず独立にしておくことで直積(総当たりの組み合わせ)で表現できるようにすることで目的を達成させている例です。
ではこの後のCZゲートが何しているのか確認しましょう。
そもそもCZゲートは制御ビットがの時に標的ビットにZゲートを掛ける(位相を反転する)というものです。
制御ビットがの場合
分かりやすくするため、標的ビットには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]
標的ビットの状態ベクトルに変化はないですね。
ちなみに確率振幅の配列は左から順にです。
だから数式としては下記の状態になって、Zゲートがかからずそのままということです。
制御ビットがの場合
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]
標的ビットの状態ベクトルがZ軸を軸に180度回っています。
つまり、標的ビットの位相が反転したということです。
確率振幅もだけ符号がマイナスになっています。
そして制御ビットを重ね合わせにすると、4状態の内の符号だけ反転するということです。
ここではCZゲートの働きがやりたいことをちょうど満たしてくれているから使っているということです。
オラクル回路で符号を反転させる状態を変える
では例えば4状態の内、の符号を反転させるには?
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]
数式上では
もう一例、の符号を反転させたい場合は制御ビットだけ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]
このCZゲートを使ったオラクル回路についてはデフォルトでは (一般にはすべてのビットが1の状態)の符号が反転し、状態をにするビットについてCZゲートの後にXゲートを掛ければよいです。
他にCXゲートを使ったオラクル回路がありますが、その解説はまたの機会に譲ります。
まとめ
今回はGroverのアルゴリズムの要素の一つであるオラクル回路の実装の一つでCZゲートを使ったものを解説しました。
CZゲートの制御ビットが1の時に標的ビットの位相を反転する性質がオラクル回路の実装に都合がいいということを示しました。
他の実装にはCXゲートを使ったものがあります、更にそれ以外があるかはわかりませんが、都合がいいゲートを組み合わせてプログラミングをしましょう。