Quantum Circuits & Measurement

The quantum circuit model is the standard framework for describing quantum algorithms. In a circuit diagram, horizontal wires represent qubits, and boxes or symbols placed on these wires represent quantum gates. Time flows from left to right: the state is initialized on the far left, gates are applied in sequence, and measurements (if any) appear on the far right.

A circuit is characterized by its width—the number of qubits—and its depth—the number of time steps or layers of gates needed when executed in parallel. These metrics are crucial for analyzing the complexity and feasibility of a quantum algorithm on near-term hardware.

Why circuits instead of Turing machines? Quantum Turing machines are theoretically important, but the circuit model is more practical for algorithm design. We typically consider uniform families of circuits $\{C_n\}$, where a classical computer can efficiently generate the description of $C_n$ from the input size $n$. This captures the notion of a quantum algorithm that can handle inputs of arbitrary size.

• • Wires = qubits, boxes = unitary gates, left-to-right = time evolution.
• • Circuit width: number of horizontal wires (qubits).
• • Circuit depth: minimum number of layers when gates are parallelized.
• • Uniform families of circuits connect the circuit model to computational complexity.

A projective measurement is described by an observable $\hat{M}$, which is a Hermitian operator with spectral decomposition $\hat{M} = \sum_m m P_m$, where $P_m$ is the projector onto the eigenspace of $\hat{M}$ with eigenvalue $m$. According to the measurement postulate, measuring the observable $\hat{M}$ on a system in state $\lvert\psi\rangle$ yields outcome $m$ with probability given by the Born rule.

The probability of obtaining outcome $m$ is $p(m) = \langle\psi\vert P_m \vert\psi\rangle$. After obtaining outcome $m$, the state of the system collapses to the post-measurement state $P_m \lvert\psi\rangle / \sqrt{p(m)}$. This is the standard von Neumann measurement model used throughout quantum computing.

As a concrete example, consider measuring the Pauli-$Z$ observable on the single-qubit state $\lvert\psi\rangle = \alpha\lvert 0 \rangle + \beta\lvert 1 \rangle$. The spectral projectors are $P_0 = \lvert 0 \rangle\langle 0 \rvert$ and $P_1 = \lvert 1 \rangle\langle 1 \rvert$. The measurement yields outcome $0$ with probability $\lvert\alpha\rvert^2$ and outcome $1$ with probability $\lvert\beta\rvert^2$, leaving the system in $\lvert 0 \rangle$ or $\lvert 1 \rangle$ respectively.

• • Observables are Hermitian: $\hat{M}^\dagger = \hat{M}$.
• • Born rule gives outcome probabilities from projectors.
• • Post-measurement state is the normalized projected state.

Projective measurements are not the most general kind of measurement allowed by quantum mechanics. A Positive Operator-Valued Measure (POVM) is defined by a set of positive operators $\{E_m\}$ satisfying $E_m \geq 0$ and $\sum_m E_m = I$. Unlike projective measurements, the POVM elements need not be orthogonal projectors, and the number of outcomes can exceed the dimension of the Hilbert space.

For a system in state $\rho$, the probability of obtaining outcome $m$ is $p(m) = \text{tr}(\rho E_m)$. POVMs capture any measurement that can be realized by coupling the system to an ancilla, performing a joint projective measurement, and then tracing out or ignoring the ancilla. They are strictly more general than projective measurements because the $E_m$ need not satisfy $E_m E_{m'} = \delta_{mm'} E_m$.

A classic example is unambiguous state discrimination. Suppose you are given a qubit known to be in one of two non-orthogonal states $\lvert\psi_1\rangle$ or $\lvert\psi_2\rangle$. No projective measurement can distinguish them with certainty, but a POVM can be constructed with three outcomes: 'definitely $\lvert\psi_1\rangle$', 'definitely $\lvert\psi_2\rangle$', and 'inconclusive'. The inconclusive outcome occurs with some nonzero probability, but when a definite outcome is obtained, the identification is error-free.

• • POVM elements: $E_m \geq 0$ and $\sum_m E_m = I$.
• • $p(m) = \text{tr}(\rho E_m)$ generalizes the Born rule.
• • POVMs arise from projective measurements on a larger Hilbert space.

The deferred measurement principle states that any intermediate measurements performed during a quantum circuit can always be moved to the end of the computation without changing the statistics of the final outcomes. To achieve this, any classical-controlled operations that depend on intermediate measurement results are replaced by quantum-controlled operations using ancilla qubits.

The implication is profound: quantum algorithms that use intermediate measurements and classical feedback are no more powerful than algorithms that perform only a single measurement at the very end. This simplifies the theoretical analysis of quantum complexity classes and shows that the unitary part of a quantum circuit can be assumed to be fully coherent.

Proof sketch: suppose a measurement is performed at some intermediate step and its outcome classically controls a subsequent gate. Instead of measuring, copy the qubit's state into a fresh ancilla qubit via a CNOT gate, then continue the circuit coherently. The ancilla acts as a quantum register holding the measurement outcome. At the end, measuring the ancilla yields exactly the same joint distribution over all outcomes as the original circuit. Repeating this for every intermediate measurement pushes all measurements to the final layer.

• • Intermediate measurements can be deferred to the end of any circuit.
• • Classical control is replaced by quantum control on ancilla qubits.
• • No additional computational power is gained from mid-circuit measurements.

Any classical reversible computation can be simulated efficiently by a quantum circuit. The universal gate set for reversible classical computing consists of the Toffoli gate (controlled-controlled-NOT) and the NOT gate. Since both are unitary, they can be implemented directly as quantum gates. Thus, every classical reversible circuit has an exact quantum counterpart.

What about irreversible classical circuits, such as those using AND and OR gates? Bennett's trick shows that any irreversible computation can be made reversible by adding ancilla bits to store intermediate results and then uncomputing them. The overhead is polynomial in the size of the original circuit: if the irreversible circuit has size $S$, the reversible simulation uses $O(S)$ gates and $O(S)$ ancilla bits.

This establishes that quantum circuits are at least as powerful as classical circuits: $\mathsf{P} \subseteq \mathsf{BQP}$. The Toffoli gate, together with the Hadamard gate, is also universal for quantum computation, highlighting the deep connection between classical reversible computing and quantum computing.

• • Toffoli + NOT are universal for classical reversible circuits.
• • Bennett's trick: make irreversible circuits reversible with ancillas.
• • Overhead is polynomial in circuit size.
• • Quantum circuits can efficiently simulate any classical circuit.