3-SAT問題
Groverの量子アルゴリズムを用いて、SAT問題が解けます。
qiskit SDK のテキストブックには、3-SATの例があります。
https://qiskit.org/textbook/ja/ch-applications/satisfiability-grover.html
こちらを実機の量子コンピュータでやってみます。
コード
テキストブックをそのままコピペすればよいですが、実機でやるにはIBMQのアカウントをロードする必要があります。
おすすめは、IBMQのWebページ上にある IBMQ Quantum Lab というクラウド開発環境を使うことです。
こちらで作業しますと、単に
from qiskit import IBMQ
provider = IBMQ.load_account()
backend_dev = provider.get_backend('ibmq_16_melbourne')
と書けば、(アカウント情報は自動的に保存してくれているので)いきなり実機へアクセスできるインスタンスbackend_devが手に入ります。
あとは、実際に投げるだけです。
quantum_instance = QuantumInstance(backend_dev, shots=1024)
result = grover.run(quantum_instance)
print(result['result'])
plot_histogram(result['measurement'])
今回は量子ビットがたくさん必要な回路なので、一番大きい”メルボルン”に投げます。
そこそこ人気があるので、待ちます。私は20分待ちました。
セッションがきれてしまった場合、IBMQのWebページ上のQueueに積まれたタスクから、タスクのIDを拾ってきます。
IDがわかったら、それを指定することでタスクをサルベージできます。
job = backend_dev.retrieve_job('60c9edf...hogehoge')
詳細に中身を見たい人は vars(job)
とすればよいです。
次に、jobから測定結果を引っ張り出してヒストグラムにします。
result = job.result()
plot_histogram(result.get_counts())
どこが解やらわかりません。
vars(job)
によると、この回路のゲート数は
'gates_executed': 913
だそうです。そりゃ、無理ですな。
まとめ
3-SATは今の量子コンピュータには難しすぎる。