Grover search and amplitude amplification¶
The submodule qat.lang.algorithms contains basic implementation of quantum amplification that can be used to (almost) trivially implement Grover search, or its more general variant, amplitude amplification.
In this notebook, we show how to use the qat.lang.algorithms.amplification_step method in order to implement a Grover search and some more general amplitude amplification.
Grover search¶
Let us first write a simple oracle that search for repeated bitstrings (i.e. bitstring of the form $a_1...a_ka_1...a_k$) of some length $2k$.
from qat.lang.AQASM import QRoutine, QInt
def detect_repetitions(k):
routine = QRoutine()
first_half = routine.new_wires(k, QInt)
second_half = routine.new_wires(k, QInt)
(first_half == second_half).phase()
return routine
detect_repetitions(2).display()
Now that we have our oracle, we can use the amplification_step to build a routine that performs a single amplification step:
from qat.lang.algorithms import amplification_step
step_4 = amplification_step(detect_repetitions(2))
step_4.display(depth=2)
From there, it is quite trivial to implement a Grover search.
Recall that we need to:
- prepare a state containing the uniform distribution
- perform a given number of amplification steps
- measure our system
from qat.lang.AQASM import Program, H
def grover_repetitions(nbits, nsteps):
prog = Program()
qbits = prog.qalloc(nbits), prog.qalloc(nbits)
step = amplification_step(detect_repetitions(nbits))
# preparing the uniform superposition
for register in qbits:
for qbit in register:
H(qbit)
for _ in range(nsteps):
step(qbits)
return prog.to_circ()
grover_repetitions(2, 5).display(depth=2)
Let's simulate this circuit! We will search for repetition on 6 bits.
There are $2^6 = 64$ bitstrings of length $6$, among which $2^3=8$ are repetitions. Thus there is a solution density of $8/64 = 1/8$.
We need to perform about $\frac{\pi}{4}{\sqrt{8}}$ steps of amplifications to maximize the success probability of our search.
import numpy as np
nsteps = int(np.pi/4 * np.sqrt(8))
print("Using", nsteps, "amplification steps")
from qat.qpus import get_default_qpu
qpu = get_default_qpu()
result = qpu.submit(grover_repetitions(3, nsteps).to_job())
for sample in result:
print(sample.state, sample.probability)
Using 2 amplification steps |000>|000> 0.11816406249999935 |000>|001> 0.0009765624999999948 |000>|010> 0.0009765624999999948 |000>|011> 0.0009765624999999948 |000>|100> 0.0009765624999999963 |000>|101> 0.0009765624999999963 |000>|110> 0.0009765624999999963 |000>|111> 0.0009765624999999963 |001>|000> 0.0009765624999999948 |001>|001> 0.11816406249999935 |001>|010> 0.0009765624999999948 |001>|011> 0.0009765624999999948 |001>|100> 0.0009765624999999963 |001>|101> 0.0009765624999999963 |001>|110> 0.0009765624999999963 |001>|111> 0.0009765624999999963 |010>|000> 0.0009765624999999948 |010>|001> 0.0009765624999999948 |010>|010> 0.11816406249999935 |010>|011> 0.0009765624999999948 |010>|100> 0.0009765624999999963 |010>|101> 0.0009765624999999963 |010>|110> 0.0009765624999999963 |010>|111> 0.0009765624999999963 |011>|000> 0.0009765624999999948 |011>|001> 0.0009765624999999948 |011>|010> 0.0009765624999999948 |011>|011> 0.11816406249999935 |011>|100> 0.0009765624999999963 |011>|101> 0.0009765624999999963 |011>|110> 0.0009765624999999963 |011>|111> 0.0009765624999999963 |100>|000> 0.0009765624999999963 |100>|001> 0.0009765624999999963 |100>|010> 0.0009765624999999963 |100>|011> 0.0009765624999999963 |100>|100> 0.11816406249999935 |100>|101> 0.0009765624999999948 |100>|110> 0.0009765624999999948 |100>|111> 0.0009765624999999948 |101>|000> 0.0009765624999999963 |101>|001> 0.0009765624999999963 |101>|010> 0.0009765624999999963 |101>|011> 0.0009765624999999963 |101>|100> 0.0009765624999999948 |101>|101> 0.11816406249999935 |101>|110> 0.0009765624999999948 |101>|111> 0.0009765624999999948 |110>|000> 0.0009765624999999963 |110>|001> 0.0009765624999999963 |110>|010> 0.0009765624999999963 |110>|011> 0.0009765624999999963 |110>|100> 0.0009765624999999948 |110>|101> 0.0009765624999999948 |110>|110> 0.11816406249999935 |110>|111> 0.0009765624999999948 |111>|000> 0.0009765624999999963 |111>|001> 0.0009765624999999963 |111>|010> 0.0009765624999999963 |111>|011> 0.0009765624999999963 |111>|100> 0.0009765624999999948 |111>|101> 0.0009765624999999948 |111>|110> 0.0009765624999999948 |111>|111> 0.11816406249999935
As you can see, the repetitions are dramatically more likely to be observed.
From Grover search to amplitude amplification¶
Amplitude amplification is a variant of Grover's search where the solution is searched according to a custom distribution (and not necessarily a uniform one). To perform this type of search, we need to build a state preparation circuit that prepares a quantum state encoding this custom distribution. Here we will generate a somewhat random distribution using the following circuit:
from qat.lang.AQASM import RY
def state_preparation(nbits):
routine = QRoutine()
wires = routine.new_wires(2 * nbits)
for wire in wires:
RY(np.random.random() * np.pi)(wire)
return routine
prep = state_preparation(3)
prep.display()
This state preparation circuit can be fed to the amplification_step method and used to prepare the initial distribution:
def grover_repetitions(nbits, nsteps):
prog = Program()
qbits = prog.qalloc(nbits), prog.qalloc(nbits)
prep = state_preparation(nbits)
step = amplification_step(detect_repetitions(nbits), state_prep=prep)
# preparing the uniform superposition
prep(qbits)
for _ in range(nsteps):
step(qbits)
return prog.to_circ()
def display_success_proba(result):
succ_proba = 0
for sample in result:
value = sample.state.value
if value[0] == value[1]:
succ_proba += sample.probability
print("Success with probability:", succ_proba)
qpu = get_default_qpu()
for nsteps in range(5):
result = qpu.submit(grover_repetitions(3, nsteps).to_job())
print("=== nsteps:", nsteps, "====")
display_success_proba(result)
=== nsteps: 0 ==== Success with probability: 0.15802168498136135 === nsteps: 1 ==== Success with probability: 0.6876884996727967 === nsteps: 2 ==== Success with probability: 0.5528287272571961 === nsteps: 3 ==== Success with probability: 0.9455444656069841 === nsteps: 4 ==== Success with probability: 0.4248054549480958
You can retry several time and observe that the number of steps depends on the initial success probability (the probability of success at step 0).