IBM Quantum Challenge 2019 振り返り(最終週)
最終週を振り返っていきます。
第3週までやってきたことをフル活用する課題となっていました。 これまでの課題と違って解答例がなく、自力が試されます。
私は、力足りず解答をサブミットできませんでした！
悔しいので、この振り返りで今後の糧にしていきます。
↓最終週の課題
上の地図の0-6の地域にA,B,C,Dの4社のコンビニを 隣接したノードが同じコンビニにならないように配置してく、4色問題を量子コンピュータで解くことが課題です。
注意点としては
自分の解答
全体の方針は第3週と同じで、オラクル回路を設計しDiffusion回路を付け加えることで、Groverのアルゴリズムを実装していきます。
まずは簡単のため、地図左上のA,0,2,3,Cのみで考えてみます。
可能な配置は、下の4通りです。
| 0番地区 | 2番地区 | 3番地区 |
|---|---|---|
| C社 | B社 | D社 |
| D社 | B社 | C社 |
| B社 | D社 | C社 |
| C社 | D社 | B社 |
A社を00、B社を01、C社を10、D社を11とし、
量子レジスタq[2n], q[2n+1]にn番目の区域に出店するコンビニを格納します。
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit from qiskit import IBMQ, Aer, execute import numpy as np from qiskit.tools.visualization import plot_histogram q = QuantumRegister(13) c = ClassicalRegister(13) qc = QuantumCircuit(q,c) # initialization # 0番地区 qc.h(q[0:2]) # 2番地区 qc.x(q[4]) qc.h(q[5]) # 3番地区 qc.h(q[6:8])
2番地区はA社とC社に隣接しているので、初期状態ではB社とD社の重ね合わ背状態を作ります。
0番地区と3番地区はA社と隣接しているので、A社以外のコンビニが配置されているかの情報を他の量子ビットに格納します。
# 0番地区が01,10,11のときq[8]が1、00のときq[8]が0 qc.cx(q[0], q[8]) qc.cx(q[1], q[8]) qc.ccx(q[0], q[1],q[8]) qc.barrier() # 3番地区が01,10,11のときq[9]が1、00のときq[9]が0 qc.cx(q[6], q[9]) qc.cx(q[7], q[9]) qc.ccx(q[6], q[7],q[9]) qc.barrier()
0番地区、3番地区とA社の関係をそれぞれq[8]、q[9]に格納しました。
続いて、0番地区、2番地区、3番地区でB社、C社、D社がそれぞれ1つずつ配置されたかを判別する回路を作成します。
qc.cx(q[0], q[10]) qc.cx(q[4], q[10]) qc.cx(q[6], q[10]) qc.x(q[10]) qc.cx(q[1], q[11]) qc.cx(q[5], q[11]) qc.cx(q[7], q[11]) qc.x(q[11]) qc.barrier()
q[10]、q[11]に情報を格納しました。両方が1のときB社、C社、D社がそれぞれ1つずつ配置された状態になっています。
コンビニの配置が条件をみたすかの情報を持っている量子ビットq[8],q[9],q[10],q[11]がすべて1の場合、求めたいコンビニ配置の状態になっていると考えられます。
qc.mct(q[8:12],q[12],[],mode='noancilla') qc.barrier()
オラクルが完成しました。
ちゃんとできているか、確認しましょう。
qc.measure(q[0:2], c[0:2]) qc.measure(q[4:8], c[4:8]) qc.measure(q[-1], c[-1]) backend = Aer.get_backend('qasm_simulator') job = execute(qc, backend, shots=8000) result = job.result() count = result.get_counts() qc.draw(output='mpl')
plot_histogram(count)
最上位ビットが1となっているのが、上記の表の4通りと一致しています。 オラクルが完成しました！！！
ここから、1番地区、4番地区、5番地区、…と同様に、地図の情報を量子回路に反映していけば解答できると考えました。
隣接した地区で同じコンビニが出店しているかは、ccccxゲートとxゲートを組み合わせることが実現ができます。
しかし、この方法では地域の初期化とグラフの辺で1つずつ量子ビットを使い、32ビットの制限をオーバーしてしまいます。
効率の良く辺の情報を格納する量子回路を検討しましたが、開催期間中に見つけることができなかったです。
一方で、このあとDiffusion回路をつけてちゃんと解が得られるか確認しましたが、うまく実装できていないようでした、原因の理解できず解決できませんでした。
ここまでが、IBM Quantum Challenge 2019 開催期間中にたどり着いた解答になります。
ジャッジの解説を見ながら振り返る
入力の重ね合わせ状態を作る
空間削減のため初期状態を減らすことは思いついていましたが、余分に量子ビットをつかっていました。
# 0地区の初期状態 theta = 2 * np.arccos(1 / np.sqrt(3)) qc.ry(theta,qr[0]) qc.ch(qr[0],qr[1]) qc.x(qr[1])
Ryゲートを使うことで、0と1が1:2で重ね合わさった状態を作り、CHゲートとXゲートでうまいこと初期状態を作っています。
問題の制約に基づくオラクルを構成する
ccccxゲートと反転ゲートを使うことは解答例とあっていました。
コストが低いrccxやrcccx と 4つのccccxを4つのccxで置き換える方法 について理解は今後の課題にしたいと思います。
diffusion
初期状態の逆操作が必要なことを理解できておらず、ちゃんと反転操作ができていませんでした。
Groverのアルゴリズムを理解できていたつもりが、全然理解できていませんでした。
やはり、数式をちゃんと書いて量子状態を追いかけながらの理解が1回は必要ですね。
感想
最終週の課題は解答例がなかったので、どこから手を付けるか試行錯誤しながらの検討でした。
平日は仕事から帰ってきた後のチャレンジで、疲れた頭では全然考えが回りません。
第3周目までの課題をヒントにしつつ解答方針が固まったのが締め切り3日前くらいで、その頃には解答クリアチームのランキングが出揃ってきて焦りました。
残り時間ひとりであっちこっち考えながら取り組みましが、そのまま時間は過ぎ、タイムアップしてしまいチャレンジ未達で終了。
全体を通して、量子コンピュータ初心者でも取り組みやすく学ぶことが多く、参加かしてよかったです。
参加者のみなさん お疲れさまでした！
Passしたみなさん おめでとうございます！
入賞したみなさん 流石です！解答で勉強させてもらいます！！
また来年あれば、リベンジするぞ！！！
2019/9/23~2019/12/13でIBM Q Awards開催しているみたいです。
