注釈
このページは docs/tutorials/grover_with_sampler.ipynb から生成されました。
GroverのSamplerを使用したデータベース検索¶
In this tutorial, you will solve a small database search problem using Grover’s algorithm with the Sampler primitive in Qiskit Runtime.
始める前に¶
このチュートリアルでは、Qiskit Runtime サービス・インスタンスが必要です。まだ実行していない場合は、入門ガイド に従ってセットアップします。
背景情報¶
非構造化探索の問題¶
昔、あなたは電話帳で人の電話番号を調べていました。 電話帳は名前のアルファベット順に並べられているので、その人の名前を知っていれば、これは簡単な作業です。 ただし、反対のタスク、つまり、電話番号が与えられ、それが誰に属しているかを知りたい場合は、はるかに困難です。 そのため、電話帳は電話番号順には並んでいません。 これは、非構造化探索の問題の例です。 従来のコンピューターでこの問題を解決するには、エントリーをランダムに選択するのが最善の方法です。 平均して、電話番号の持ち主を見つけるには、全体の半分 (\(N\) がエントリーの総数の場合 \(N/2\) ) を調べる必要があります。 ただし、量子コンピューターを使用している場合は、グローバーのアルゴリズムを使用して、 \(\sqrt N\) 回の試行で持ち主を見つけることができます。 つまり、100万件の番号がある電話帳で所有者を特定するには、500,000回ではなく1000回の試行を行うだけで済みます。
Grover のアルゴリズム¶
一言で言えば、グローバーのアルゴリズムは、振幅増幅と呼ばれる優れた量子トリックを使用して、各試行 (反復) で正しい答え (電話番号の所有者) を見つける可能性を劇的に高めます。 今知っておく必要があるのはそれだけです。 Qiskitがやってくれるので、グローバーのアルゴリズムの仕組みについて詳細を理解する必要はありません! ただし、興味がある場合は、 Qiskit textbook でグローバーのアルゴリズムに関する章を読むことができます。
次に、具体的な例を見てみましょう。
概要¶
このチュートリアルでは、以下の手順に従って、Groverのアルゴリズムを使用して小さな電話帳の所有者を探します。
電話帳検索の問題のためにGroverの回路を作成します。
Submit the circuits to a quantum computer on the cloud using Qiskit Runtime service and the Sampler primitive.
結果を分析し、電話番号の所有者を特定します。
グローバーの回路の作成¶
Qiskit で非構造化探索の問題を定義します¶
この簡単な例では、 人物0 から人物7 までの8 つの項目を持つ小さな電話帳が与えられ、特定の電話番号の所有者を見つけたいと考えています。 しかし、直接電話帳を見ることは許されていません。 私たちは 「オラクル」 に相談することしか許されていません。 オラクルは、私たちの推測が正しいか間違っているか ( 「行列」のオラクルのように) すぐにわかるブラック・ボックス回路です。
[1]:
import random
from qiskit.quantum_info import Statevector
secret = random.randint(0, 7) # the owner is randomly picked
secret_string = format(secret, "03b") # format the owner in 3-bit string
oracle = Statevector.from_label(secret_string) # let the oracle know the owner
一度オラクルを手にしてしまえば、 Qiskitの AmplificationProblem
クラスを使用して非構造化探索の問題を定義できます。
[2]:
from qiskit.algorithms import AmplificationProblem
problem = AmplificationProblem(oracle, is_good_state=secret_string)
問題に対するグローバーの回路を構成する¶
これで、この問題に対するグローバーのアルゴリズムの量子回路を構築する準備が整いました。 正しい答えを見つける際のグローバーのアルゴリズムの精度は、反復回数とともに増加します。 この効果を確認するために、1回と2回の反復で回路を作成してみましょう。
[3]:
from qiskit.algorithms import Grover
grover_circuits = []
for iteration in range(1, 3):
grover = Grover(iterations=iteration)
circuit = grover.construct_circuit(problem)
circuit.measure_all()
grover_circuits.append(circuit)
回路を見ていきましょう。
[4]:
# Grover's circuit with 1 iteration
grover_circuits[0].draw()
[4]:

[5]:
# Grover's circuit with 2 iterations
grover_circuits[1].draw()
[5]:

ステップ2: 回路をクラウド上の量子コンピューターに送信する¶
Now that the Grover’s circuits are created, let’s submit them to a quantum computer on the cloud by using the Sampler primitive.
Qiskit Runtime サービスに接続する¶
まず、 最初のステップ で作成した Qiskit Runtime サービス・インスタンスに接続します。
[6]:
from qiskit_ibm_runtime import QiskitRuntimeService
service = QiskitRuntimeService()
backend = "ibmq_qasm_simulator" # use the simulator
Grover’s algorithm determines the correct answer based on the highest probability of measurement outcomes. The Sampler
primitive is perfect for getting probabilities, so you will use that. In the following cell, you create an instance of the Sampler
primitive, and start a Runtime session using the context manager (with ...:
), which automatically opens and closes the session for you.
The Sampler
primitive allows a batch submission of circuits in a job. Here you are passing a list of two circuits (Grover with 1 iteration and 2 iterations) to the Sampler but only one call is needed to sample the probability of measurement outcomes of both circuits.
[7]:
from qiskit_ibm_runtime import Sampler, Session
with Session(service=service, backend=backend):
sampler = Sampler()
job = sampler.run(circuits=grover_circuits, shots=1000)
result = job.result()
print(result)
SamplerResult(quasi_dists=[{1: 0.029, 2: 0.026, 5: 0.032, 3: 0.808, 0: 0.029, 7: 0.029, 6: 0.023, 4: 0.024}, {5: 0.011, 2: 0.012, 0: 0.007, 3: 0.936, 7: 0.005, 6: 0.015, 4: 0.006, 1: 0.008}], metadata=[{'header_metadata': {}, 'shots': 1000}, {'header_metadata': {}, 'shots': 1000}])
ステップ 3: 結果の分析¶
結果を見てみよう。
[8]:
from qiskit.tools.visualization import plot_histogram
# Extract bit string with highest probability from results as the answer
result_dict = result.quasi_dists[1].binary_probabilities()
answer = max(result_dict, key=result_dict.get)
print(
f"As you can see, the quantum computer returned '{answer}' as the answer with highest probability.\n"
"And the results with 2 iterations have higher probability than the results with 1 iteration."
)
# Plot the results
plot_histogram(result.quasi_dists, legend=["1 iteration", "2 iterations"])
As you can see, the quantum computer returned `3` as the answer with highest probability.
And the results with 2 iterations have higher probability than the results with 1 iteration.
[8]:

量子の結果を秘密の文字列とともに印字して、量子コンピューターが正しい答えを見つけたことを確認しましょう。
[9]:
# Print the results and the correct answer.
print(f"Quantum answer: {answer}")
print(f"Correct answer: {secret_string}")
print("Success!" if answer == secret_string else "Failure!")
Quantum answer: 011
Correct answer: 011
Success!
おめでとうございます!電話番号の所有者が見つかりました。
チュートリアルを数回再実行すると、他のランダムな秘密の文字列を生成して、私たちが不正をしていないことを確認することができます。 量子コンピュータは毎回正しい答えを見つけるでしょう。
概要¶
In this tutorial, you have solved a small database search problem using a quantum computer. You have constructed Grover’s circuits by defining a phone book search problem using the AmplificationProblem
class in Qiskit and then submitted the circuits to run using the Sampler primitive through Qiskit Runtime service.
参考文献¶
Harkins, F., Grover’s search algorithm. In A. Abbas, et al. Learn Quantum Computation Using Qiskit. URL: https://learn.qiskit.org/course/introduction/grovers-search-algorithm (accessed 09/01/2022) (2020).
Qiskit のバージョンと著作権¶
[10]:
import qiskit_ibm_runtime
qiskit_ibm_runtime.version.get_version_info()
[10]:
'0.7.0'
[11]:
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright
Version Information
Qiskit Software | Version |
---|---|
qiskit-terra | 0.21.1 |
qiskit-aer | 0.10.4 |
qiskit-ibmq-provider | 0.19.2 |
System information | |
Python version | 3.10.5 |
Python compiler | Clang 13.0.1 |
Python build | main, Jun 14 2022 07:05:37 |
OS | Darwin |
CPUs | 8 |
Memory (Gb) | 16.0 |
Tue Aug 23 13:55:53 2022 CEST |
This code is a part of Qiskit
© Copyright IBM 2017, 2022.
This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.