Skip to content

Amplitude Amplification

Amplitude Amplification is an algorithm which boosts the amplitude of being in a certain subspace of a Hilbert space[1]. Using the grover operator, the state is shifted towards the 'good' states, which are marked by the oracle, by some amount.

Amplitude Amplification is utilized in many algorithm and offers a quadratic speedup to the classical counterpart. The most famous application is grover search, in which one can find an item in an unordered list in \(O(\sqrt{N})\) uses of the grover oracle. This is in contrast to the best we can do classically which is to go over the entire list in \(O(N)\).

The optimal number of grover iterations needed (which maximizes the probability to be in a good state) depends on the initial probability to be in a 'good' state. Although the probability is not always known, it is still possible to achieve quadratic speedup by using randomization[1].

The special case of \(P\)(good_state)=\(\frac{1}{2}\)

Even though the Amplitude Amplification algorithm achieves a quadratic speedup, there is one case in which it can't find a valid solution due to how the search works, and that happens when exactly half of the states are good states.

Consider the arithmetic oracle \((x + y) \% 2 == 1\). Note that exactly half of the possible values of (x, y) answer that oracle (Those are the states where the least significant bit of x is different from the least significant bit of y). If we denote those "good states" as \(|g>\) and the "bad states" as \(|b>\), then we start the algorithm with the state:

\(|\Psi> = \frac{1}{\sqrt2} (|g> + |b>)\)

The oracle changes the sign of the good states, so then the state changes to:

\(O|\Psi> = \frac{1}{\sqrt2} (-|g> + |b>)\)

The diffuser \(I-2|s><s|\) changes the state to:

\(G|\Psi> = \frac{1}{\sqrt2} (|g> - |b>)\)

That means that each activation of the Grover operator will not change the probability of measuring a good state.

Syntax

Problem: amplitude_amplification

Parameters:

  • iterations: List[int]
  • growth_rate: float
  • sample_from_iterations: bool
  • num_of_highest_probability_states_to_check: int

growth_rate is used to generate iteration if the latter is missing. If sample_from_iterations is set to True, the powers are chosen uniformly from [0, iter - 1] for every iter in iterations. After measurement, num_of_highest_probability_states_to_check states are checked for validity, if any contains a satisfying assignment, it is returned as a solution.

Example 1:

To run amplitude amplification from the IDE, first select the Grover application suite in the synthesis tab. This brings up an example grover operator problem.

synthesis

Important: Inputs and Outputs

There is an important requirement for running grover problems which can be seen in the default example: inputs and outputs must be defined. that the inputs and Both the inputs and outputs of the grover block, and those of the entire model must also be defined. This allows the amplitude amplification algorithm to know which qubits need to be fed into the next loop iteration.

To execute the model, click the execution tab and select your desired hardware or simulator. Then select the amplitude amplification option and specify your execution parameters. For this example, just set the grown rate to 2 and leave the rest as default. You can then click on the "Run" button to execute the model.

execution

After execution completes, you can view the results in the results tab. The values found for each of the variables are shown in a table, as shown below.

results

Alternatively, you can run a grover problem using the SDK. This is shown in the snippet below.

from classiq import Model, Executor, RegisterUserInput, QReg
from classiq.model import Constraints
from classiq.builtin_functions import ArithmeticOracle, GroverOperator
from classiq.execution import (
    ExecutionPreferences,
    AmplitudeAmplification,
)

oracle_params = ArithmeticOracle(
    expression="a + b == 7 and a & b == 8",
    definitions=dict(
        a=RegisterUserInput(size=4), b=RegisterUserInput(size=4, is_signed=True)
    ),
    uncomputation_method="naive",
    qubit_count=22,
)
grover_params = GroverOperator(oracle_params=oracle_params)

model = Model()
in_wires = model.create_inputs(
    {name: QReg[reg.size] for name, reg in grover_params.inputs.items()}
)
out_wires = model.GroverOperator(params=grover_params, in_wires=in_wires)
model.set_outputs(out_wires)

circuit = model.synthesize(constraints=Constraints(max_width=22))
res = Executor(
    amplitude_amplification=AmplitudeAmplification(
        growth_rate=2, sample_from_iterations=False
    )
).execute(circuit)

This example runs amplitude amplification with the grover operator with the oracle for \(\verb!a + b == 7 and a & b == 8!\). The growth rate in the problem preferences is set to two which mean that number of grover operators applied in between consecutive tries will be multiplied by two. The first try will use two grover operator, the second four, the third eight, etc., until a valid solution is found or max number of tries is reached.

Possible output:

{
  "result": {
    "a": 11,
    "b": -4
  }
}

References

[1]G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, “Quantum Amplitude Amplification and Estimation,” arXiv:quant-ph/0005055, vol. 305, pp. 53–74, 2002, doi: 10.1090/conm/305/05215.