Quantum Amplitude Amplification algorithm (QAA) in ProjectQ

by Fernando de la Iglesia

Some months ago I wrote on the Quantum Phase Estimation algorithm added to ProjectQ and how to use it. Now is the turn to other key algorithm also added to ProjectQ as a native operation: The Quantum Amplitude Amplification algorithm.

As it is well known, the objective of this algorithm is to amplify the amplitude (:-)) of the Hilbert subspace marked by the Oracle involved in the algorithm, such that when we measure, we have a high probability to obtain the state that is the one (or in the subspace) marked by the Oracle.

I highly recommend to read the references: A quick one is the corresponding Wikipedia article, were you can find more references therein, but the “must read” is the great paper by G. Brassard, P. Hoyer, M. Mosca, A. Tapp (2000) Quantum Amplitude Amplification and Estimation https://arxiv.org/abs/quant-ph/0005055.

Please refer to the ProjectQ documentation for setting up an environment to run the framework and to be able to run programs that make use of the framework. This post assumes that you have already installed all the required libraries. In addition, here you can find a link to a jupyter notebook including the examples presented below that include all the required installations and library imports.

To use the Quantum Amplitude Amplification (QAA) native operation you have just to import it in your program.

from projectq.ops import QAA

Provided you import as well all the required libraries typically you need to run ProjectQ programs.

The QAA operation acts on the qubits that form the system (system_qubits in the examples below) and on a control qubit (control in the examples) that helps to invert the amplitude of the selected subspace when the Oracle marks it. This control qubit is initialized to the state |->.

n = 7
system_qubits = eng.allocate_qureg(n)
# Prepare the control qubit in the |-> state
control = eng.allocate_qubit()
X | control
H | control

The other important components are: the algorithm that takes the system from the initial |0> state to a prepared one, and the Oracle that is able to mark the selected (or “good”) subspace. These components need to be defined before the use of the QAA operation.

To fully understand the role of all these components I encourage you to read the references presented before and specially the paper in the arXiv.

In order to show how to use the QAA operation let us make use of it with some examples.

Grover algorithm

The first example is a very special one, that is the Grover algorithm. QAA is in fact a generalization of Grover.

In this special case the algorithm that is applied to the initial state in |0> is the one that takes it to a uniform superposition of all the states in the Hilbert space:

def hache_algorithm(eng, qreg):
    All(H) | qreg

And as the next component, the Oracle, we have one that (for example) marks as the good one the state |1010101> (for a space of 7 qubits)

def simple_oracle(eng, system_q, control):
    # This oracle selects the state |1010101> as the one marked
    with Compute(eng):
        All(X) | system_q[1::2]
    with Control(eng, system_q):
        X | control
    Uncompute(eng)

As can bee seen this simple Oracle inverts the amplitude of the control qubit (and therefore of the whole system) only if the system_qubits is in the marked state.

We have already all the required ingredients, therefore we can now proceed to execute the QAA algorithm the correct number of times to measure and obtain (with high probability) the marked state. First as stated before, we create the quantum register for the system_qubits and for the control one and put the control in the |-> state

n = 7
system_qubits = eng.allocate_qureg(n)
# Prepare the control qubit in the |-> state
control = eng.allocate_qubit()
X | control
H | control

Next we apply the initial algorithm to the initial |0> state, for Grover, a uniform superposition as defined in hache_algorithm

# Creates the initial state form the Algorithm
hache_algorithm(eng, system_qubits)

As it is explained in the references and in any reference for the Grover algorithm we need to execute the QAA algorithm the “correct” number of times. Therefore we need to calculate which is this correct number. The method can be found in the references and depends on the amplitude of the marked state after the initial algorithm execution. In Grover this amplitude is easily known because we have a uniform superposition.

# The correct number of iterations is related to the initial
# amplitude of the selected state after the execution of the
# Algorithm. For Grover that means an equal superposition of
# all the states, therefore the amplitude is 1/sqrt(2**7)
num_it = int(math.pi/4.* math.sqrt(2**n))

Time to apply the QAA algorithm the correct number of times

# Apply Quantum Amplitude Amplification the correct number of times
with Loop(eng, num_it):
    QAA(hache_algorithm, simple_oracle) | (system_qubits, control)

That should prepare the system in a state where we have amplified the amplitude of state marked by the Oracle. Let us measure the system and print the result to verify that this is the case.

# If we measure the system we would find the selected state with
# high probability
All(Measure) | system_qubits
H | control
Measure | control
result = [int(q) for q in system_qubits]
control_result = int(control)
print (result)

Great!: with high (very high) probability we find that we end in the marked state

[1, 0, 1, 0, 1, 0, 1]

As a conclusion we have ran the Grover algorithm by using the QAA operation.

QAA applied to a general initial algorithm and oracle

A more general application of QAA would use an initial algorithm that takes the |0> state to a general one, and an Oracle that marks as “good” a subspace of the complete Hilbert space.

For this example let us create an initial algorithm that is simple and at the same time makes a more or less non uniform random mixture of the states in the Hilbert space

def complex_algorithm(eng, qreg):
    All(H) | qreg
    with Control(eng, qreg[0]):
        All(X) | qreg[1:]
    All(Ry(math.pi / 4)) | qreg[1:]
    with Control(eng, qreg[-1]):
        All(X) | qreg[1:-1]

And let us fix the Oracle as the one that selects the subspace created by |000000> + |111111> (for a space of 6 qubits)

def complex_oracle(eng, system_q, control):
    # This oracle selects the subspace |000000>+|111111> as the good one
    with Compute(eng):
        with Control(eng, system_q[0]):
            All(X) | system_q[1:]
        H | system_q[0]
        All(X) | system_q
    with Control(eng, system_q):
        X | control
    Uncompute(eng)

As before we have already all the components, therefore, let execute QAA in order to obtain a state in the selected subspace with high probability. Firt we create the required quantum registers and execute the initial algorithm for the first time on the system_qubits.

eng = MainEngine()
system_qubits = eng.allocate_qureg(6)
# Prepare the control qubit in the |-> state
control = eng.allocate_qubit()
X | control
H | control
# Creates the initial state form the Algorithm
complex_algorithm(eng, system_qubits)

For this example we will take for granted that we know the initial amplitudes and probabilities of the selected subspace (after the first execution of the algorithm). As stated before, this is key for executing the QAA the correct number of times. When using the ProjectQ simulator we have access to the complete state vector and therefore we can obtain these amplitudes and probabilities (of course we are cheating, in a real quantum computer we have no access to these)

# Get the probabilty of getting the marked state before the QAA
# to calculate the number of iterations
eng.flush()
prob000000 = eng.backend.get_probability('000000', system_qubits)
prob111111 = eng.backend.get_probability('111111', system_qubits)
total_amp_before = math.sqrt(prob000000 + prob111111)
theta_before = math.asin(total_amp_before)
# The number of iterations to run QAA is related to the probability
# of the good subspace after applying the algorithm for the first
# time to the |0> state
num_it = int(math.pi / (4. * theta_before) + 1)

Please review the references in order to know how to obtain the number of iterations to run QAA form the initial probabilities.

Now we can loop the execution of QAA

# Apply Quantum Amplitude Amplification the correct number of times
with Loop(eng, num_it):
    QAA(complex_algorithm, complex_oracle) | (system_qubits, control)

And after that, measure the system and obtain (hopefully) the good subspace with high probability

# If we measure the system now we would obtain a result in the
# good subspace with high probability
All(Measure) | system_qubits
H | control
Measure | control
result = [int(q) for q in system_qubits]
control_result = int(control)
print (result)
eng.flush()

It seems that it worked in this case ;-)

[1, 1, 1, 1, 1, 1]

Of course a next example would be to obtain an amplified amplitude in the case of not knowing the initial amplitudes of the marked subspace. This will be the subject of a future post.