# Kaleido is used to convert Plotly to static png
!pip install -Uqq kaleido
# skq is used for building quantum circuits
!pip install -Uqq skq
This notebook is part of the q4p (Quantum Computing for Programmers) series. The original notebook can be found on Github.
00b. Guessing the number of marbles in a vase
This notebook will give you a high-level overview of a practical problem where we can gain a (quadratic) advantage over classical algorithms using a quantum algorithm. This notebook also provides an outline of the topics discussed in this course. To solve our first problem with a quantum algorithm we are going to guess the number of marbles in a hidden vase. This exercise will show you how to gain a quadratic advantage over classical algorithms with Grover’s unstructured search algorithm.
Problem Outline
#
Imagine your friend has a vase with marbles hidden inside a closet. You can have unlimited guesses at how many marbles are in the vase. Each time you guess your friend will tell you if it is the right answer or not.
Classically you would start going through all the options. \(0, 1, 2,\) etc. In the worst case you will end up guessing \(n\) times, where \(n\) is the number of marbles in the vase. What if I told you that with a quantum algorithm we can guess the number of marbles with only \(\sqrt{n}\) guesses? That is, if your friend is part of the quantum system. To solve this problem we will use Grover’s algorithm, so you can begin to build an intuition of what quantum computing has to offer. The details of the algorithm will be discussed in notebook 5.
Let’s say there can be a maximum of \(255\) marbles in the vase, which corresponds to \(8\) bits of information. Then in the worst case the classical algorithm will have to take \(256\) guesses. With a quantum algorithm we can achieve a worst case of approximately \(\sqrt{256} = 16\) guesses. We do this by leveraging quantum interference and entanglement. In the quantum context a guess is equal to a Grover iteration. We will show that even with only \(6\) Grover iterations we are able to solve this search problem on \(8\) bits.
import numpy as np
from skq.circuits import Grover
import plotly.graph_objects as go
# Fix Plotly rendering in Jupyter forks.
# If you are running this notebook locally you can comment this out.
# This allows you to play with interactive Plotly plots.
import plotly.io as pio
= 'png' pio.renderers.default
Building and running Grover’s algorithm
= 8
n_qubits # Generate secret random state (vase with marbles in the closet)
= np.zeros((2**n_qubits))
target_state = np.random.randint(2**n_qubits)
random_index = 1 target_state[random_index]
# Execute Grover's search algorithm
= 6
grover_iterations = Grover().circuit(n_iterations=grover_iterations,
grover =n_qubits,
n_qubits=target_state)
target_state= grover(np.array([1]+[0]*(len(target_state)-1))) result
Don’t worry about the details of the quantum circuit below. In notebook 2 we will learn more about quantum logic gates and how they work in a quantum computer. For now note that each Grover iteration consists of a PhaseOracle
and a GroverDiffusion
operator, which we repeat \(6\) times. You can view this as \(6\) “guesses” of the number of marbles in the vase. The PhaseOracle
is like your friend that tells you if you got the right answer or not. GroverDiffusion
amplifies the probability of the correct answer.
='mpl') grover.draw(output
= np.argmax(result)
max_idx = result[max_idx]
max_val
= go.Figure(data=[
fig =list(range(len(result))), y=result),
go.Bar(x
go.Scatter(=[max_idx],
x=[max_val],
y='text',
mode=[f'{max_idx:.0f} Marbles'],
text='top center',
textposition=dict(color='green'),
marker=False
showlegend
)
])
fig.update_layout(="Grover's Algorithm Results",
title="State",
xaxis_title="Probability"
yaxis_title
) fig.show()
print(f"Guessed number of marbles: '{np.argmax(result.round())}'")
print(f"Number of marbles in the vase: '{np.argmax(target_state)}'")
print(f"Answer is {'correct' if np.argmax(result.round()) == np.argmax(target_state) else 'incorrect'}!")
Guessed number of marbles: '40'
Number of marbles in the vase: '40'
Answer is correct!
Congratulations, you’ve just built and ran your first quantum algorithm! Note that what we have run here is a classical simulation of the quantum algorithm using NumPy.
Running algorithms on real quantum hardware
To run the algorithm on a real quantum computer we have to convert the circuit to a quantum computing framework. One popular framework is IBM’s Qiskit. To convert the circuit we have built to Qiskit we simply call the convert
method.
= grover.convert(framework="qiskit")
qc qc
<qiskit.circuit.quantumcircuit.QuantumCircuit at 0x15edd0650>
Notebook 8 will be all about how to run quantum algorithms on real quantum computers.
A quadratic advantage over classical algorithms is already pretty cool! Though other algorithms like Shor’s algorithm can gain exponential advantages over classical algorithms. Intrigued? Then this course is for you!
I would recommend you start this course by learning more about qubits first in notebook 1. By going through the notebooks you will be able to gain a solid understanding of how quantum algorithms work and implement your own algorithms.
Continue with the next lesson: - On Github - On Kaggle
This notebook is part of the q4p (Quantum Computing for Programmers) series. The original notebook can be found on Github.