This notebook is a brief sketch of how to use Grover's algorithm. We start by declaring all necessary imports.



In [ ]:

    
from itertools import product

from mock import patch

from grove.amplification.grover import Grover

Grover's algorithm can be used to amplify the probability of an oracle-selected bitstring in an input superposition state.



In [ ]:

    
target_bitstring = '010'
bit = ("0", "1")
bitstring_map = {}
target_bitstring_phase = -1
nontarget_bitstring_phase = 1

# We construct the bitmap for the oracle
for bitstring in product(bit, repeat=len(target_bitstring)):
    bitstring = "".join(bitstring)
    if bitstring == target_bitstring:
        bitstring_map[bitstring] = target_bitstring_phase
    else:
        bitstring_map[bitstring] = nontarget_bitstring_phase

We'll make sure the bitstring_map is as we expect.



In [ ]:

    
target_bitstring_phase = -1
nontarget_bitstring_phase = 1
for k,v in bitstring_map.items():
    if k == target_bitstring:
        assert v == target_bitstring_phase, "The target bitstring has the wrong phase."
    else:
        assert v == nontarget_bitstring_phase, "A nontarget bistring has the wrong phase."

To use Grover's algorithm on quantum hardware we need to define a connection to a QVM or QPU. However we don't have a real connection in this notebook, so we just mock out the response. If you intend to run this notebook on a QVM or QPU, be sure to replace qc with a pyQuil QuantumComputer object.



In [ ]:

    
with patch("pyquil.api.QuantumComputer") as qc:
    qc.run.return_value = [[int(bit) for bit in target_bitstring]]

Now let's run Grover's algorithm. We instantiate the Grover object and then call its find_bitstring method. Finally we assert its correctness by checking with the bitstring we used to generate the object.



In [ ]:

    
grover = Grover()
found_bitstring = grover.find_bitstring(qc, bitstring_map)
assert found_bitstring == target_bitstring, "Found bitstring is not the expected bitstring"

If the assertion succeeded we know we found the correct bitstring.