amplitude_estimation

amplitude_estimation#

Functionality#

Quantum Amplitude Estimation (QAE) [1] is an extremely useful algorithm which provides a quadratic speedup over classical computers for wide classes of problems which would typically be solved by classical Monte Carlo simulations. This algorithm uses two ubiquitous elements of quantum algorithms: Quantum Amplitude Amplification (QAA), and Quantum Phase Estimation (QPE).

The Quantum Amplitude Estimation Algorithm was first proposed by Brassard et al. as an extension of Grover’s search algorithm. The goal of this algorithm is to estimate a value \(a\) given a unitary operation \(\mathcal{A}\) defined as:

\[ \ket{\psi} \equiv \mathcal{A}\ket{0}_{n+1} = \sqrt{1-a}\ket{0}_1\ket{\psi_0}_n + \sqrt{a}\ket{1}_1\ket{\psi_1}_n, \]

where \(\ket{\psi_0}_n\) and \(\ket{\psi_1}_n\) are any two states on \(n\) qubits, not necessarily orthogonal. In this context, we can think of \(\mathcal{A}\) as distinguishing between the “bad state” \(\ket{0}_1\ket{\psi_0}_n\) and “good state” \(\ket{1}_1\ket{\psi_1}_n\) using the value of an additional qubit. Therefore, \(a\) is the probability of measuring a good state from the prepared state \(\mathcal{A}\ket{0}_{n+1}\).

amplitude_estimation.py#

Callee: AmplitudeEstimation

To begin with, we display the relation betweeen the registers and thier indexes used in this implementation:

Index

\(0 \sim (m-1)\)

\(m \sim (m+n-1)\)

\(m+n\)

Register

Counting qubits

State qubits

Objective qubit

To find an estimation of \(a\), we first use QAA to generate a unitary operator \(Q\) which encodes \(a\) into a phase as \(\theta_a = \sin^{-1}\sqrt{a}\). We can do this through calls to our oracle \(A\) and its inverse; we do not require knowledge of \(a\) to generate \(Q\). By using PE, we can determine this phase. We then measure out the counting qubits to obtain an integer \(y\) and associated estimation

\[\begin{split} \tilde{\theta}_a \approx \begin{cases} \frac{\pi y}{2^m}, & \text{if } 0 \leq y \leq 2^{m-1} \\ \pi - \frac{\pi y}{2^m}, & \text{if } 2^{m-1} < y < 2^m \end{cases} \end{split}\]

where the above two cases result from the symmetry of the phase involved in QPE. We finally get an estimation of \(a\) by evaluating

\[ \tilde{a} \approx \sin^2(\tilde{\theta}_a). \]

More details about the implementation of QAA and QPE can be found in [2].

Note:

  • The state initialization is included in the program, which is associated with the input a (i.e., \(a\)) as the reference of the amplitude \(\tilde{a}\) to be estimated. In other words, this program implements a self-testing instance of the QAE algorithm with known ground truth.

  • According to the literature [1], the error bound of the estimation \(\tilde{a}\) can be proven as

    \[ \left|\tilde{a} - a\right| \leq \frac{2\pi\sqrt{a(1-a)}}{2^m} + \frac{\pi^2}{2^{2m}}, \]

    with probability at least \(8/\pi^2\), where \(m\) is the number of counting qubits. For the estimated theta \(\tilde{\theta}_a\), the error bound is

    \[ \left|\tilde{\theta}_a - \theta_a\right| \leq \frac{\pi}{2^m}. \]

    with probability at least \(8/\pi^2\).

Test expectations:

Repeated measurements yield a histogram over \(y\) with dominant peaks near the phase corresponding to \(a\), enabling it to converge to the true amplitude as \(m\) grows.

Doc references: [2]

API#

qolumbina.programs.amplitude_estimation.amplitude_estimation#

class AmplitudeEstimation(num_state_qubits, num_counting_qubits, a, psi_zero=None, psi_one=None, if_barrier=False, name=None)[source]#

Bases: QuantumCircuit

Amplitude Estimation Circuit via Phase Estimation.

This class creates a Quantum Circuit implementing the Amplitude Estimation algorithm using the Phase Estimation approach.

Parameters:

  • num_state_qubits (int) – Number of state qubits \(n\).

  • num_counting_qubits (int) – Number of counting qubits \(m\) for phase estimation.

  • a (float) – The amplitude \(a\) to be estimated (\(0 \leq a \leq 1\)). This argument determines the probability of measuring a good state from the prepared state \(\mathcal{A}\ket{0}_{n+1}\).

  • psi_zero (str | None) – Bitstring representing the \(\ket{\psi_0}\) state. If None, defaults to '0'*num_state_qubits.

  • psi_one (str | None) – Bitstring representing the \(\ket{\psi_1}\) state. If None, defaults to '1'*num_state_qubits.

  • if_barrier (bool) – Whether to include barriers in the circuit for better visualization.

  • name (str | None) – Optional name for the circuit.

Raises:

ValueError – If a is not between 0 and 1.

A_gens(num_state_qubits, a, psi_zero=None, psi_one=None)[source]#
Ctrl_Q(num_state_qubits, A_circ)[source]#
Contents