Category: search | Difficulty: advanced | Qubits: 4 | Gates: 16 | Depth: 10
Quantum amplitude estimation generalises Grover's algorithm. Given an operator A such that A|0⟩ = √(1-a)|0⟩|good=0⟩ + √a|1⟩|good=1⟩, the algorithm estimates a with quadratic speedup over classical Monte Carlo. It applies QPE to the Grover operator Q = -AS₀A†Schi. This circuit uses 3 evaluation qubits for ~3 bits of precision and a single system qubit prepared with Ry(π/4) (a = sin²(π/8)).
Binary fraction close to 1/8=0.125 (a ≈ 0.146 → phase ≈ 0.125)
The OpenQASM 2.0 circuit is in circuit.qasm.
OPENQASM 2.0;
include "qelib1.inc";
// Amplitude estimation for a = sin^2(pi/8) ~ 0.146
// 3 evaluation qubits (anc[0..2]) + 1 system qubit (sys[0])
qreg anc[3];
qreg sys[1];
creg c[3];
// Superpose evaluation register
h anc[0]; h anc[1]; h anc[2];
// Prepare initial system state A|0> = Ry(pi/4)|0>
ry(0.7853981633974483) sys[0];
// Controlled Q^(2^k) approximated as controlled Ry(2^k * pi/4)
// Controlled-Q^1 from anc[2] (LSB)
cry(1.5707963267948966) anc[2],sys[0];
// Controlled-Q^2 from anc[1]
cry(3.141592653589793) anc[1],sys[0];
// Controlled-Q^4 from anc[0] wraps to identity (4*pi/4 = pi -> Rz equivalent)
// (omitted for clarity; adds near-zero phase for this angle)
// Inverse QFT on evaluation register
swap anc[0],anc[2];
h anc[0];
cu1(-1.5707963267948966) anc[1],anc[0];
h anc[1];
cu1(-0.7853981633974483) anc[2],anc[0];
cu1(-1.5707963267948966) anc[2],anc[1];
h anc[2];
measure anc[0] -> c[0];
measure anc[1] -> c[1];
measure anc[2] -> c[2];
amplitude-estimation qpe grover monte-carlo
MIT — part of the OpenQC Algorithm Catalog.