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: Optional[List[int],int]
  • growth_rate: Optional[float]
  • sample_from_iterations: Optional[bool]
{
  "amplitude_amplification": {
    "iterations": [1, 2, 3, 4],
    "sample_from_iterations": false
  }
}

Example 1:

To run amplitude amplification, first create a grover operator. Second, in the configuration file, write the amplitude amplification params, use the execute command and select the grover operator generation folder.

problem.qmod

{
    "constraints": {
      "max_width": 21,
      "max_depth": 1400
    },
    "logic_flow": [
        {
            "function": "GroverOperator",
            "function_params": {
                "oracle": {
                    "expression": "a + b == 7 and a & b == 8",
                    "definitions": {
                        "a": {
                            "size": 4
                        },
                        "b": {
                            "size": 4,
                            "is_signed": true
                        }
                    },
                    "uncomputation_method": "naive",
                    "qubit_count": 21
                },
                "state_preparation": null
            }
        }
    ]
}

example.exct

{
  "preferences": {
    "simulator": "aer_simulator",
    "amplitude_amplification": {
      "growth_rate": 2,
      "sample_from_iterations": false
    }
  }
}
from classiq import ModelDesigner, Executor
from classiq.builtin_functions import ArithmeticOracle, GroverOperator
from classiq.interface.generator.arith.arithmetic import RegisterUserInput
from classiq.interface.executor.execution_preferences 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=21,
)
grover_params = GroverOperator(oracle=oracle_params)

model_designer = ModelDesigner()
model_designer.GroverOperator(grover_params)

circuit = model_designer.synthesize()
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.