Iterative Quantum Amplitude Estimation (IQAE) — Paper Implementation Challenge

[avd1729]

Quantum Amplitude Estimation Without Phase Estimation — Paper Implementation Challenge

Author: @avd1729

---

Overview

Quantum Amplitude Estimation (QAE) is one of the most important quantum primitives, offering a quadratic speedup over classical Monte Carlo methods. The standard QAE algorithm however depends on Quantum Phase Estimation (QPE), which requires deep circuits with many ancilla qubits — making it largely impractical on today's hardware.

This proposal implements Iterative QAE (IQAE) — a QPE-free, NISQ-friendly reformulation that achieves the same theoretical speedup using shallow, repeated Grover circuits combined with classical Maximum Likelihood Estimation (MLE). This is a clean, self-contained algorithm that maps naturally onto Classiq's synthesis framework.

---

Research Paper

Title: Quantum Amplitude Estimation without Phase Estimation
Authors: Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Takumi Onodera, Naoki Yamamoto
Link: https://arxiv.org/abs/1904.10246
Published: Quantum Information Processing, 2020

---

Motivation & Novelty

Standard QAE estimates the amplitude $a = \sin^2(\theta)$ encoded by a unitary $\mathcal{A}$ such that:

$$\mathcal{A} |0\rangle = \sqrt{1-a}|\psi_0\rangle|0\rangle + \sqrt{a}|\psi_1\rangle|1\rangle$$

The canonical algorithm uses QPE on the Grover operator:

$$Q = \mathcal{A} S_0 \mathcal{A}^\dagger S_\chi$$

to extract $\theta$ with $O(1/\epsilon)$ queries. But QPE demands $m$ ancilla qubits and controlled-$Q^{2^k}$ operations — a circuit depth that is completely infeasible on near-term devices.

IQAE's novelty is eliminating QPE entirely. Instead it:

• Runs $Q^{k_i} \mathcal{A}$ circuits for a schedule of increasing $k_i$ values
• Collects binary measurement outcomes
• Feeds them into a Maximum Likelihood Estimator to iteratively narrow a confidence interval $[\theta_l, \theta_u]$ on $\theta$

This achieves the same $O(1/\epsilon)$ query complexity with no ancilla qubits and no controlled unitaries — a fundamental practical improvement.

---

Technical Approach

Step 1 — Oracle Construction

Define a state preparation oracle $\mathcal{A}$ that encodes amplitude $a$:

$$\mathcal{A}|0\rangle = \sqrt{1-a}|0\rangle + \sqrt{a}|1\rangle$$

Step 2 — Grover Iterate

Build the Grover operator $Q$:

$$Q = -\mathcal{A} S_0 \mathcal{A}^\dagger S_\chi, \quad S_\chi = I - 2|\psi_1\rangle\langle\psi_1|, \quad S_0 = I - 2|0\rangle\langle 0|$$

For each iteration $i$, apply $Q^{k_i}$ before measuring. The probability of measuring $|1\rangle$ is:

$$P(1 | k_i) = \sin^2((2k_i + 1)\theta)$$

Step 3 — MLE over iterations

Given measurement outcomes $h_i$ successes out of $N_i$ shots at depth $k_i$, the log-likelihood is:

$$\mathcal{L}(\theta) = \sum_i \left[ h_i \log \sin^2((2k_i+1)\theta) + (N_i - h_i)\log\cos^2((2k_i+1)\theta) \right]$$

Maximize $\mathcal{L}(\theta)$ over the current confidence interval to update $[\theta_l, \theta_u]$ until $|\theta_u - \theta_l| < \epsilon$.

Step 4 — Final Estimate

$$\hat{a} = \sin^2(\hat{\theta}), \quad \hat{\theta} = \arg\max_\theta \mathcal{L}(\theta)$$

---

Outcome

• A fully working Jupyter Notebook implementing IQAE end-to-end with the Classiq SDK
• .qmod file exported via write_qmod()
• Convergence plots: $|\hat{a} - a|$ vs. number of oracle calls for varying $\epsilon$
• Gate count comparison via count_ops() between IQAE and standard QPE-based QAE
• (Bonus) A finance-flavored extension estimating the expected payoff of a simple derivative

---

Why This is a Good Fit for Classiq

Classiq's core strength is expressing quantum algorithms at a high level of abstraction without manually managing gate-level decomposition. IQAE is a perfect candidate because:

• The Grover iterate $Q = -\mathcal{A} S_0 \mathcal{A}^\dagger S_\chi$ is naturally expressed as a composition of high-level Classiq functions using @qfunc, without needing manual gate decomposition
• The iterative circuit structure — varying $k_i$ Grover applications — maps cleanly onto parameterized circuit synthesis
• Classiq's count_ops() makes the gate efficiency story quantitatively demonstrable
• The algorithm is modular: the oracle $\mathcal{A}$ can be swapped out for any application domain (finance, ML, optimization), making this a reusable template for the community
• No QPE means no controlled multi-qubit gates, keeping circuits within Classiq's noise-aware optimization sweet spot

---