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



In [ ]:

    
from collections import defaultdict

import numpy as np
from mock import patch

from grove.simon.simon import Simon, create_valid_2to1_bitmap

Simon's algorithm can be used to find the mask $m$ of a 2-to-1 periodic Boolean function defined by $$f(x) = f(x \oplus m)$$ where $\oplus$ is the bit-wise XOR operator. To create one we can define a mask as a string and call a utility to generate a map. To assert the correct result we check it against an expected map



In [ ]:

    
mask = '110'
bm = create_valid_2to1_bitmap(mask, random_seed=42)
expected_map = {
    '000': '001',
    '001': '101',
    '010': '000',
    '011': '111',
    '100': '000',
    '101': '111',
    '110': '001',
    '111': '101'
}
for k, v in bm.items():
    assert v == expected_map[k]

To understand what a 2-to-1 function is let us revert the map and collect all keys tha point to the same value. As the assertion shows all values have 2 distinct origins



In [ ]:

    
reverse_bitmap = defaultdict(list)
for k, v in bm.items():
    reverse_bitmap[v].append(k)

expected_reverse_bitmap = {
    '001': ['000', '110'],
    '101': ['001', '111'],
    '000': ['010', '100'],
    '111': ['011', '101']
}

for k, v in reverse_bitmap.items():
    assert sorted(v) == sorted(expected_reverse_bitmap[k])

To use Simon's algorithm on a Quantum Hardware we need to define the connection to the QVM or QPU. However we don't have a real connection in this notebook, so we just mock out the response. If you run this notebook, ensure to replace cxn with a pyQuil connection object.



In [ ]:

    
with patch("pyquil.api.QuantumComputer") as qc:
    # Need to mock multiple returns as an iterable
    qc.run.side_effect = [
        (np.asarray([0, 1, 1], dtype=int), ),
        (np.asarray([1, 1, 1], dtype=int), ),
        (np.asarray([1, 1, 1], dtype=int), ),
        (np.asarray([1, 0, 0], dtype=int), ),
    ]

Now let's run Simon's algorithm. We instantiate the Simon object and then call its find_mask mehtod with the connection object and the 2-to-1 function whose mask we wish to find. Finally we assert its correctness by checking with the mask we used to generate the function



In [ ]:

    
sa = Simon()
found_mask = sa.find_mask(qc, bm)
assert ''.join([str(b) for b in found_mask]) == mask, "Found mask is not expected mask"

If the assertion succeeded we know we found the mask and we got our result.