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

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

Changes to pexpect so it does what we need after conversion to Python 3.
Changes to pexpect so it does what we need after conversion to Python 3.
Brian E. Granger - - Load All Authors

File last commit:

r4637:d919e2ec
r4835:a69359fb
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 }$$