##// END OF EJS Templates
upstream » ipython
RSS

Clone from https://github.com/ipython/ipython.git

add feedback that ctrl-d was pressed
add feedback that ctrl-d was pressed
Brian E. Granger - - Load All Authors

File last commit:

r4637:d919e2ec
r4950:2b7a2280
Show More
grovers.ipynb
139 lines | 24.3 KiB | text/plain | TextLexer
/ docs / examples / notebooks / grovers.ipynb
History | Annotation | Raw |Copy content |Copy permalink

Grover's Algorithm

In [1]:
%load_ext sympyprinting
In [2]:
from sympy import sqrt, symbols, Rational
from sympy import expand, Eq, Symbol, simplify, exp, sin
from sympy.physics.quantum import *
from sympy.physics.quantum.qubit import *
from sympy.physics.quantum.gate import *
from sympy.physics.quantum.grover import *
from sympy.physics.quantum.qft import QFT, IQFT, Fourier
from sympy.physics.quantum.circuitplot import circuit_plot
In [3]:
nqubits = 3

Grover's algorithm is a quantum algorithm which searches an unordered database (inverts a function).
Provides polynomial speedup over classical brute-force search ($O(\sqrt{N}) vs. O(N))$

Define a black box function that returns True if it is passed the state we are searching for.

In [4]:
def black_box(qubits):
    return True if qubits == IntQubit(1, qubits.nqubits) else False

Build a uniform superposition state to start the search.

In [5]:
psi = superposition_basis(nqubits); psi
Out[5]:
$$\frac{1}{4} \sqrt{2} {\left|0\right\rangle } + \frac{1}{4} \sqrt{2} {\left|1\right\rangle } + \frac{1}{4} \sqrt{2} {\left|2\right\rangle } + \frac{1}{4} \sqrt{2} {\left|3\right\rangle } + \frac{1}{4} \sqrt{2} {\left|4\right\rangle } + \frac{1}{4} \sqrt{2} {\left|5\right\rangle } + \frac{1}{4} \sqrt{2} {\left|6\right\rangle } + \frac{1}{4} \sqrt{2} {\left|7\right\rangle }$$
In [6]:
v = OracleGate(nqubits, black_box)

Perform two iterations of Grover's algorithm. Each iteration, the amplitude of the target state increases.

In [7]:
iter1 = qapply(grover_iteration(psi, v)); iter1
Out[7]:
$$\frac{1}{8} \sqrt{2} {\left|0\right\rangle } + \frac{5}{8} \sqrt{2} {\left|1\right\rangle } + \frac{1}{8} \sqrt{2} {\left|2\right\rangle } + \frac{1}{8} \sqrt{2} {\left|3\right\rangle } + \frac{1}{8} \sqrt{2} {\left|4\right\rangle } + \frac{1}{8} \sqrt{2} {\left|5\right\rangle } + \frac{1}{8} \sqrt{2} {\left|6\right\rangle } + \frac{1}{8} \sqrt{2} {\left|7\right\rangle }$$
In [8]:
iter2 = qapply(grover_iteration(iter1, v)); iter2
Out[8]:
$$- \frac{1}{16} \sqrt{2} {\left|0\right\rangle } + \frac{11}{16} \sqrt{2} {\left|1\right\rangle } - \frac{1}{16} \sqrt{2} {\left|2\right\rangle } - \frac{1}{16} \sqrt{2} {\left|3\right\rangle } - \frac{1}{16} \sqrt{2} {\left|4\right\rangle } - \frac{1}{16} \sqrt{2} {\left|5\right\rangle } - \frac{1}{16} \sqrt{2} {\left|6\right\rangle } - \frac{1}{16} \sqrt{2} {\left|7\right\rangle }$$

A single shot measurement is performed to retrieve the target state.

In [9]:
measure_all_oneshot(iter2)
Out[9]:
$${\left|001\right\rangle }$$