QUANTUM AMPLITUDE AMPLIFICATION

In this tutorial, we provide a detailed discussion and implementation of the Quantum Amplitude Amplification (QAA) algorithm using the Amazon Braket SDK. QAA is a routine in quantum computing which generalizes the idea behind Grover's famous search algorithm, with applications across many quantum algorithms. In short, QAA uses an iterative approach to systematically increase the probability of finding one or multiple target states in a given search space. In a quantum computer, QAA can be used to obtain a quadratic speedup over several classical algorithms [1].

TECHNICAL BACKGROUND OF QAA

Formal introduction of QAA: We start off with a brief formal introduction to QAA, following standard references [1-4]. In the lines that follow, we provide a pictorial derivation of QAA, giving an intuitive background to the derivation shown here. Consider a unitary acting on qubits as follows

where is the amplitude we wish to amplify. Setting , equivalently we can write

Here, we have introduced the -qubit states and by convention referred to as good and bad states, respectively. The states and are (unique) projections of the original state into good and bad subspaces, denoted as and , respectively. Note that and are orthogonal, i.e., , because .

Goal of QAA: The goal of the algorithm is then to evolve the initial state into a state with a higher overlap with the good subspace by amplifying the amplitude of the component of the state.

The amplification process that follows boosts the amplitude of the good state from to with denoting the number of queries or applications of the unitary . The probability of finding a good outcome is maximized when .

Procedure of QAA: Rather than directly taking measurements on (as prepared by a single application of ), QAA proceeds by applying the following operator (that is derived from , i.e., taking as an input),

Here, is a reflection about (leaving the all-zero state untouched while giving a minus sign to all other states) and similarly is a reflection about , giving a negative sign on the good state, as , while leaving the bad state untouched. Finally, denotes the adjoint of . As demonstrated in Refs.[2,3], repeated application of the operator (-times) on gives

In a nutshell, this equation shows that, for small values of the unknown parameter , the repeated application of (involving queries of in total) yields a state for which the desired good state would be measured with a probability at least times larger than that of a naive strategy as obtained from . This result is because the probability of measuring the good state is . Compare this to naive queries, i.e., measurements from copies of the state which gives the good state with linear increase in probability . This reasoning is at the heart of the quadratic speedup obtained with QAA: the probability of measuring the good state after QAA scales quadratically with instead of linearly, meaning we only need queries of to achieve the same probability of measuring compared to the classical strategy. Specifically, if , we have amplified the success probability to .

Because is an input to QAA that we assume is given, our goal is to figure out how to implement , , and as unitaries in a quantum circuit. This work is shown in detail in the lines that follow.

Intuition for QAA: The previous discussion follows the canonical, formal introduction to QAA. This section provides a pictorial derivation of the QAA routine, which helps to get an intuitive understanding of the definition and the role of the operator introduced previously. As shown previously, the two states and are orthogonal, and the whole problem can be analyzed in the two-dimensional subspace spanned by these two orthogonal vectors, with real amplitudes. Since the length of the vectors involved are preserved (that is, the vectors remain normalized) we can visualize the whole QAA procedure as transformations of a point on a simple circle, as shown below, using the good and bad states and as basis vectors, respectively.

Going from left to right in the image above, the QAA routine proceeds as follows:

1. Original situation: First, the original state prepared by as resides in the two-dimensional plane spanned by the basis vectors and , respectively, with (typically small) projection onto the axis.
2. Reflection about : We then apply a reflection around , transforming to , keeping the projection along unchanged, but adding a minus sign to the component. Reflection about means that all terms apart from pick up a negative sign. Because there are only two terms, only picks up a negative sign, which is accomplished by the operator , as defined previously.
3. Reflection about : Finally, we apply a reflection around the original state , giving the final state , with an amplified amplitude of , adding an angle of from the rotation around to the original angle . Reflection about means that all terms except for pick up a minus sign, as can be done by applying the operator . Using the definition and conversely as well as the unitarity condition , this reflection can be rewritten as , where is a reflection about the all-zero state where all terms except for pick up a minus sign.

This sequence completes one cycle of the QAA routine, that is one application of . In total, each application of involves two reflections, first through and then through . The product is a rotation with angle . Based on our analysis above we can write the rotation as

thereby confirming the formal definition above. Repeating this sequence, after iterations of we get the generalized equation

Obtaining a quantum speedup: To see that QAA indeed provides a quantum speedup, suppose we use it to query an unsorted database with elements and good elements. The classical algorithm for finding good entries is to query each element in the database until a good one is found. Thus, the classical solution requires queries. A quantum solution would be to query the database in superposition using the state , where enumerates the elements of the database. The oracle prepares the state

Thus, and for the typical scenario where .

We then apply the QAA algorithm to amplify the amplitude of the good states, such that the probability of obtaining a good outcome is amplified. To ensure that we measure a good outcome with high probability, we apply the Grover iterator times. In other words, we only need to query the oracle times in order to find a good outcome to the search problem with high probability. This outcome is a quadratic improvement over the oracle calls required classically.

CIRCUIT IMPLEMENTATION OF QAA

Implementation of QAA on a QC: Now that we have an intuitive understanding for QAA (after all, it is just a rotation, as illustrated previously), the final puzzle piece that remains to be solved is the actual implementation of the reflections and as a quantum circuit (since is given as input to the QAA problem). Rather than implementing below, we will show how to implement

which gives a minus sign to only, leaving all other states untouched. To compensate for this minus sign, overall we will show how to implement the unitary

Implementation of : First, let us consider

which is a reflection about , because and . This transformation can be achieved by applying to the (last) ancilla qubit. This way, we obtain a minus sign whenever the ancilla is in the state.

Implementation of : We must implement the transformation , while leaving all other states untouched. To this end, we can flip all the qubits (using single-qubit gates), flipping the sign of , and flipping the qubits back. Thus, the last operation that remains to be defined explicitly is flipping the sign of , which can be done with ancilla qubits. One possible way to do this task is by using a multiply-controlled Toffoli gate: First apply a Pauli- gate to each qubit. Then apply the qubit Toffoli, controlled on all of the qubits we want to test, and targeted on a single ancilla qubit. If (and only if) all of the qubits were in the zero state, then the ancilla qubit will be flipped to . We then apply a gate to the ancilla qubit, so the overall wavefunction picks up a minus sign whenever all of the register qubits are in the state. Finally, we uncompute the ancilla by applying another qubit Toffoli gate.

We can decompose the qubit Toffoli gate into CCNOT (that is, 3 qubit Toffoli) gates and ancilla qubits, shown as follows for register qubits:

Thus, the final circuit can be implemented using ancilla qubits as

IMPORTS and SETUP

IMPLEMENTATION OF REFLECTION OPERATORS

In utils_qaa.py we provide a set of simple helper functions to implement the quantum circuit for the QAA algorithm. Specifically, we demonstrate how such modular building blocks can be registered as subroutines, using @circuit.subroutine(register=True). Here we first highlight the implementation of the reflections and as discussed previously. The functions defined as follows comprise the utiles_qaa.py module.

REFLECTION AROUND

We need to apply a minus sign to only. We achieve this goal by applying to the ancilla qubit, so that we obtain a minus sign whenever the ancilla is in the state.

# helper function to apply XZX to given qubit
@circuit.subroutine(register=True)
def minus_R_B(qubit):
    """
    Function to apply a minus sign to |B>|0>. This goal is achieved by applying XZX to the ancilla qubit.

    Args:
        qubit: the ancilla qubit on which we apply XZX.
    """
    # instantiate circuit object
    circ = Circuit()
    
    # Apply sequence XZX to given qubit
    circ.x(qubit).z(qubit).x(qubit)
    
    return circ

REFLECTION AROUND

We must implement , which gives a minus sign to only, leaving all other states untouched. To this end, we implement the circuit visualized previously using ancilla qubits; alternatively, as controlled by the flag use_explicit_unitary, one can evolve the system with the the unitary . This way, we can run QAA on classical simulators without the need to resort to ancilla qubits.

# Helper function to apply rotation -R0
@circuit.subroutine(register=True)
def minus_R_zero(qubits, use_explicit_unitary=False):
    """
    Function to implement transformation: |0,0,...0> -> -|0,0,...0>, all others unchanged. 

    Args:
        qubits: list of qubits on which to apply the gates
        use_explicit_unitary (default False): Flag to specify that we could instead implement
        the desired gate using a custom gate defined by the unitary diag(-1,1,...,1).
    """

    circ = Circuit()
    
    # If the use_explicit_matrix flag is True, we just apply the unitary defined by |0,0,...0> -> -|0,0,...0>
    if use_explicit_unitary:
        # Create the matrix diag(-1,1,1,...,1)
        unitary = np.eye(2**len(qubits))
        unitary[0][0]=-1
        # Add a gate defined by this matrix
        circ.unitary(matrix=unitary, targets=qubits)
    
    # Otherwise implement the unitary using ancilla qubits:
    else:
        # Flip all qubits. We now must check whether all qubits are |1>, rather than |0>.
        circ.x(qubits)

        # If we have only 1 qubit, we only must apply XZX to that qubit to pick up a minus sign on |0>
        if len(qubits) < 2:
            circ.z(qubits)

        # For more qubits, we use Toffoli (or CCNOT) gates to verify the qubits are in |1> (after applying X)
        else:

            # Dynamically add ancilla qubits, starting on the next unused qubit in the circuit
            # NOTE: if this subroutine is being applied to a subset of qubits in a circuit, these ancilla
            # registers may already be used. We could pass in circ as an argument and add ancillas outside of
            # circ.targets instead, if desired.
            ancilla_start = max(qubits) + 1

            # Check that the first two register qubits are both 1's using a CCNOT on a new ancilla qubit.
            circ.ccnot(qubits[0],qubits[1],ancilla_start)

            # Now add a CCNOT from each of the next register qubits, comparing with the ancilla we just added.
            # Target on a new ancilla. If len(qubits) is 2, this does not execute.
            for ii,qubit in enumerate(qubits[2:]):
                circ.ccnot(qubit,ancilla_start+ii, ancilla_start+ii+1)

            # A Z gate applied to the last ancilla qubit gives a minus sign if all register qubits are |1>
            ancilla_end = ancilla_start + len(qubits[2:])
            circ.z(ancilla_end)

            # Now uncompute to disentangle the ancilla qubits by applying CCNOTs in the reverse order to the previous.
            for jj,qubit in enumerate(reversed(qubits[2:])):
                circ.ccnot(qubit,ancilla_end-jj-1, ancilla_end-jj)

            # Finally undo the last CCNOT on the first two register qubits.
            circ.ccnot(qubits[0],qubits[1],ancilla_start)

        # Flip all qubits back
        circ.x(qubits)
    
    return circ

VISUALIZATION OF THE CIRCUIT FOR THE REFLECTION

To check our implementation of the circuit discussed previously, let us visualize this circuit for small number of qubits. Note that our implementation accepts a list of qubit indices with arbitrary index ordering.

Example circuit with four qubits and simple index ordering:

Example with four qubits and arbitrary index ordering:

Note that the simulators require contiguous qubit indexing, while our algorithm does not.

IMPLEMENTATION OF QAA

This section puts everything together and shows how to implement QAA using the subroutines given previously. We first build a function grover_iterator(...) that implements the Grover iterator , given the unitary and the so-called flag qubit labeling the good/bad subspaces. Given this implementation for the Grover iterator it is straightforward to implement a QAA routine qaa(...) which repeatedly applies the iterator for a given number of iterations.

The full code (imported into this notebook in the imports and setup section) is available in the module utils_qaa.py.

@circuit.subroutine(register=True)
def grover_iterator(A,flag_qubit,qubits=None,use_explicit_unitary=False):
    """
    Function to implement the Grover iterator Q=A R_0 A* R_B. 

    Args:
        A: Circuit defining the unitary A
        flag_qubit: Specifies which of the qubits A acts on labels the good/bad subspace.
                    Must be an element of qubits (if passed) or A.qubits.
        qubits: list of qubits on which to apply the gates (including the flag_qubit).
                If qubits is different from A.qubits, A is applied to qubits instead.
        use_explicit_unitary: Flag to specify that we should implement R_0 using using a custom
                              gate defined by the unitary diag(-1,1,...,1). Default is False.
    """
    # If no qubits are passed, apply the gates to the targets of A
    if qubits is None:
        qubits = A.qubits
    else:
        # If qubits are passed, make sure it's the right number to remap from A.
        if len(qubits)!=len(A.qubits):
            raise ValueError('Number of desired target qubits differs from number of targets in A'.format(flag_qubit=repr(flag_qubit)))
    
    # Verify that flag_qubit is one of the qubits on which A acts, or one of the user defined qubits
    if flag_qubit not in qubits:
        raise ValueError('flag_qubit {flag_qubit} is not in targets of A'.format(flag_qubit=repr(flag_qubit)))
    
    # Instantiate the circuit
    circ = Circuit()
    
    # Apply -R_B to the flag qubit
    circ.minus_R_B(flag_qubit)
    
    # Apply A^\dagger. Use target mapping if different qubits are specified
    circ.add_circuit(A.adjoint(),target=qubits)
    
    # Apply -R_0
    circ.minus_R_zero(qubits,use_explicit_unitary)
    
    # Apply A, mapping targets if desired.
    circ.add_circuit(A,target=qubits)
    
    return circ

@circuit.subroutine(register=True)
def qaa(A,flag_qubit,num_iterations,qubits=None,use_explicit_unitary=False):
    """
    Function to implement the Quantum Amplitude Amplification Q^m, where Q=A R_0 A* R_B, m=num_iterations. 

    Args:
        A: Circuit defining the unitary A
        flag_qubit: Specifies which of the qubits A acts on labels the good/bad subspace.
                    Must be an element of qubits (if passed) or A.qubits.
        num_iterations: number of applications of the Grover iterator Q.
        qubits: list of qubits on which to apply the gates (including the flag_qubit).
                If qubits is different from A.qubits, A is applied to qubits instead.
        use_explicit_unitary: Flag to specify that we should implement R_0 using using a custom
                              gate defined by the unitary diag(-1,1,...,1). Default is False.
    """
    # Instantiate the circuit
    circ = Circuit()
    
    # Apply the Grover iterator num_iterations times:
    for _ in range(num_iterations):
        circ.grover_iterator(A,flag_qubit,qubits,use_explicit_unitary)
    
    return circ

NUMERICAL EXAMPLE

This section shows how to use QAA to amplify the amplitude of of a two-qubit state, thereby increasing the entanglement between the two qubits. Consider a single qubit in the state

where is small. This state can be prepared using a small rotation around the direction:

where is chosen to give a coefficient of to .

Suppose is the "good" state and is the "bad" state. We can use a single ancilla qubit to mark whether our register qubit is in the "good" or "bad" state, which can be accomplished by applying a single gate to our ancilla qubit and . Thus,

Our goal is to amplify the coefficient of the "good" state. Using the previous algorithm, this amplification corresponds to applying Quantum Amplitude Amplification with an input unitary . We then test whether the flag qubit is in the state, which we can achieve by checking the amplitude of the state.

Let us check the effectiveness of the algorithm by plotting the probability of measuring as a function of the number of repetitions , which corresponds to the number of queries of the oracle, in the classical problem. According to the description given previously, we should see a distribution that looks like . Note that the probability ResultType we will use requires a non-zero value for shots when running on an on-demand simulator.

As expected, we see that the repeated application of the Grover iterator does increase the amplitude associated with the state . The probability of measuring the bitstring 11 follows the expected analytical result, given by , and shown as the solid orange line. Moreover, we have verified that the optimal number of iterations is approximately given by .

---

APPENDIX

APPENDIX: ALTERNATIVE RUN WITH AMPLITUDE RESULT TYPE

Rather than just examining the marginal probability to find the flag qubit in state as done before, we can also investigate the behavior of the amplitude associated with the state . This amplitude is initially given by for small . We can check explicitly that this amplitude increases using repeated applications of the Grover iterator, and recover the plot using the absolute value squared of the amplitudes.

Using amplitudes also presents a learning opportunity: If we use ancilla qubits to implement the reflection (by fixing use_explicit_unitary = False), then measurement outcomes are bitstrings of size (as we measure the original qubits on which the circuit acts, as well as the ancilla qubits).

Since the ancilla qubits are initialized in and are uncomputed back to their initial state in the last step of the algorithm, we can find the amplitude of a given bitstring on the register qubits by padding that target bitstring (for example, in our example) with the right number () of zeros.

Using a classical simulator backend, we can attach the corresponding amplitude as a ResultType to the circuit, as shown in the following code.

---

References

[1] Wikipedia: Amplitude Amplification.

[2] G. Brassard, P. Høyer, "An exact quantum polynomial-time algorithm for Simon's problem", Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems. IEEE Computer Society Press: 12–23, arXiv:quant-ph/9704027 (1997).

[3] G. Brassard, P. Høyer, M. Mosca, A. Tapp, "Quantum Amplitude Amplification and Estimation", arXiv:quant-ph/0005055 (2000).

[4] Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, N. Yamamoto, "Amplitude Estimation without Phase Estimation", arXiv:1904.10246 (2019).