qcfront

qcfront is a Rust quantum computing framework built on roqoqo for circuit construction and QuEST (via roqoqo-quest) for high-performance statevector simulation.

This site is the published documentation for the project. It is generated with mdBook from the sources in the docs/ directory of the repository.

Status

The book is just getting started — most of the project's design notes currently live in the notes/ directory of the repository and will be migrated here as they are polished.

Source

• Repository: https://github.com/youyuanwu/qcfront
• License: MIT

Quantum Gates

A reference for the quantum gates used in qcfront — what they do mathematically and when to use them. For how gates map to physical hardware operations (microwave pulses, lasers, etc.), see GatePhysics.md.

All gates are available in roqoqo as roqoqo::operations::*.

Qubit Basics

A qubit has two basis states: |0⟩ and |1⟩. A general qubit state is α|0⟩ + β|1⟩ where α and β are complex numbers with |α|² + |β|² = 1. |α|² is the probability of measuring 0, |β|² of measuring 1.

The Bloch sphere visualizes a qubit as a point on a unit sphere:

• |0⟩ is the north pole
• |1⟩ is the south pole
• |+⟩ = (|0⟩+|1⟩)/√2 is on the equator

Gates are rotations and reflections on this sphere.

Bloch Sphere

Open bloch.html for an interactive 3D visualization. Drag to rotate, scroll to zoom, apply gates to see how they move the state vector.

• Z axis: |0⟩ (north) ↔ |1⟩ (south). Rz rotates around this axis.
• X axis: |+⟩ ↔ |−⟩. Rx rotates around this axis.
• Y axis: |+i⟩ ↔ |−i⟩. Ry rotates around this axis.
• Hadamard: reflects through the XZ plane (swaps Z and X axes).

Single-Qubit Gates

Pauli Gates

PauliX (X gate, NOT gate, bit-flip)

$$X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)X\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}\beta \\ \alpha \end{array}\right)$$

Flips the qubit: $X|0⟩=|1⟩$, $X|1⟩=|0⟩$. Like a classical NOT gate. On the Bloch sphere: 180° rotation around X.

#![allow(unused)]
fn main() {
circuit += PauliX::new(0); // flip qubit 0
}

PauliY (Y gate)

$$Y=\left(\begin{array}{cc}0& -i\\ i& 0\end{array}\right)Y\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}-i\beta \\ i\alpha \end{array}\right)$$

Flips the qubit and adds a phase: $Y|0⟩=i|1⟩$, $Y|1⟩=-i|0⟩$. 180° rotation around Y axis. Rarely used directly; appears in decompositions.

PauliZ (Z gate, phase-flip)

$$Z=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)Z\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}\alpha \\ -\beta \end{array}\right)$$

Doesn't change measurement probabilities — only flips the phase of |1⟩. $Z|0⟩=|0⟩$, $Z|1⟩=-|1⟩$. 180° rotation around Z.

Key insight: Z does nothing to basis states individually (they're eigenstates). It matters in superposition: $Z|+⟩=Z\frac{|0⟩+|1⟩}{\sqrt{2}}=\frac{|0⟩-|1⟩}{\sqrt{2}}=|-⟩$.

Hadamard Gate

Hadamard (H gate)

$$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)H\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\frac{1}{\sqrt{2}}\left(\begin{array}{c}\alpha +\beta \\ \alpha -\beta \end{array}\right)$$

Creates superposition from a basis state: $H|0⟩=\frac{|0⟩+|1⟩}{\sqrt{2}}=|+⟩$, $H|1⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}=|-⟩$.

The most important gate in quantum computing — almost every algorithm starts with H on all qubits. $H\cdot H=I$ (self-inverse).

#![allow(unused)]
fn main() {
// Create equal superposition over all 3-qubit states
for q in 0..3 {
    circuit += Hadamard::new(q);
}
}

Used in: Grover (initialization), Shor/QPE (counting register), Deutsch-Jozsa, Bernstein-Vazirani, teleportation.

Rotation Gates

RotateX(θ), RotateY(θ), RotateZ(θ)

Rotate the qubit by angle θ around the X, Y, or Z axis of the Bloch sphere. These are the continuous-parameter gates — any single-qubit gate can be decomposed into a sequence of rotations.

$$R_x(\theta )=\left(\begin{array}{cc}\cos \frac{\theta }{2}& -i\sin \frac{\theta }{2}\\ -i\sin \frac{\theta }{2}& \cos \frac{\theta }{2}\end{array}\right)R_x(\theta )\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}\alpha \cos \frac{\theta }{2}-i\beta \sin \frac{\theta }{2}\\ -i\alpha \sin \frac{\theta }{2}+\beta \cos \frac{\theta }{2}\end{array}\right)$$

$$R_y(\theta )=\left(\begin{array}{cc}\cos \frac{\theta }{2}& -\sin \frac{\theta }{2}\\ \sin \frac{\theta }{2}& \cos \frac{\theta }{2}\end{array}\right)R_y(\theta )\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}\alpha \cos \frac{\theta }{2}-\beta \sin \frac{\theta }{2}\\ \alpha \sin \frac{\theta }{2}+\beta \cos \frac{\theta }{2}\end{array}\right)$$

$$R_z(\theta )=\left(\begin{array}{cc}{e}^{-i\theta /2}& 0\\ 0& e^{i\theta /2}\end{array}\right)R_z(\theta )\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}\alpha e^{-i\theta /2}\\ \beta e^{i\theta /2}\end{array}\right)$$

$R_y$ changes amplitudes (measurement probabilities). $R_z$ changes only phases (no effect on probabilities). This is why Möttönen state preparation uses $R_y$ for amplitude trees and $R_z$ for phase trees.

How rotations move states on the Bloch sphere

Try these in bloch.html: start from |0⟩ and apply gates.

Key intuition:

• Ry(θ) changes how much |0⟩ vs |1⟩ — it moves the state between the poles. This controls measurement probabilities. Ry(π/2) takes |0⟩ → |+⟩ → |1⟩ → |−⟩ → |0⟩.
• Rz(θ) changes the phase between |0⟩ and |1⟩ without changing probabilities. It spins the state around the equator. Rz(π/2) takes |+⟩ → |+i⟩ → |−⟩ → |−i⟩ → |+⟩.
• Rx(θ) is like Ry but in the Z-Y plane.

This is why Möttönen state preparation uses Ry for amplitudes (setting probabilities) and Rz for phases (setting interference patterns).

Common rotation angles

Note: $\theta$ is the rotation angle, but the state-vector coefficients use $\theta /2$ (half-angle). $R_y(\pi /2)$ produces $\cos (\pi /4)|0⟩+\sin (\pi /4)|1⟩=|+⟩$.

Special cases:

• $R_x(\pi )=-iX$ (same as X up to global phase)
• $R_y(\pi )=-iY$
• $R_z(\pi )=-iZ$

#![allow(unused)]
fn main() {
use qoqo_calculator::CalculatorFloat;
// Rotate qubit 0 by π/4 around Y axis: tilt toward equator
circuit += RotateY::new(0, CalculatorFloat::Float(std::f64::consts::PI / 4.0));

// Rotate qubit 1 by π/2 around Z axis: add 90° relative phase
circuit += RotateZ::new(1, CalculatorFloat::Float(std::f64::consts::FRAC_PI_2));
}

Used in: State preparation (Möttönen decomposition uses Ry and Rz trees).

Phase Gates

SGate (√Z, phase gate)

$$S=\left(\begin{array}{cc}1& 0\\ 0& i\end{array}\right)S\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}\alpha \\ i\beta \end{array}\right)$$

Adds a $\pi /2$ phase to |1⟩. $S^2=Z$.

TGate (π/8 gate)

$$T=\left(\begin{array}{cc}1& 0\\ 0& e^{i\pi /4}\end{array}\right)T\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}\alpha \\ e^{i\pi /4}\beta \end{array}\right)$$

Adds a $\pi /4$ phase to |1⟩. $T^2=S$. Important for universal gate sets and fault-tolerant quantum computing (T gate is the expensive one to implement with error correction).

PhaseShiftGate1(θ)

$$P(\theta )=\left(\begin{array}{cc}1& 0\\ 0& e^{i\theta }\end{array}\right)P(\theta )\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)=\left(\begin{array}{c}\alpha \\ e^{i\theta }\beta \end{array}\right)$$

General phase shift. $S=P(\pi /2)$, $T=P(\pi /4)$, $Z=P(\pi )$.

Two-Qubit Gates

CNOT (Controlled-NOT, CX)

$$\text{CNOT}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)\text{CNOT}\left(\begin{array}{c}{a}_{00}\\ a_{01}\\ a_{10}\\ a_{11}\end{array}\right)=\left(\begin{array}{c}{a}_{00}\\ a_{01}\\ a_{11}\\ a_{10}\end{array}\right)$$

Flips the target qubit if the control qubit is $|1⟩$: $\text{CNOT}|c,t⟩=|c,t\oplus c⟩$. The fundamental entangling gate.

#![allow(unused)]
fn main() {
circuit += CNOT::new(0, 1); // control=0, target=1
}

Bell state creation: $H(0)$ then $\text{CNOT}(0,1)$ creates $(|00⟩+|11⟩)/\sqrt{2}$. This is the "hello world" of entanglement.

Used in: Everything — Bell states, teleportation, Grover diffusion, QPE controlled unitaries, state preparation (Möttönen decomposition), error correction.

ControlledPauliZ (CZ)

$$\text{CZ}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& -1\end{array}\right)\text{CZ}\left(\begin{array}{c}{a}_{00}\\ a_{01}\\ a_{10}\\ a_{11}\end{array}\right)=\left(\begin{array}{c}{a}_{00}\\ a_{01}\\ a_{10}\\ -a_{11}\end{array}\right)$$

Phase-flips only $|11⟩$. Symmetric: $\text{CZ}(a,b)=\text{CZ}(b,a)$. $\text{CZ}=(I\otimes H)\cdot \text{CNOT}\cdot (I\otimes H)$.

#![allow(unused)]
fn main() {
circuit += ControlledPauliZ::new(0, 1);
}

Used in: Grover phase oracle (multi-CZ marks solutions).

SWAP

$$\text{SWAP}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right)\text{SWAP}\left(\begin{array}{c}{a}_{00}\\ a_{01}\\ a_{10}\\ a_{11}\end{array}\right)=\left(\begin{array}{c}{a}_{00}\\ a_{10}\\ a_{01}\\ a_{11}\end{array}\right)$$

Exchanges two qubit states: $\text{SWAP}|a,b⟩=|b,a⟩$. Built from 3 CNOTs: $\text{SWAP}=\text{CNOT}(a,b)\cdot \text{CNOT}(b,a)\cdot \text{CNOT}(a,b)$.

Used in: Shor (controlled modular multiplication swaps work qubits).

Three-Qubit Gates

Toffoli (CCX, CCNOT)

$$\text{Toffoli}|c_1,c_2,t⟩=|c_1,c_2,t\oplus (c_1\wedge c_2)⟩$$

Flips the target only when both controls are $|1⟩$. Classical AND gate made reversible. Universal for classical computation.

#![allow(unused)]
fn main() {
// roqoqo convention: first arg is TARGET
circuit += Toffoli::new(2, 0, 1); // target=2, ctrl1=0, ctrl2=1
}

⚠️ roqoqo convention: Toffoli::new(target, control_1, control_2) — the first argument is the target, not a control. This differs from some other frameworks.

Used in: SAT oracle (clause evaluation), modular arithmetic.

ControlledControlledPauliZ (CCZ)

$$\text{CCZ}|a,b,c⟩=(-1{)}^{a\wedge b\wedge c}|a,b,c⟩$$

Phase-flips only $|111⟩$. Symmetric in all three qubits. $\text{CCZ}=(I\otimes I\otimes H)\cdot \text{Toffoli}\cdot (I\otimes I\otimes H)$.

Used in: Multi-target Grover oracle (marks multiple solutions).

Composite Operations

QFT (Quantum Fourier Transform)

Not a single gate but a built-in roqoqo operation that emits the full QFT circuit (Hadamards + controlled phase rotations + swaps).

#![allow(unused)]
fn main() {
let qubits = vec![0, 1, 2, 3];
circuit += QFT::new(qubits, true, true); // inverse=true, swap=true
}

Used in: Shor/QPE (inverse QFT extracts phase from counting register).

MeasureQubit

Collapses a qubit to |0⟩ or |1⟩ and records the classical result. Irreversible — destroys superposition.

#![allow(unused)]
fn main() {
circuit += MeasureQubit::new(0, "result".to_string(), 0);
//                          qubit  register_name     bit_index
}

PragmaGetStateVector

QuEST-specific: extracts the full state vector without measurement. Deterministic (no collapse). Used for verification/debugging.

#![allow(unused)]
fn main() {
circuit += DefinitionComplex::new("sv".to_string(), dim, true);
circuit += PragmaGetStateVector::new("sv".to_string(), None);
}

Ancilla Qubits

An ancilla (Latin: "servant") is a helper qubit added to a circuit that doesn't hold input or output data. Ancillas serve as scratch space for computations that can't be done directly on the data qubits.

Why ancillas are needed

Quantum gates are reversible — every gate has an inverse. But many useful operations (like AND, OR, multi-controlled gates) are irreversible classically. To make them reversible for a quantum circuit, we store intermediate results in ancilla qubits and uncompute them afterward.

Example: a 5-qubit controlled-Z can't be built from 1- and 2-qubit gates alone. The V-chain decomposition uses 3 ancilla qubits as a "Toffoli ladder" to cascade the AND of controls:

controls: ─●──●─────────────────●──●─
           │  │                 │  │
           ├──┤                 ├──┤
controls: ─●──┼──●──────────●──┼──●─
              │  │          │  │
ancilla₀: ───⊕──●──────────●──⊕─── (back to |0⟩)
              │  │          │  │
ancilla₁: ──────⊕──●────●──⊕────── (back to |0⟩)
                    │    │
ancilla₂: ─────────⊕─CZ─⊕──────── (back to |0⟩)
                      │
target:   ────────────●──────────── (phase flipped)
           forward    ↑   reverse
           pass      gate  pass

The golden rule: clean up after yourself

Ancillas must be returned to |0⟩ after use. If an ancilla is left entangled with the data qubits, subsequent operations (like the diffuser in Grover's algorithm) will act on the wrong subspace, silently producing wrong results.

The standard pattern is compute → use → uncompute:

1. Compute: fill ancillas with intermediate results
2. Use: apply the target operation (e.g., phase flip)
3. Uncompute: run the compute steps in reverse to erase ancillas

Since every quantum gate is its own inverse or has a known inverse, uncomputation is always possible — just replay the gates backward.

Common uses in qcfront

Ancilla vs workspace vs scratch

These terms are used interchangeably in the literature. In qcfront:

• ancilla = any non-data qubit
• The Oracle trait's num_ancillas() reports total scratch needed
• The driver allocates ancillas and passes them via apply()

Gate Universality

Any quantum computation can be built from:

• $\{H,T,\text{CNOT}\}$ — universal gate set (discrete)
• $\{R_y(\theta ),R_z(\theta ),\text{CNOT}\}$ — universal gate set (continuous)

qcfront's state preparation uses $\{R_y,R_z,\text{CNOT}\}$. The algorithms use $\{H,X,Z,\text{CNOT},\text{CZ},\text{Toffoli}\}$ for clarity.

Quick Reference

Gate Physics

How abstract quantum gates map to physical operations on real hardware. This doc connects the math in Gates.md to what actually happens inside a quantum computer.

The Abstraction Stack

Algorithm level:    circuit += Hadamard::new(0)
                         ↓
Gate level:         H = (1/√2)[[1,1],[1,-1]]    ← Gates.md lives here
                         ↓
Pulse level:        microwave pulse, 25 ns, 5.1 GHz
                         ↓
Physics level:      electromagnetic field rotates electron spin

Quantum software (including qcfront) works at the gate level. The hardware provider's compiler translates gates into physical pulses. This doc explains that bottom layer.

How Each Hardware Realizes Gates

Superconducting Qubits (IBM, Google, Rigetti)

Qubit: a tiny superconducting circuit (transmon) cooled to 15 mK. Two lowest energy levels of an anharmonic oscillator serve as |0⟩ and |1⟩. The energy gap corresponds to a microwave frequency, typically 4–6 GHz.

Single-qubit gates: Apply a calibrated microwave pulse at the qubit's resonance frequency. The pulse parameters control which gate is performed:

• $R_x(\pi )$ = full-power pulse at 0° phase for ~25 ns
• $R_x(\pi /2)$ = same pulse for half the duration (or half amplitude)
• $R_z(\theta )$ = no physical pulse needed — implemented by shifting the phase reference frame of all subsequent pulses (virtual-Z gate, ~0 ns)

Two-qubit gates (CNOT, CZ): Enabled by coupling two transmons through a resonator bus or direct capacitive coupling:

• Cross-resonance (IBM): Drive qubit A at qubit B's frequency. The off-resonant drive creates an effective ZX interaction.
• Tunable coupler (Google Sycamore): Flux-tune a coupler between two qubits to turn the interaction on/off.
• Typical CNOT duration: 200–400 ns (much slower than single-qubit gates).

Why CNOT is expensive: Single-qubit gates take ~25 ns with >99.9% fidelity. Two-qubit gates take ~300 ns with ~99–99.5% fidelity. This is why gate counts (especially CNOT counts) matter for circuit depth.

Trapped Ions (IonQ, Quantinuum)

Qubit: a single ion (e.g., Yb⁺, Ba⁺, Ca⁺) trapped in an electromagnetic field. Two hyperfine or optical energy levels serve as |0⟩ and |1⟩.

Single-qubit gates: Focused laser beams drive transitions between the two levels (Rabi oscillation):

$R_y(\pi /2)$: laser pulse of duration $t=\pi /(2\Omega )$ where $\Omega$ is the Rabi frequency (~MHz range). Typical gate time: 1–10 μs.

Two-qubit gates (Mølmer-Sørensen / XX gate): Two laser beams create a spin-dependent force on the ion chain's shared vibrational mode (phonon bus). The ions' motion mediates entanglement:

1. Lasers excite the collective motion of two ions
2. Spin-motion coupling entangles the internal states
3. Motion returns to ground state, leaving only spin entanglement

Gate time: 50–200 μs. Fidelity: 99–99.9%.

Key difference from superconducting: All-to-all connectivity — any ion can interact with any other ion (no nearest-neighbor restriction). But gates are much slower (~1000× longer than superconducting).

Photonic (Xanadu, PsiQuantum)

Qubit: a single photon. Unlike other platforms where the qubit persists in a trap or circuit, a photonic qubit is short-lived — it is generated on demand, flies through optical components at the speed of light, and is destroyed upon detection. The entire computation happens during the photon's flight (~nanoseconds).

Photon source: Single photons are generated from quantum dots, spontaneous parametric down-conversion (SPDC) crystals, or four-wave mixing in silicon waveguides. Generating truly single photons reliably is itself a major engineering challenge.

Encoding varies:

• Polarization: horizontal |H⟩ = |0⟩, vertical |V⟩ = |1⟩
• Path: photon in upper waveguide = |0⟩, lower = |1⟩
• Time-bin: early arrival = |0⟩, late = |1⟩

Single-qubit gates: Optical elements manipulate the photon in flight:

Two-qubit gates: The hard part. Photons don't naturally interact. Approaches:

• Measurement-based (KLM protocol): Entangle via post-selected measurements on ancilla photons. Probabilistic — requires many attempts.
• Fusion gates: Merge photonic resource states via Bell measurements.

Because two-qubit gates are probabilistic, many photonic quantum computers use measurement-based quantum computing (MBQC) instead of the circuit model: generate a large entangled cluster state of many photons, then compute by measuring individual photons in chosen bases. The computation emerges from the measurement pattern, not from applying gates in sequence.

Neutral Atoms (QuEra, Pasqal)

Qubit: individual atoms (Rb, Cs) held in optical tweezers (focused laser beams). Hyperfine ground states or Rydberg excited states encode |0⟩ and |1⟩.

Single-qubit gates: Raman transitions via laser pulses (similar to trapped ions).

Two-qubit gates (Rydberg blockade): Excite one atom to a highly excited Rydberg state. The enormous electric dipole of the Rydberg atom shifts the energy levels of a nearby atom, preventing double excitation:

• If atom A is in Rydberg state, atom B cannot be excited → CZ gate
• Blockade radius: ~5–10 μm
• Gate time: ~0.5–1 μs

Gate Fidelities by Platform (approximate, 2024)

These numbers determine how many gates you can apply before errors accumulate. With 99.5% two-qubit fidelity, a 100-CNOT circuit has expected fidelity ~0.995¹⁰⁰ ≈ 0.61 — already marginal.

Native Gate Sets

Hardware doesn't implement arbitrary gates directly. Each platform has a native gate set — the physically calibrated operations. The compiler decomposes your circuit into these:

Virtual-Z optimization: On most superconducting platforms, $R_z$ is "free" — it's implemented by changing the software phase reference, not by applying a physical pulse. Compilers exploit this aggressively.

Measurement

Standard measurement: Project onto Z basis (|0⟩ or |1⟩).

Measuring in other bases: To measure in the X basis, apply H before measuring in Z. To measure in an arbitrary basis defined by angles $(\theta ,\varphi )$, apply $R_z(-\varphi )\cdot R_y(-\theta )$ before measuring. The detector doesn't rotate — the state does.

Why This Matters for Software

1. Gate count → circuit fidelity: More gates = more error accumulation. Our Möttönen state preparation uses O(2ⁿ) CNOTs — only practical for small qubit counts on current hardware.

2. Connectivity constraints: Superconducting qubits have nearest-neighbor connectivity. A CNOT between distant qubits requires SWAP gates to move data — the transpiler adds these automatically. Trapped ions don't have this problem.

3. Native gate translation: When we export QIR for Azure Quantum, the hardware provider's compiler handles translation to native gates. Our circuit uses {H, CNOT, Ry, Rz, Toffoli} which all decompose cleanly.

4. Virtual-Z means Rz is free: Circuit optimizations that convert gates into Rz equivalents save real time on superconducting hardware.

Beyond Qubits: Qudits

Qubits use 2 energy levels, but physical systems often have more. A qudit uses d levels (qutrit for d=3, ququart for d=4). A single qutrit carries ${\log }_{2}3\approx 1.58$ bits — more information per particle, potentially fewer particles and fewer two-particle gates.

Why qubits still dominate: Error correction for d>2 is harder — each additional level adds decay and leakage channels. The entire software stack (algorithms, compilers, cloud APIs) assumes d=2. Superconducting transmons actively avoid their third level by engineering the anharmonicity so the 0↔1 transition frequency differs from 1↔2. The marginal information gain from d=3 doesn't yet justify rebuilding the ecosystem.

qcfront and roqoqo are qubit-only, matching the industry standard.

Sources

• Krantz et al., "A Quantum Engineer's Guide to Superconducting Qubits", arXiv:1904.06560 (2019)
• Bruzewicz et al., "Trapped-ion quantum computing: Progress and challenges", arXiv:1904.04178 (2019)
• Saffman, "Quantum computing with neutral atoms", National Science Review (2019)
• IBM Quantum documentation: https://docs.quantum.ibm.com
• Google Quantum AI: https://quantumai.google

Grover's Algorithm

A beginner-friendly guide to Grover's quantum search — what it does, why it's faster than classical search, and how it works step by step. For gate definitions used below, see Gates.md.

The Core Question: How Many Queries Does It Take?

Suppose you have a black-box function $f(x)$ that answers "yes" or "no" for each input. You want to find an $x$ where $f(x)=1$. The only way to learn anything about $f$ is to query it — feed in an $x$ and read the answer. Every query costs time (and on real hardware, money).

The goal is to minimize the number of queries.

Classically, if there are $N$ possible inputs and only one correct answer, you have no choice but to try inputs one at a time. On average you need $N/2$ queries, and in the worst case all $N$.

Grover's algorithm solves this with only $O(\sqrt{N})$ queries by exploiting quantum superposition — querying the function on all inputs simultaneously and then amplifying the answer that comes back "yes."

This is a quadratic speedup. Not exponential like Shor's factoring algorithm, but it applies to any problem that can be phrased as "search for an input satisfying some condition" — database lookup, constraint satisfaction (SAT), optimization, cryptographic key search, and more. That generality makes Grover one of the most broadly useful quantum algorithms.

The Oracle: A Quantum Yes/No Black Box

There are two layers to understand:

1. $f(x)$ — the abstract function that defines the problem. It maps each input to 0 ("no") or 1 ("yes"). For example, "is $x$ a prime factor of 21?" This is pure math — it says what you're searching for.

2. $U_f$ — the oracle circuit that implements $f$ on a quantum computer. It's the physical realization — a sequence of quantum gates that evaluates $f$ on a superposition of all inputs at once.

You don't need to know the internals of $f$ to understand Grover's algorithm — it works with any yes/no function. That's why $f$ is called a "black box."

The key trick is how $U_f$ reports its answer. Instead of writing a classical 0 or 1 to an output register, it flips the phase (sign) of solution states:

$$U_f|x⟩=(-1{)}^{f(x)}|x⟩$$

• If $f(x)=0$ (not a solution): the state is unchanged
• If $f(x)=1$ (a solution): the amplitude gets a minus sign

This is called a phase oracle. The minus sign is invisible if you measure immediately — $|-\alpha {|}^2=|\alpha {|}^2$ — but it creates a pattern that the rest of the algorithm can exploit.

Why a phase flip instead of a bit flip? Because Grover's algorithm works by interference. The negative amplitude of the solution state interferes constructively with itself during the diffuser step (below), causing its probability to grow. A classical 0/1 output can't produce this interference effect.

Building real oracle circuits: For a simple "find value 5" search, $U_f$ is just a few X and multi-controlled-Z gates (shown in the walkthrough below). For harder problems like SAT, $U_f$ encodes the entire formula as a reversible circuit — see sat_grover.rs for a working example.

Key Idea: Amplitude Amplification

Quantum states carry amplitudes (complex numbers whose squares give probabilities). Grover's algorithm works by manipulating amplitudes:

1. Start with all items equally likely (uniform superposition)
2. Repeatedly shrink the amplitude of wrong answers and grow the amplitude of right answers
3. Measure — the right answer pops out with high probability

Each "shrink + grow" cycle is one Grover iteration. After $\lfloor \frac{\pi }{4}\sqrt{N/M}\rfloor$ iterations (where $M$ is the number of solutions), the success probability is nearly 100%.

The Circuit

     ┌───┐ ┌────────┐ ┌─────────┐       ┌────────┐ ┌─────────┐ ┌───┐
|0⟩──┤ H ├─┤        ├─┤         ├─ ... ─┤        ├─┤         ├─┤ M ├
     └───┘ │        │ │         │       │        │ │         │ └───┘
     ┌───┐ │ Oracle │ │ Diffuser│       │ Oracle │ │ Diffuser│ ┌───┐
|0⟩──┤ H ├─┤  U_f   ├─┤  U_s    ├─ ... ─┤  U_f   ├─┤  U_s    ├─┤ M ├
     └───┘ │        │ │         │       │        │ │         │ └───┘
     ┌───┐ │        │ │         │       │        │ │         │ ┌───┐
|0⟩──┤ H ├─┤        ├─┤         ├─ ... ─┤        ├─┤  U_s    ├─┤ M ├
     └───┘ └────────┘ └─────────┘       └────────┘ └─────────┘ └───┘
           ├────── one iteration ──────┤
                    × k iterations

Three stages:

1. Initialization — Hadamard on every qubit → uniform superposition
2. Grover iterations — repeat (Oracle + Diffuser) $k$ times
3. Measurement — read out the answer

Step-by-Step Walkthrough (3 qubits, target = 5)

Step 1: Superposition

Apply $H^{\otimes n}$ to $|000⟩$:

$$|s⟩=\frac{1}{\sqrt{8}}\sum _{x=0}^7|x⟩$$

Every state has amplitude $\frac{1}{\sqrt{8}}\approx 0.354$. Probability of measuring any specific state is $\frac{1}{8}=12.5\%$.

Step 2: Oracle ($U_f$) — "Mark" the Winner

The oracle flips the sign (phase) of the solution:

$$U_f|x⟩=(-1{)}^{f(x)}|x⟩$$

For target $|5⟩=|101⟩$:

No measurement probabilities change yet — the minus sign is hidden in the phase. But it sets up the diffuser to amplify the target.

How the oracle circuit works

To flip only $|101⟩$:

1. Apply $X$ to qubits where the target bit is 0 (qubit 1) — this maps $|101⟩\to |111⟩$
2. Apply a multi-controlled-$Z$ gate (MCZ) — flips the phase of $|111⟩$
3. Undo the $X$ gates

In qcfront, MCZ is built from Toffoli + CZ gates via a V-chain decomposition (see multi_cz.rs).

Step 3: Diffuser ($U_s$) — "Amplify" the Winner

The diffuser reflects every amplitude about the mean:

$$U_s=2|s⟩⟨s|-I$$

where $|s⟩=\frac{1}{\sqrt{N}}{\sum }_x|x⟩$ is the uniform superposition.

Concrete math for our example:

After the oracle, the mean amplitude is:

$$\bar{a}=\frac{7\times \frac{1}{\sqrt{8}}+1\times (-\frac{1}{\sqrt{8}})}{8}=\frac{6}{8\sqrt{8}}=\frac{3}{4\sqrt{8}}$$

The diffuser maps each amplitude $a_x\to 2\bar{a}-a_x$:

• Non-targets: $2\bar{a}-\frac{1}{\sqrt{8}}\approx 0.177$
• Target $|5⟩$: $2\bar{a}+\frac{1}{\sqrt{8}}\approx 0.884$

After 1 iteration, the target has amplitude $\approx 0.884$, giving $P(|5⟩)\approx 78\%$.

How the diffuser circuit works

$$U_s=H^{\otimes n}\cdot (2|0⟩⟨0|-I)\cdot H^{\otimes n}$$

Implemented as: H on all → X on all → MCZ → X on all → H on all.

This is the same MCZ gate used in the oracle, but sandwiched in Hadamard + X gates to reflect about $|0⟩$ instead of $|1\dots 1⟩$.

Step 4: More Iterations

For $n=3$, $N=8$, $M=1$:

$$k=\lfloor \frac{\pi }{4}\sqrt{\frac{8}{1}}\rfloor =\lfloor 2.22\rfloor =2$$

Our implementation uses $k=2$ for 3 qubits, achieving >94% success.

Step 5: Measure

Measure all qubits → read out the binary string → decode as integer. With 94.5% probability, you get 5 ($=101_2$).

The Geometry

Grover's algorithm has an elegant geometric interpretation in a 2D plane spanned by:

• $|w⟩$ = the target state (or uniform superposition of all targets)
• $|w^{\perp }⟩$ = the uniform superposition of non-targets

The initial state $|s⟩$ makes angle $\theta /2$ with $|w^{\perp }⟩$ where $\sin (\theta /2)=\sqrt{M/N}$.

Each Grover iteration rotates the state by $\theta$ toward $|w⟩$:

        |w⟩
         ↑
         |   /  ← after 2 iterations (angle 5θ/2)
         |  /
         | /  ← after 1 iteration (angle 3θ/2)
         |/
    ─────┼───── |w⊥⟩
   θ/2 ↗
  |s⟩ = initial state

After $k$ iterations, the angle is $(2k+1)\theta /2$. The algorithm works best when this angle is close to $\pi /2$ (pointing at $|w⟩$).

Overshooting: If you apply too many iterations, the state rotates past $|w⟩$ and success probability drops. This is why the optimal iteration count matters — Grover is not "more iterations = better."

Multiple Solutions

When there are $M>1$ solutions, the optimal iteration count drops:

$$k=\lfloor \frac{\pi }{4}\sqrt{\frac{N}{M}}\rfloor$$

When $M>N/2$, random measurement is already likely to succeed, so $k=0$ (no Grover iterations at all).

Oracle Complexity

The oracle is the expensive part. Grover's speedup is measured in oracle queries, not total gates. A single oracle query for our simple "find value $x$" costs just $O(n)$ gates (X gates + one MCZ). But for real problems (SAT, optimization), the oracle encodes problem logic and can be much more complex.

SAT oracle example: Given a CNF formula, the oracle computes the formula on a superposition of all assignments. If the formula is satisfiable, Grover finds a satisfying assignment in $\sqrt{N/M}$ oracle calls instead of exhaustive search. See sat_grover.rs for a working example.

What Grover Cannot Do

• Unknown $M$: If you don't know how many solutions exist, you can't compute the optimal iteration count. Workaround: quantum counting (QPE on the Grover operator) to estimate $M$ first, or randomized approaches with $O(\sqrt{N})$ expected queries.

• Unstructured search only: Problems with structure (sorting, graph search) often have better classical algorithms. Grover shines when the only access to the problem is a black-box oracle.

• No exponential speedup: The $\sqrt{N}$ speedup is provably optimal for unstructured search (BBBV theorem). No quantum algorithm can do better with black-box oracle access.

qcfront Implementation

See GroverSearch.md for implementation details, API reference, and the Oracle trait design.

Further Reading

• Grover, L. K. (1996). "A fast quantum mechanical algorithm for database search." Proceedings of STOC '96, pp. 212–219.
• Nielsen & Chuang, Quantum Computation and Quantum Information, Chapter 6: "Quantum search algorithms."
• Boyer et al. (1998). "Tight bounds on quantum searching." Fortschritte der Physik, 46(4-5), pp. 493–505.

Bloch Sphere

An interactive 3D visualization of single-qubit states on the Bloch sphere. Click the link below to open it in a new tab — it uses three.js loaded from a CDN to render the sphere and animate gate operations.

Open the interactive Bloch sphere →

What it shows

• The unit sphere with $|0⟩$ at the north pole and $|1⟩$ at the south pole.
• The state vector for a single qubit, with controls to apply $X$, $Y$, $Z$, $H$, $S$, and $T$ gates and watch the vector rotate.
• The mapping between gate operations and rotations of the sphere (see Gate Physics for the underlying math).

Source

The source is a single self-contained HTML file at docs/theory/bloch.html in the repository.