qbraid_algorithms.amplitude_amplification

Amplitude Amplification Algorithm

Amplitude Amplification

This module provides implementations of amplitude amplification algorithms, including Grover’s algorithm and general amplitude amplification techniques. Grover’s algorithm provides quadratic speedup for searching unsorted databases by repeatedly applying an oracle that marks target states and diffusion operator that inverts amplitudes about average. General Amplitude Amplification works with arbitrary oracles and state preparation operators.

FORMULATION

Grover’s

For a search space of \(N\) items containing \(M\) target solutions:

  • Oracle operator: \(O_f = I - 2|f\rangle\langle f|\) marks target states

  • Diffusion operator: \(D = 2|s\rangle\langle s| - I\) where \(|s\rangle = \frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}|i\rangle\)

  • Grover operator: \(G = D \cdot O_f\)

  • Optimal iterations: \(k \approx \frac{\pi}{4}\sqrt{\frac{N}{M}}\)

  • Success probability: approaches 1 after \(k\) iterations

General Amplitude Amplification

For initial state \(|\psi\rangle\) and target subspace spanned by good states:

  • State preparation: \(A|\psi\rangle = \sqrt{1-a}|\psi_0\rangle + \sqrt{a}|\psi_1\rangle\)

  • Reflection operators:

    • \(S_{\psi} = I - 2|\psi\rangle\langle\psi|\) reflects about initial state

    • \(S_{\chi} = I - 2|\chi\rangle\langle\chi|\) reflects about good states

  • Amplitude amplification operator: \(Q = -A S_{\psi} A^{\dagger} S_{\chi}\)

  • Amplified amplitude: grows as \(\sin((2k+1)\theta)\) where \(\sin^2(\theta) = a\)

Classes

AALibrary(*args, **kwargs)

Amplitude Amplification Library that implements Grover's algorithm and general amplitude amplification