{"cells":[{"cell_type":"text","text":"<h1>Grover's Algorithm</h1>"},{"code":"%load_ext sympyprinting","cell_type":"code","prompt_number":1},{"code":"from sympy import sqrt, symbols, Rational\nfrom sympy import expand, Eq, Symbol, simplify, exp, sin\nfrom sympy.physics.quantum import *\nfrom sympy.physics.quantum.qubit import *\nfrom sympy.physics.quantum.gate import *\nfrom sympy.physics.quantum.grover import *\nfrom sympy.physics.quantum.qft import QFT, IQFT, Fourier\nfrom sympy.physics.quantum.circuitplot import circuit_plot","cell_type":"code","prompt_number":2},{"code":"nqubits = 3\n","cell_type":"code","prompt_number":3},{"cell_type":"text","text":"Grover's algorithm is a quantum algorithm which searches an unordered database (inverts a function).<br/>\nProvides polynomial speedup over classical brute-force search ($O(\\sqrt{N}) vs. O(N))$ "},{"cell_type":"text","text":"Define a black box function that returns True if it is passed the state we are searching for."},{"code":"def black_box(qubits):\n    return True if qubits == IntQubit(1, qubits.nqubits) else False\n","cell_type":"code","prompt_number":4},{"cell_type":"text","text":"Build a uniform superposition state to start the search."},{"code":"psi = superposition_basis(nqubits); psi\n","cell_type":"code","prompt_number":5},{"code":"v = OracleGate(nqubits, black_box)\n","cell_type":"code","prompt_number":6},{"cell_type":"text","text":"Perform two iterations of Grover's algorithm.  Each iteration, the amplitude of the target state increases."},{"code":"iter1 = qapply(grover_iteration(psi, v)); iter1\n","cell_type":"code","prompt_number":7},{"code":"iter2 = qapply(grover_iteration(iter1, v)); iter2\n","cell_type":"code","prompt_number":8},{"cell_type":"text","text":"A single shot measurement is performed to retrieve the target state."},{"code":"measure_all_oneshot(iter2)\n","cell_type":"code","prompt_number":9},{"code":"%notebook save grovers.ipynb","cell_type":"code","prompt_number":28},{"code":"%notebook load qft.ipynb","cell_type":"code","prompt_number":63}]}