Chapter 7: Quantum Circuits: Building Computations from Gates — Universal Gate Sets, Circuit Diagrams, and Circuit Depth

Learning Objectives

After completing this chapter, you will be able to:

• Read and interpret quantum circuit diagrams using standard notation
• Compose single-qubit and multi-qubit gates into functional quantum circuits
• Define and compute circuit depth, width, and gate count
• Explain the concept of universal gate sets and why they matter
• Apply circuit identities to simplify and optimize quantum circuits
• Understand the relationship between circuits and unitary matrices
• Use Qiskit to build, visualize, and transpile quantum circuits
• Appreciate the role of reversible computation in the circuit model
• Derive the Solovay-Kitaev approximation and understand its implications
• Construct controlled versions of arbitrary unitaries from basic gates

7.1 The Circuit Model of Quantum Computation

The circuit model is the lingua franca of quantum computing. Just as classical logic circuits compose AND, OR, and NOT gates to perform arbitrary Boolean functions, quantum circuits compose unitary gates acting on qubits to implement arbitrary unitary transformations. The circuit model provides an intuitive visual language, a precise mathematical framework, and a direct mapping to physical implementations on real quantum hardware.

Historical Context. The circuit model for quantum computation was formalized by David Deutsch in 1989, building on Richard Feynman's 1982 observation that quantum systems are hard to simulate classically. Deutsch showed that a quantum computer could be described as a sequence of unitary operations on qubits — a direct quantum analogue of the classical circuit model. Andrew Yao later proved in 1993 that the quantum circuit model is equivalent to the quantum Turing machine, cementing its universality.

7.1.1 Why Circuits?

The circuit model is not the only way to describe quantum computation — quantum Turing machines, adiabatic evolution, measurement-based computation, and topological quantum computation are all equivalent in computational power. But circuits have several compelling advantages:

1. Visual clarity. A well-drawn circuit diagram communicates the structure of an algorithm at a glance.
2. Composability. Circuits can be built hierarchically: sub-circuits are composed into larger ones.
3. Hardware correspondence. Every gate in a circuit diagram maps to a physical operation (a laser pulse, a microwave burst, etc.).
4. Optimizability. Circuit identities allow algebraic simplification, reducing depth and gate count.
5. Verifiability. Circuits can be simulated classically (for small qubit counts) and their unitaries can be compared for equivalence.

Recurring Theme. Quantum computation is linear algebra, not magic. Every quantum circuit is just a unitary matrix — nothing more, nothing less. When a circuit seems mysterious, write down the matrices and multiply them. The mystery evaporates.

A quantum circuit consists of three essential ingredients:

1. Qubit wires — horizontal lines representing individual qubits, read left to right in time
2. Quantum gates — symbols placed on wires representing unitary operations
3. Measurements — terminal operations that project qubits onto the computational basis

The fundamental postulate is deceptively simple: any unitary operation on $n$ qubits can be approximated to arbitrary precision by a finite sequence of gates drawn from a universal gate set. This is the quantum analogue of the classical result that NAND gates are universal for Boolean logic.

7.1.2 Reading Circuit Diagrams

Consider the simplest nontrivial quantum circuit — creating and measuring a Bell state:

q_0: ── H ──●── M ──
             │
q_1: ─────── X ── M ──

Reading left to right: - Qubit $q_0$ starts in $|0\rangle$, passes through a Hadamard gate $H$, then acts as the control for a CNOT gate targeting $q_1$, and is finally measured. - Qubit $q_1$ starts in $|0\rangle$, receives the CNOT target, and is measured.

The circuit implements the transformation:

$$|00\rangle \xrightarrow{H \otimes I} \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |0\rangle \xrightarrow{\text{CNOT}} \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = |\Phi^+\rangle$$

Try it yourself: Draw the circuit that prepares the state $|\Psi^+\rangle = \frac{1}{\sqrt{2}}(|01\rangle + |10\rangle)$. Hint: Start from the Bell state circuit and add an $X$ gate on the second qubit before the CNOT.

7.1.3 Qubit Wires and Time

Each horizontal wire represents the worldline of a single qubit. Time flows from left to right. A wire is not a physical wire — it represents the identity operation on that qubit during intervals when no gate acts on it. Mathematically, a bare wire segment corresponds to the identity matrix $I$.

When a gate appears on multiple wires (like CNOT), it acts on all connected qubits simultaneously. The vertical connector in a CNOT symbol links the control (●) and target (⊕) qubits.

The convention that time flows left-to-right means that when we write the matrix expression for a circuit, the leftmost gate in the diagram is applied first — and therefore appears rightmost in the matrix product, since operators act on kets from left to right:

$$|\text{output}\rangle = U_{\text{last}} \cdots U_2 \cdot U_1 |\text{input}\rangle$$

This "reverse order" convention is a common source of confusion for beginners.

Common Misconception. "The gates in a circuit diagram are multiplied left to right." No! The leftmost gate in the diagram is applied first to the state, which means it appears on the right in the matrix product. The circuit $q_0$: ──A──B── implements $B \cdot A$ (not $A \cdot B$).

7.2 Universal Gate Sets

A set of quantum gates is universal if any unitary operation on any number of qubits can be approximated to arbitrary precision by a finite sequence of gates from the set. This is the quantum counterpart of functional completeness in classical logic.

Historical Context. The proof that a finite set of gates can approximate any unitary to arbitrary precision was a landmark result. In 1995, Barenco et al. showed that CNOT plus all single-qubit gates form a universal set. Shortly after, the Solovay-Kitaev theorem established that efficient approximation is possible. This resolved a fundamental question: can a quantum computer with a fixed, finite gate set perform arbitrary computations? The answer is yes, and the overhead is remarkably small.

7.2.1 Common Universal Gate Sets

Standard Set: $\{H, S, \text{CNOT}, T\}$ (or equivalently $\{H, S, \text{CNOT}, T^\dagger\}$)

Where: $$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \quad S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}, \quad T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}$$

Clifford + T: The most important universal gate set in fault-tolerant quantum computing. The Clifford group (generated by $\{H, S, \text{CNOT}\}$) is not universal on its own (Gottesman-Knill theorem), but adding the $T$ gate makes it universal. The $T$ gate is sometimes called the "magic" gate because it enables non-Clifford operations — the source of quantum computational advantage.

Why the Clifford group alone is not universal: The Gottesman-Knill theorem (Chapter 11) shows that any circuit composed of Clifford gates, measurements, and classical control can be efficiently simulated on a classical computer. This means Clifford circuits cannot provide exponential speedup. The $T$ gate breaks out of the Clifford framework, enabling universal quantum computation.

Common Misconception. "If I can implement $H$, $S$, and CNOT, I have a universal quantum computer." Not quite. These are all Clifford gates. Without the $T$ gate (or another non-Clifford gate), your circuit can be classically simulated in polynomial time. The $T$ gate is essential for quantum advantage.

Native Gate Sets: Real quantum processors have hardware-specific native gates. For example, IBM's superconducting qubits typically use:

$$\{R_z(\theta), \sqrt{X}, \text{CNOT}\}$$

The $R_z(\theta)$ gate implements an arbitrary rotation about the Z-axis:

$$R_z(\theta) = e^{-i\theta Z/2} = \begin{pmatrix} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{pmatrix}$$

The $\sqrt{X}$ gate (also called the $\sqrt{\text{NOT}}$ or $SX$ gate) is:

$$\sqrt{X} = \frac{1}{2}\begin{pmatrix} 1+i & 1-i \\ 1-i & 1+i \end{pmatrix} = e^{i\pi/4} R_x(\pi/2)$$

Recurring Theme. The gap between abstract gates and native gates is real and consequential. Every "logical" $H$ gate might decompose into multiple native rotations on hardware. Every "logical" CNOT might require SWAPs to satisfy connectivity constraints. Noise is the enemy, and transpilation is how we fight back — but transpilation adds depth, which adds error.

7.2.2 The Solovay-Kitaev Theorem

The Solovay-Kitaev theorem guarantees that any universal gate set can efficiently approximate any unitary. Specifically, to approximate an $n$-qubit unitary to precision $\epsilon$ requires $O(\log^c(1/\epsilon))$ gates, where $c \approx 3.97$.

Full Statement of the Theorem:

Let $\mathcal{G}$ be a universal gate set that is closed under inverses and generates a dense subgroup of $SU(2)$. Then there exists a constant $c$ such that for any target unitary $U \in SU(2)$ and any $\epsilon > 0$, there exists a sequence $g_1 g_2 \cdots g_L$ of gates from $\mathcal{G}$ satisfying:

$$\|U - g_1 g_2 \cdots g_L\| \leq \epsilon$$

where $L = O(\log^c(1/\epsilon))$.

Why this matters: Without Solovay-Kitaev, we would need exponentially many gates to approximate a unitary, making quantum computation impractical. The theorem tells us that the overhead of working with a finite gate set is only polylogarithmic — a very small price to pay.

The Solovay-Kitaev Algorithm (Sketch):

The algorithm works by iterative decomposition:

1. Base case: For each gate $U$ in the target set, precompute a good approximation using a sequence of gates from $\mathcal{G}$ to some initial precision $\epsilon_0$.

2. Recursive step: Given a target unitary $U$ and desired precision $\epsilon$: - Find an $\epsilon^{1/2}$-approximation $V$ of $U$ (recursively) - The error in $V$ is at most $\epsilon^{1/2}$ - Decompose the correction $UV^\dagger$ as a product of group commutators - Each commutator can be approximated to precision $\epsilon$ using shorter sequences - Combine to get an $\epsilon$-approximation of $U$

3. Result: Each level of recursion roughly squares the precision while adding a constant factor of gates, yielding the $O(\log^c(1/\epsilon))$ scaling.

Practical implications: For the Clifford + T gate set, the $T$-count (number of $T$ gates) required to approximate an arbitrary single-qubit unitary to precision $\epsilon$ is approximately:

$$T\text{-count} \approx 3.53 \log_2(1/\epsilon) + O(\log \log(1/\epsilon))$$

This means a precision of $\epsilon = 10^{-10}$ requires only about 117 $T$ gates. Modern synthesis algorithms achieve even better constants.

7.2.3 Building Arbitrary Single-Qubit Gates

Any single-qubit unitary $U \in SU(2)$ can be decomposed using Euler angles. The Z-Y-Z decomposition (also called the $U_3$ decomposition) states:

$$U = e^{i\alpha} R_z(\beta) R_y(\gamma) R_z(\delta)$$

where $\alpha, \beta, \gamma, \delta \in \mathbb{R}$ and $R_y$ and $R_z$ are rotation matrices:

$$R_y(\theta) = \begin{pmatrix} \cos(\theta/2) & -\sin(\theta/2) \\ \sin(\theta/2) & \cos(\theta/2) \end{pmatrix}, \quad R_z(\theta) = \begin{pmatrix} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{pmatrix}$$

Derivation of the Z-Y-Z decomposition:

Any $2 \times 2$ unitary has the form:

$$U = \begin{pmatrix} u_{00} & u_{01} \\ u_{10} & u_{11} \end{pmatrix}$$

where $|u_{00}|^2 + |u_{10}|^2 = 1$ and $u_{00}u_{01}^* + u_{10}u_{11}^* = 0$.

We can always write $U = e^{i\alpha} \tilde{U}$ where $\det(\tilde{U}) = 1$, placing $\tilde{U} \in SU(2)$.

Since $R_y(\theta)$ and $R_z(\theta)$ are both in $SU(2)$ (up to global phase), and $SU(2)$ is a Lie group with Lie algebra spanned by $\{i\sigma_x, i\sigma_y, i\sigma_z\}$, the product $R_z(\beta) R_y(\gamma) R_z(\delta)$ can reach any element of $SU(2)$ by appropriate choice of angles.

Explicit parameter extraction: Given $U = \begin{pmatrix} a & b \\ -b^* & a^* \end{pmatrix}$ with $|a|^2 + |b|^2 = 1$, we can extract:

$$\gamma = 2 \arccos(|a|), \quad \beta + \delta = 2 \arg(a), \quad \beta - \delta = 2 \arg(b) + \pi$$

Or using the Z-X-Z decomposition:

$$U = e^{i\alpha} R_z(\beta) R_x(\gamma) R_z(\delta)$$

In Qiskit, this is automated:

from qiskit import QuantumCircuit
from qiskit.circuit.library import UGate
import numpy as np

theta, phi, lam = np.pi/3, np.pi/4, np.pi/2
qc = QuantumCircuit(1)
qc.u(theta, phi, lam, 0)
print(qc.draw('text'))

# Verify: compute the unitary
from qiskit.quantum_info import Operator
U_computed = Operator(qc).data
print("\nComputed unitary:")
print(np.round(U_computed, 4))

# Expected from the formula
print("\nExpected from U(θ,φ,λ) formula:")
expected = np.array([
    [np.cos(theta/2), -np.exp(1j*lam)*np.sin(theta/2)],
    [np.exp(1j*phi)*np.sin(theta/2), np.exp(1j*(phi+lam))*np.cos(theta/2)]
])
print(np.round(expected, 4))

The $U_3$ gate (now called $U$ in Qiskit) is:

$$U(\theta, \phi, \lambda) = \begin{pmatrix} \cos(\theta/2) & -e^{i\lambda}\sin(\theta/2) \\ e^{i\phi}\sin(\theta/2) & e^{i(\phi+\lambda)}\cos(\theta/2) \end{pmatrix}$$

Worked Example 7.1: Decomposing $H$ into native gates

The Hadamard gate can be decomposed into $R_z$ and $\sqrt{X}$:

$$H = R_z(\pi/2) \cdot \sqrt{X} \cdot R_z(\pi/2)$$

Let's verify this:

$$R_z(\pi/2) = \begin{pmatrix} e^{-i\pi/4} & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}$$

$$\sqrt{X} = \frac{1}{2}\begin{pmatrix} 1+i & 1-i \\ 1-i & 1+i \end{pmatrix}$$

Multiplying $R_z(\pi/2) \cdot \sqrt{X} \cdot R_z(\pi/2)$ and simplifying, we get $\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = H$. ✓

Worked Example 7.2: Approximating the $T$ gate with Clifford gates is impossible

The $T$ gate $T = \text{diag}(1, e^{i\pi/4})$ is not a Clifford gate. We can prove this by contradiction: if $T$ were Clifford, then for any Pauli $P$, we would need $TPT^\dagger$ to be a Pauli. But:

$$TXT^\dagger = T \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} T^\dagger = \begin{pmatrix} 0 & e^{-i\pi/4} \\ e^{i\pi/4} & 0 \end{pmatrix} = \frac{1}{\sqrt{2}}(X + Y)$$

This is not a Pauli matrix, so $T$ is not Clifford. This is why $T$ (or any non-Clifford gate) is needed to make the gate set universal.

7.3 Circuit Depth and Width

Two critical metrics characterize any quantum circuit:

Circuit Width ($w$): The number of qubits. Determines the size of the Hilbert space ($2^w$) and the memory requirements for classical simulation.

Circuit Depth ($d$): The length of the longest path from input to output, measured in layers of gates that can be executed simultaneously. Gates acting on disjoint qubits can be parallelized into the same layer.

Gate Count ($g$): The total number of quantum gates. Related to depth by $d \leq g \leq w \cdot d$.

7.3.1 Computing Depth

Consider this circuit:

q_0: ── H ──●──────────●── M ──
             │          │
q_1: ── H ── X ──●──── X ── M ──
                 │
q_2: ── H ───── X ───────── M ──

Layer decomposition: - Layer 1: $H$ on all three qubits (parallel) - Layer 2: CNOT (0→1) and CNOT (2→1) — wait, these share qubit 1, so they must be sequential - Layer 2: CNOT (0→1) - Layer 3: CNOT (2→1) - Layer 4: CNOT (0→1) again

Depth = 4, Width = 3, Gate count = 6.

Worked Example 7.3: Depth of a GHZ circuit

For an $n$-qubit GHZ state created with the "chain" pattern:

q_0: ── H ──●────────────
             │
q_1: ─────── X ──●────────
                  │
q_2: ─────────── X ──●────
                       │
q_3: ──────────────── X ──

The depth is $n$ (one Hadamard plus $n-1$ sequential CNOTs). But we can reduce this! A "binary tree" approach uses parallel CNOTs:

q_0: ── H ──●─────────────
             │
q_1: ─────── X ──●────────
                  │
q_2: ────●── X ── X ──●──
          │            │
q_3: ──── X ────────── X ──

Wait, that's not quite right for GHZ. The binary tree approach works for creating the state but requires careful ordering. The depth for $n$ qubits using a binary fan-out is $O(\log n)$ instead of $O(n)$.

from qiskit import QuantumCircuit

def ghz_linear(n):
    """GHZ with linear depth O(n)."""
    qc = QuantumCircuit(n)
    qc.h(0)
    for i in range(n - 1):
        qc.cx(i, i + 1)
    return qc

def ghz_log_depth(n):
    """GHZ with logarithmic depth O(log n)."""
    qc = QuantumCircuit(n)
    qc.h(0)
    step = 1
    while step < n:
        for i in range(0, n - step, 2 * step):
            if i + step < n:
                qc.cx(i, i + step)
        step *= 2
    return qc

for n in [4, 8, 16]:
    qc_lin = ghz_linear(n)
    qc_log = ghz_log_depth(n)
    print(f"n={n}: Linear depth={qc_lin.depth()}, Log depth={qc_log.depth()}")

7.3.2 Why Depth Matters

Depth directly impacts fidelity. Each gate introduces error, and qubits decohere over time. The probability of success decays roughly as:

$$P_{\text{success}} \approx e^{-d \cdot \epsilon_{\text{gate}} - T_{\text{circuit}} / T_2}$$

where $\epsilon_{\text{gate}}$ is the average gate error, $T_{\text{circuit}}$ is the total circuit duration, and $T_2$ is the coherence time.

Numerical example: On a device with single-qubit gate error $0.1\%$, two-qubit gate error $1\%$, and $T_2 = 100\ \mu s$: - A circuit with 5 single-qubit gates and 3 two-qubit gates and depth 8: - Gate error probability: $5 \times 0.001 + 3 \times 0.01 = 0.035$, so $P_{\text{gate}} \approx 0.966$ - If each layer takes $0.1\ \mu s$, total time $= 0.8\ \mu s$, so $P_{\text{decoherence}} \approx e^{-0.8/100} \approx 0.992$ - Overall: $\approx 0.958$

• A circuit with depth 80 (10× deeper):
• Gate error probability: $\approx 0.35$, so $P_{\text{gate}} \approx 0.70$
• Total time $= 8\ \mu s$, so $P_{\text{decoherence}} \approx e^{-8/100} \approx 0.923$
• Overall: $\approx 0.646$

Depth matters enormously.

Recurring Theme. Noise is the enemy. Every layer of depth adds more error and more decoherence. The entire field of quantum algorithm design can be seen as a quest to minimize circuit depth while maximizing computational advantage.

Try it yourself: Estimate the maximum circuit depth that can be executed with fidelity > 50% on a hypothetical device with gate error rate 0.5% per layer and $T_2 = 200\ \mu s$, assuming each layer takes $0.05\ \mu s$. Answer: Approximately 100 layers, since $0.995^{100} \times e^{-5/200} \approx 0.61$. At depth 140, fidelity drops below 50%.

7.4 Composing Gates into Circuits

7.4.1 The Tensor Product Structure

When gates act on different qubits, their combined action is the tensor product:

q_0: ── H ────
q_1: ── X ────

This circuit implements $H \otimes X$, a $4 \times 4$ matrix:

$$H \otimes X = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \otimes \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & -1 & 0 \end{pmatrix}$$

Full derivation of the tensor product: For $A = \begin{pmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{pmatrix}$ and $B = \begin{pmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \end{pmatrix}$:

$$A \otimes B = \begin{pmatrix} a_{00}B & a_{01}B \\ a_{10}B & a_{11}B \end{pmatrix} = \begin{pmatrix} a_{00}b_{00} & a_{00}b_{01} & a_{01}b_{00} & a_{01}b_{01} \\ a_{00}b_{10} & a_{00}b_{11} & a_{01}b_{10} & a_{01}b_{11} \\ a_{10}b_{00} & a_{10}b_{01} & a_{11}b_{00} & a_{11}b_{01} \\ a_{10}b_{10} & a_{10}b_{11} & a_{11}b_{10} & a_{11}b_{11} \end{pmatrix}$$

Worked Example 7.4: Computing $H \otimes X |01\rangle$

$$H \otimes X |01\rangle = (H \otimes X)(|0\rangle \otimes |1\rangle) = H|0\rangle \otimes X|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |0\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)$$

This makes sense: $H$ creates a superposition on qubit 0, and $X$ flips qubit 1 from $|1\rangle$ to $|0\rangle$.

7.4.2 Sequential Composition

When gates act on the same qubit sequentially, their matrices multiply (right to left!):

q_0: ── H ── X ──

This implements $X \cdot H$ (note: $H$ first, then $X$):

$$XH = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \cdot \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}$$

Verification with Qiskit:

from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
import numpy as np

qc = QuantumCircuit(1)
qc.h(0)
qc.x(0)
U = Operator(qc)
print("XH =")
print(np.round(U.data, 4))

# Verify by direct computation
H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)
X = np.array([[0, 1], [1, 0]])
print("\nDirect computation:")
print(np.round(X @ H, 4))

7.4.3 Mixed Composition: Parallel and Sequential

Most real circuits involve both parallel and sequential composition. Consider:

q_0: ── H ──●──
             │
q_1: ── X ──⊕──

The total unitary is:

$$U_{\text{total}} = \text{CNOT} \cdot (H \otimes X)$$

where the CNOT (with qubit 0 as control, qubit 1 as target) is:

$$\text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

Step by step: Start with $|00\rangle$:

$$|00\rangle \xrightarrow{H \otimes X} (H|0\rangle) \otimes (X|0\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |1\rangle = \frac{1}{\sqrt{2}}(|01\rangle + |11\rangle)$$

$$\xrightarrow{\text{CNOT}} \frac{1}{\sqrt{2}}(\text{CNOT}|01\rangle + \text{CNOT}|11\rangle)$$

Now, $\text{CNOT}|01\rangle = |01\rangle$ (control is $|0\rangle$, no flip) and $\text{CNOT}|11\rangle = |10\rangle$ (control is $|1\rangle$, flip target).

Result: $\frac{1}{\sqrt{2}}(|01\rangle + |10\rangle) = |\Psi^+\rangle$

This is one of the four Bell states!

7.4.4 Building a GHZ State Circuit

The Greenberger-Horne-Zeilinger (GHZ) state is a generalization of the Bell state to $n$ qubits:

$$|\text{GHZ}_n\rangle = \frac{1}{\sqrt{2}}(|0\rangle^{\otimes n} + |1\rangle^{\otimes n})$$

q_0: ── H ──●──────────●──
             │          │
q_1: ─────── X ──●──────┼──
                  │      │
q_2: ─────────── X ──●──┼──
                       │  │
q_3: ─────────────── X ── X ──

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

def create_ghz_state(n_qubits: int) -> QuantumCircuit:
    qc = QuantumCircuit(n_qubits)
    qc.h(0)
    for i in range(n_qubits - 1):
        qc.cx(i, i + 1)
    return qc

qc_ghz = create_ghz_state(4)
print(qc_ghz.draw('text'))

state = Statevector.from_instruction(qc_ghz)
print(f"\nStatevector:\n{state.data}")
print(f"\nState probabilities: {state.probabilities_dict()}")

Mathematical verification for 3-qubit GHZ:

Starting from $|000\rangle$:

$$|000\rangle \xrightarrow{H \otimes I \otimes I} \frac{1}{\sqrt{2}}(|000\rangle + |100\rangle)$$

$$\xrightarrow{\text{CNOT}_{0,1}} \frac{1}{\sqrt{2}}(|000\rangle + |110\rangle)$$

$$\xrightarrow{\text{CNOT}_{1,2}} \frac{1}{\sqrt{2}}(|000\rangle + |111\rangle) = |\text{GHZ}_3\rangle \checkmark$$

7.5 Reversible Computation

Quantum mechanics is unitary, and unitary operations are invertible. Every quantum gate must therefore be reversible — information cannot be destroyed. This has profound implications for how we design quantum algorithms.

7.5.1 The Landauer Principle

Landauer showed in 1961 that erasing one bit of information dissipates at least $k_B T \ln 2$ of energy as heat, where $k_B$ is Boltzmann's constant and $T$ is temperature. This is a fundamental thermodynamic limit — it applies regardless of the technology.

At room temperature (300 K), this is approximately $2.9 \times 10^{-21}$ joules per bit — tiny, but fundamental. Quantum computation, being reversible at the gate level (until measurement), can in principle approach zero energy dissipation per computational step.

Implication: Classical irreversible gates like AND ($2$ inputs $\to$ $1$ output) necessarily erase information and dissipate energy. Quantum computation must avoid such irreversible operations. This is why we embed classical functions into reversible oracles.

7.5.2 Making Classical Functions Reversible

Consider a classical function $f: \{0,1\}^n \to \{0,1\}^m$. To implement it on a quantum computer, we must construct a unitary $U_f$ such that:

$$U_f |x\rangle |y\rangle = |x\rangle |y \oplus f(x)\rangle$$

This is the standard oracle construction. The input $|x\rangle$ is preserved, and the output is XORed into an ancilla register.

Why XOR? The XOR operation $y \oplus f(x)$ is its own inverse: applying $U_f$ twice gives $(y \oplus f(x)) \oplus f(x) = y$, so $U_f$ is its own inverse, confirming reversibility.

Why not $|x\rangle |y\rangle \to |x\rangle |f(x)\rangle$? This would not be reversible when $f$ is not injective. For example, if $f(x) = 0$ for all $x$, then $U|x\rangle|0\rangle = |x\rangle|0\rangle$ and $U|x\rangle|1\rangle = |x\rangle|0\rangle$ for different inputs produce the same output, violating unitarity.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
import numpy as np

def build_reversible_xor():
    """Build U_f for f(x) = x (the identity function on 1 bit).
    This is just a CNOT gate: |x⟩|y⟩ → |x⟩|y ⊕ x⟩."""
    qc = QuantumCircuit(2)
    qc.cx(0, 1)
    return qc

qc_xor = build_reversible_xor()
U = Operator(qc_xor)
print("Unitary for reversible XOR (CNOT):")
print(np.round(U.data, 2))
print(f"\nIs unitary? {np.allclose(U.data @ U.data.conj().T, np.eye(4))}")
print(f"Is self-inverse? {np.allclose(U.data, np.eye(4))}")

7.5.3 The Toffoli Gate: Universal Classical Reversible Gate

The Toffoli gate (CCNOT) is universal for classical reversible computation:

a: ──●──
     │
b: ──●──
     │
c: ──⊕──

$$\text{CCNOT} |a, b, c\rangle = |a, b, c \oplus (a \land b)\rangle$$

Any classical Boolean circuit can be converted to a reversible one using Toffoli gates, at the cost of additional ancilla qubits to hold intermediate results.

Proof sketch that Toffoli is universal for reversible classical computation:

1. NOT: $\text{CCNOT}|1, 1, c\rangle = |1, 1, c \oplus 1\rangle$ (flip $c$ when $a=b=1$)
2. AND: $\text{CCNOT}|a, b, 0\rangle = |a, b, a \land b\rangle$
3. NAND: $\text{CCNOT}|a, b, 1\rangle = |a, b, \neg(a \land b)\rangle$ (since $1 \oplus (a \land b) = \neg(a \land b)$)
4. FANOUT: $\text{CCNOT}|x, 1, 0\rangle = |x, 1, x\rangle$ (copy $x$ when $b=1$)

Since NAND is universal for classical computation, and Toffoli can implement NAND, Toffoli is universal.

Ancilla cost: Converting an irreversible circuit with $g$ gates and $k$ outputs to a reversible one requires $O(g)$ ancilla qubits. This is the "garbage" problem — intermediate results must be kept around until the computation is complete, then "uncomputed" by running the circuit backwards.

7.6 Circuit Identities and Optimizations

Circuit identities are equivalences between different gate sequences that produce the same unitary. They are the bread and butter of circuit optimization.

7.6.1 Common Single-Qubit Identities

Pauli identities: $$H^2 = I, \quad X^2 = Y^2 = Z^2 = I$$

Hadamard conjugation (Hadamard swaps Pauli axes): $$HXH = Z, \quad HYH = -Y, \quad HZH = X$$

Proof of $HXH = Z$: $$HXH = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix} = \frac{1}{2}\begin{pmatrix} 2 & 0 \\ 0 & -2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = Z \quad \checkmark$$

Phase gate identities: $$S^2 = Z, \quad T^2 = S, \quad T^4 = Z$$

Proof of $T^2 = S$: $$T^2 = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}^2 = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/2} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} = S \quad \checkmark$$

Conjugation by S: $$SXS^\dagger = Y, \quad SYS^\dagger = -X$$

Proof of $SXS^\dagger = Y$: $$SXS^\dagger = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & -i \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \begin{pmatrix} 0 & -i \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix} = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$$

Since $Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$, we have $SXS^\dagger = Y$. ✓

Common Misconception. "If two circuits produce the same unitary, they have the same depth." No! Equivalent unitaries can have vastly different depths. The entire field of circuit optimization is about finding shorter implementations of the same unitary.

7.6.2 CNOT Identities

──●── = ──●──      (control and target are symmetric for Z-basis control)
──X──   ──X──

──●── H ──●── H    (Hadamard conjugates swap control and target of CNOT)
──X──   ──X──

──●──●── = ──────   (two identical CNOTs cancel)
──X──X──   ──────

The Hadamard swap identity is particularly important for transpilation. It states that a CNOT with control on qubit $a$ and target on qubit $b$ is equivalent to a CNOT with control on qubit $b$ and target on qubit $a$, provided both qubits are conjugated with Hadamards:

$$(H \otimes H) \cdot \text{CNOT}_{a \to b} \cdot (H \otimes H) = \text{CNOT}_{b \to a}$$

Proof: $$(H \otimes H) \text{CNOT}_{a \to b} (H \otimes H) = (H \otimes H) \begin{pmatrix} 1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0 \end{pmatrix} (H \otimes H)$$

Since $H \otimes H$ permutes the computational basis as $|00\rangle \leftrightarrow |++\rangle$, etc., the matrix transformation swaps the control and target. This identity is used extensively in transpilation to route CNOTs through limited connectivity.

7.6.3 Commutation Rules

Gates acting on different qubits always commute. Gates acting on the same qubit commute if they are both diagonal in the same basis:

$$[Z \otimes I, I \otimes X] = 0 \quad \text{(different qubits)}$$ $$[R_z(\theta), R_z(\phi)] = 0 \quad \text{(same basis, same qubit)}$$

But in general, $[A, B] \neq 0$ when $A$ and $B$ act on the same qubit and don't share eigenbases.

The Baker-Campbell-Hausdorff (BCH) formula quantifies the non-commutativity:

$$e^A e^B = e^{A + B + \frac{1}{2}[A,B] + \frac{1}{12}([A,[A,B]] - [B,[A,B]]) + \cdots}$$

When $[A, B] = 0$, this reduces to $e^A e^B = e^{A+B}$ — the familiar exponential rule.

Worked Example 7.5: Using commutation rules

The circuit:

q_0: ── Z ──●──
             │
q_1: ─────── X ──

Can we commute the $Z$ gate past the CNOT? Since $Z$ acts on the control qubit, and CNOT is controlled-$X$, we use the identity:

If a single-qubit gate $U$ acts on the control qubit, it commutes with the CNOT control operation. More precisely, $Z \otimes I$ commutes with $\text{CNOT}$ when the $Z$ is on the control wire, because $\text{CNOT} = |0\rangle\langle 0| \otimes I + |1\rangle\langle 1| \otimes X$ and $Z = |0\rangle\langle 0| - |1\rangle\langle 1|$, and these share the eigenbasis $\{|0\rangle, |1\rangle\}$.

So the $Z$ commutes through the CNOT control:

q_0: ── Z ──●──  =  ──●── Z ──
             │              │
q_1: ─────── X ──  ─────── X ──

7.6.4 Circuit Optimization Example

Consider this redundant circuit:

q_0: ── H ── X ── H ──●── H ── X ── H ──
                        │
q_1: ───────────────── X ────────────────

Step 1: Using $HXH = Z$, the circuit simplifies to:

q_0: ── Z ──●── Z ──
             │
q_1: ─────── X ──────

Step 2: Since $Z$ commutes with the control of CNOT (as shown above), both $Z$ gates can be moved to the same side:

q_0: ──●── Z ── Z ──  =  ──●── Z² ──  =  ──●──
        │                    │              │
q_1: ── X ────────────  ─── X ─────────  ── X ──

Step 3: Since $Z^2 = I$, the two $Z$ gates cancel, and we're left with just a single CNOT!

q_0: ──●──
        │
q_1: ── X ──

The original circuit had 6 gates and depth 6. The optimized circuit has 1 gate and depth 1. This is a dramatic improvement.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import Optimize1qGatesDecomposition
import numpy as np

# Build the redundant circuit
qc = QuantumCircuit(2)
qc.h(0)
qc.x(0)
qc.h(0)
qc.cx(0, 1)
qc.h(0)
qc.x(0)
qc.h(0)

print("Original circuit:")
print(qc.draw('text'))
print(f"Depth: {qc.depth()}, Gate count: {qc.size()}")

# Verify it equals a single CNOT
U_original = Operator(qc)
qc_simple = QuantumCircuit(2)
qc_simple.cx(0, 1)
U_simple = Operator(qc_simple)
print(f"\nEquivalent to CNOT? {np.allclose(U_original.data, U_simple.data, atol=1e-10)}")

# Optimize with Qiskit
pm = PassManager([Optimize1qGatesDecomposition()])
qc_opt = pm.run(qc)
print(f"\nOptimized circuit:")
print(qc_opt.draw('text'))
print(f"Depth: {qc_opt.depth()}, Gate count: {qc_opt.size()}")

7.6.5 The Gate Cancellation Pass

A systematic approach to optimization is the gate cancellation pass: scan the circuit for adjacent gates that multiply to identity or simplify to a single gate.

Rules for gate cancellation: 1. $G \cdot G^\dagger = I$ (any gate followed by its inverse cancels) 2. $G \cdot G = I$ for self-inverse gates ($X, Y, Z, H, \text{CNOT}$) 3. $T \cdot T = S$, $S \cdot S = Z$ (phase accumulation) 4. Rotations add: $R_z(\theta) \cdot R_z(\phi) = R_z(\theta + \phi)$

Common Misconception. "More optimization is always better." No! Aggressive optimization can change the structure of a circuit in ways that make it harder to debug, harder to verify, and sometimes even longer after transpilation to native gates. Always compare the before and after.

7.7 The Relationship Between Circuits and Unitary Matrices

Every quantum circuit corresponds to a unitary matrix. The mapping is:

1. Tensor product for gates in parallel (same time slice, different qubits)
2. Matrix multiplication for gates in series (same qubit, different time slices)
3. Right-to-left ordering: the leftmost gate in the diagram is applied first to the state vector

7.7.1 Computing the Unitary of a Circuit

For a circuit with $n$ qubits and $m$ time steps, the total unitary is:

$$U_{\text{circuit}} = U_m \cdot U_{m-1} \cdot \ldots \cdot U_1$$

where each $U_j$ is the tensor product of all gates acting at time step $j$, padded with identities on idle qubits.

Worked Example 7.6: Computing the Bell state circuit unitary

The Bell state circuit is:

q_0: ── H ──●──
             │
q_1: ─────── X ──

Step 1: The first time slice has $H$ on qubit 0 and identity on qubit 1:

$$U_1 = H \otimes I = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{pmatrix}$$

Step 2: The second time slice has CNOT:

$$U_2 = \text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

Step 3: Total unitary:

$$U = U_2 \cdot U_1 = \text{CNOT} \cdot (H \otimes I)$$

Computing this product gives the matrix that maps $|00\rangle \to |\Phi^+\rangle$, $|01\rangle \to |\Psi^+\rangle$, etc.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
import numpy as np

qc = QuantumCircuit(2)
qc.h(0)
qc.cx(0, 1)

U = Operator(qc)
print("Circuit unitary (4×4 matrix):")
print(np.round(U.data, 3))

# Verify each basis state transformation
from qiskit.quantum_info import Statevector
for i in range(4):
    basis = Statevector.from_int(i, 2)
    result = basis.evolve(qc)
    print(f"|{i:02b}⟩ → {np.round(result.data, 3)}")

7.7.2 Verifying Circuit Equivalence

Two circuits are equivalent if their unitaries are equal (up to global phase):

def circuits_equivalent(qc1, qc2, eps=1e-10):
    U1 = Operator(qc1).data
    U2 = Operator(qc2).data
    # Check equality up to global phase
    phase = U1[0, 0] / U2[0, 0] if abs(U2[0, 0]) > eps else 1.0
    return np.allclose(U1, phase * U2, atol=eps)

qc1 = QuantumCircuit(1)
qc1.h(0)
qc1.z(0)
qc1.h(0)

qc2 = QuantumCircuit(1)
qc2.x(0)

print(f"HZH = X: {circuits_equivalent(qc1, qc2)}")

Try it yourself: Verify that $HZH = X$ by direct matrix multiplication. Compute $H$, then $ZH$, then $HZH$, and confirm it equals $X$.

7.7.3 The Gate Count-Depth Trade-off

There is often a trade-off between gate count and circuit depth. Consider a circuit that applies $H$ to all $n$ qubits:

• Serial implementation: Apply $H$ one qubit at a time. Gate count = $n$, depth = $n$.
• Parallel implementation: Apply $H$ to all qubits simultaneously. Gate count = $n$, depth = 1.

Both implementations have the same gate count, but the parallel one is $n$ times shorter. This illustrates why parallelism is crucial for quantum computing: we want to minimize depth to stay within coherence time.

7.8 Transpilation

Transpilation is the process of converting a logical quantum circuit into an equivalent circuit that respects the constraints of a specific quantum processor. This involves:

1. Gate decomposition — expressing arbitrary gates in terms of the native gate set
2. Qubit mapping — assigning logical qubits to physical qubits respecting connectivity
3. SWAP insertion — adding SWAP gates when two-qubit gates require non-adjacent qubits
4. Optimization — reducing depth and gate count

7.8.1 The Transpilation Pipeline

from qiskit import QuantumCircuit, transpile
from qiskit.providers.fake_provider import FakeBrisbane
import numpy as np

# Create a circuit with non-native gates
qc = QuantumCircuit(3)
qc.h(0)
qc.cx(0, 1)
qc.cx(1, 2)
qc.u(np.pi/3, np.pi/4, np.pi/2, 0)
qc.cx(2, 0)  # Requires SWAP if 0 and 2 aren't connected
qc.measure_all()

print("Original circuit:")
print(qc.draw('text'))
print(f"Depth: {qc.depth()}, Gates: {qc.size()}")

# Transpile for a specific backend
backend = FakeBrisbane()
qc_transpiled = transpile(qc, backend, optimization_level=3)

print("\nTranspiled circuit:")
print(qc_transpiled.draw('text', fold=100))
print(f"Depth: {qc_transpiled.depth()}, Gates: {qc_transpiled.size()}")

7.8.2 Understanding the Transpiled Output

After transpilation, you'll notice: - $H$ gates decomposed into $R_z$ and $\sqrt{X}$ sequences - $U_3$ gates decomposed into native rotations - Additional CNOT gates (from SWAP insertions) to satisfy connectivity - Possibly increased depth due to routing overhead

Worked Example 7.7: Gate decomposition

The Hadamard gate on IBM hardware decomposes as:

$$H = R_z(\pi/2) \cdot \sqrt{X} \cdot R_z(\pi/2)$$

This means one "logical" $H$ becomes three "physical" gates. A Bell state circuit with 2 logical gates ($H$ + CNOT) becomes 4 physical gates ($R_z + \sqrt{X} + R_z + \text{CNOT}$).

The SWAP overhead: If qubits 0 and 2 are not directly connected, a CNOT between them requires:

$$\text{CNOT}_{0,2} \to \text{SWAP}_{0,1} \cdot \text{CNOT}_{1,2} \cdot \text{SWAP}_{0,1}$$

Each SWAP is 3 CNOTs, so this one logical CNOT becomes $3 + 1 + 3 = 7$ physical CNOTs!

from qiskit import QuantumCircuit, transpile
from qiskit.providers.fake_provider import FakeBrisbane

backend = FakeBrisbane()

# Simple 3-qubit circuit
qc = QuantumCircuit(3)
qc.h(0)
qc.cx(0, 2)  # Long-range CNOT
qc.measure_all()

qc_t = transpile(qc, backend, optimization_level=3)
print(f"Original: depth={qc.depth()}, gates={qc.size()}")
print(f"Transpiled: depth={qc_t.depth()}, gates={qc_t.size()}")

7.8.3 Optimization Levels

Qiskit provides four optimization levels (0-3):

for level in range(4):
    qc_t = transpile(qc, backend, optimization_level=level)
    print(f"Level {level}: depth={qc_t.depth()}, gates={qc_t.size()}")

Recurring Theme. We're at the beginning. Today's transpilers add significant overhead. As hardware improves (better connectivity, more native gates), transpilation overhead will shrink. But for now, always transpile with optimization_level=3 for production runs.

7.9 Building Complex Circuits: A Complete Example

Let's build a 4-qubit Quantum Fourier Transform (QFT) circuit, a fundamental subroutine in many quantum algorithms:

7.9.1 The QFT Circuit

The QFT maps a computational basis state $|j\rangle$ to:

$$|j\rangle \xrightarrow{\text{QFT}} \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i jk / 2^n} |k\rangle$$

The circuit consists of Hadamard gates followed by controlled rotations with exponentially decreasing angles:

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
from qiskit.quantum_info import Operator
import numpy as np

def build_qft_manual(n_qubits: int) -> QuantumCircuit:
    """Build QFT circuit manually to illustrate structure."""
    qc = QuantumCircuit(n_qubits)

    for j in range(n_qubits):
        qc.h(j)
        for k in range(j + 1, n_qubits):
            angle = 2 * np.pi / 2**(k - j + 1)
            qc.cp(angle, k, j)

    # Swap qubits to reverse order
    for j in range(n_qubits // 2):
        qc.swap(j, n_qubits - j - 1)

    return qc

qc_qft = build_qft_manual(4)
print("4-qubit QFT circuit:")
print(qc_qft.draw('text'))

# Compare with Qiskit's built-in QFT
qc_qft_builtin = QFT(num_qubits=4, do_swaps=True)
print("\nBuilt-in QFT (decomposed):")
print(qc_qft_builtin.decompose().draw('text'))

# Verify equivalence
U_manual = Operator(qc_qft)
U_builtin = Operator(qc_qft_builtin.decompose())
print(f"\nEquivalent (up to global phase)? {np.allclose(U_manual.data, U_builtin.data, atol=1e-8) or np.allclose(U_manual.data, -U_builtin.data, atol=1e-8)}")

Mathematical structure of the QFT: The QFT circuit on $n$ qubits has: - $n$ Hadamard gates - $\binom{n}{2}$ controlled phase gates - $\lfloor n/2 \rfloor$ SWAP gates - Total depth: $O(n^2)$ - Gate count: $O(n^2)$

7.9.2 QFT State Evolution Example

Let's trace the QFT on 3 qubits applied to $|5\rangle = |101\rangle$:

Step 0: |101⟩  (j = 5)

Step 1: H on q0 → (1/√2)(|101⟩ + e^{2πi·5/2}|001⟩) = (1/√2)(|101⟩ - |001⟩)
              = (1/√2)(|1⟩ - |0⟩) ⊗ |01⟩ on remaining qubits

Step 2: CR(π/2) from q1 to q0, CR(π/4) from q2 to q0
        ...

Step 3: H on q1, controlled phases on q1

Step 4: H on q2

Step 5: SWAP qubits 0 and 2

The final state should be $\frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2\pi i \cdot 5k/8} |k\rangle$.

Try it yourself: Compute the QFT of $|3\rangle$ on 3 qubits by hand. Hint: $|3\rangle = |011\rangle$, and $\text{QFT}|3\rangle = \frac{1}{\sqrt{8}} \sum_k e^{2\pi i \cdot 3k/8} |k\rangle$. Simplify the phases using $e^{2\pi i k/8} = \omega^k$ where $\omega = e^{2\pi i/8}$.

7.10 Circuit Families and Design Patterns

7.10.1 The Walsh-Hadamard Transform

Applying $H$ to all $n$ qubits creates an equal superposition over all $2^n$ basis states:

q_0: ── H ──
q_1: ── H ──
q_2: ── H ──

$$H^{\otimes n} |0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle$$

This is the starting point for virtually all quantum algorithms. The key property is that $H^{\otimes n}$ transforms between the computational basis and the Hadamard (Fourier) basis:

$$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n-1} (-1)^{x \cdot z} |z\rangle$$

where $x \cdot z$ is the bitwise inner product modulo 2.

Key property: $H^{\otimes 2n} = H^{\otimes n} \otimes H^{\otimes n}$, so applying $H$ to all qubits is the same as applying it to each qubit individually. This parallelizability makes the Walsh-Hadamard transform very cheap: $n$ gates, depth 1.

7.10.2 The Phase Oracle Pattern

Many quantum algorithms (Grover's, amplitude amplification) use phase oracles:

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

This can be constructed from a standard oracle by sandwiching the target qubit between Hadamards:

|x⟩ ──●── |x⟩
       │
|−⟩ ──⊕── |−⟩

where $|-\rangle = H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$.

Proof that this works: The standard oracle is $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$. With $|-\rangle$ on the target:

$$U_f|x\rangle|-\rangle = |x\rangle \frac{1}{\sqrt{2}}(|0 \oplus f(x)\rangle - |1 \oplus f(x)\rangle)$$

If $f(x) = 0$: $\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |-\rangle$ If $f(x) = 1$: $\frac{1}{\sqrt{2}}(|1\rangle - |0\rangle) = -|-\rangle$

So $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$. The phase is "kicked back" to the input register. ✓

7.10.3 The Uncompute Pattern

To avoid entangled garbage, quantum algorithms must uncompute intermediate results:

|x⟩ ── U_f ── (computation) ── U_f† ── |x⟩
|0⟩ ──⊕──    (ancilla)      ──⊕──    ── |0⟩

The ancilla qubits return to $|0\rangle$, allowing reuse and preventing unwanted entanglement with the output.

Why uncomputation matters: Without it, the garbage qubits remain entangled with the output, degrading the computation. In the extreme case, the output density matrix becomes maximally mixed, destroying all information.

Worked Example 7.8: Uncomputation in the Deutsch-Jozsa algorithm

In Deutsch-Jozsa, we evaluate $f: \{0,1\}^n \to \{0,1\}$ and need to determine whether it's constant or balanced. The phase oracle uses one ancilla qubit, but after applying the phase kickback, the ancilla returns to $|-\rangle$. No separate uncomputation is needed because the ancilla was never entangled with the input register — it was always in $|-\rangle$.

But in more complex algorithms (like modular exponentiation in Shor's algorithm), we must explicitly uncompute. The pattern is:

1. Compute: $|x\rangle|0\rangle \xrightarrow{U_f} |x\rangle|f(x)\rangle$
2. Use the result in further computation
3. Uncompute: $|x\rangle|f(x)\rangle \xrightarrow{U_f^\dagger} |x\rangle|0\rangle$

The uncomputation step $U_f^\dagger$ is always possible because $U_f$ is unitary (reversible).

7.10.4 The Quantum Multiplexor Pattern

A controlled operation where the control is an $n$-qubit register (not just one qubit) is called a multiplexor:

$$\text{MUX}_n |x\rangle|y\rangle = |x\rangle U_x |y\rangle$$

where each $U_x$ is a potentially different unitary. This pattern appears in quantum arithmetic (conditional rotation based on a register value) and in quantum walks.

The multiplexor can be decomposed into $2^n - 1$ controlled-$U$ gates, but more efficient decompositions exist using Gray codes and the catalytic method.

7.11 Controlled Operations in Depth

7.11.1 Building a Controlled-U Gate

Any single-qubit unitary $U$ can be turned into a controlled version using the decomposition:

$$\text{Controlled-}U = (I \otimes A) \cdot \text{CNOT} \cdot (I \otimes B) \cdot \text{CNOT} \cdot (I \otimes C)$$

where $A$, $B$, $C$ are chosen such that $ABC = I$ and $AXBXC = U$.

Proof sketch: When the control qubit is $|0\rangle$, the CNOTs act as identity on the target, so the target gets $ABC = I$. When the control is $|1\rangle$, the CNOTs flip between $A$ and $B$ phases, giving $AXBXC = U$.

For $U = R_z(\theta)$: $A = R_z(\theta/2)$, $B = R_z(-\theta/2)$, $C = I$. This gives controlled-$R_z(\theta)$ using 2 CNOTs and 2 single-qubit rotations.

For $U = R_y(\theta)$: $A = R_y(\theta/2)$, $B = R_y(-\theta/2)$, $C = I$.

For a general $U(\alpha, \beta, \gamma, \delta) = e^{i\alpha} R_z(\beta) R_y(\gamma) R_z(\delta)$:

$$A = R_z(\beta) R_y(\gamma/2), \quad B = R_y(-\gamma/2) R_z(-(\beta+\delta)/2), \quad C = R_z((\delta-\beta)/2)$$

from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
import numpy as np

def controlled_u_gate(theta, phi, lam, gamma=0):
    """Build a controlled-U(theta, phi, lam) gate from CNOTs."""
    qc = QuantumCircuit(2)
    # Decomposition following Nielsen & Chuang
    # For U(theta, phi, lam):
    alpha = (phi + lam) / 2
    beta = (phi - lam) / 2

    qc.rz((delta := (lam - phi)/2), 1)
    qc.cx(0, 1)
    qc.rz(-(phi + lam)/2, 1)
    qc.ry(-theta/2, 1)
    qc.cx(0, 1)
    qc.ry(theta/2, 1)
    qc.rz(phi, 1)

    return qc

# Verify: controlled-H
from qiskit.circuit.library import HGate
qc_ctrl_h = QuantumCircuit(2)
qc_ctrl_h.append(HGate().control(), [0, 1])

U_ours = Operator(controlled_u_gate(np.pi/2, 0, np.pi))
U_ref = Operator(qc_ctrl_h)
print(f"Controlled-H matches reference: {np.allclose(U_ours.data, U_ref.data, atol=1e-8)}")

7.11.2 Multi-Controlled Gates

A CNOT with $k$ control qubits (a $C^k$NOT or $k$-fold controlled-NOT) can be decomposed into $O(k)$ Toffoli gates using $k-1$ ancilla qubits, or $O(k^2)$ Toffoli gates without ancillas.

Without ancillas (Barenco et al.): A $C^k$NOT can be implemented using $O(k^2)$ basic gates (CNOT, Toffoli, and single-qubit gates).

With $k-1$ ancilla qubits: A $C^k$NOT can be implemented using $2(k-1)$ Toffoli gates: first "spread" the control to the ancillas, then use the ancillas as additional controls.

a: ──●───────────────────────●──
     │                       │
b: ──●───────────────────────●──
     │                       │
c: ──⊕──●── (ancilla 1) ──⊕──●──
         │                       │
d: ──────⊕──●── (ancilla 2) ──⊕──
              │
e: ───────────⊕── (target) ──────

from qiskit import QuantumCircuit

def multi_controlled_x(n_controls):
    """Build a multi-controlled X using ancilla qubits."""
    n_total = n_controls + 1  # controls + target
    n_ancilla = n_controls - 1
    total_qubits = n_total + n_ancilla

    qc = QuantumCircuit(total_qubits)

    # Forward sweep: spread control to ancillas
    ctrl_qubits = list(range(n_controls))
    ancilla_qubits = list(range(n_total, total_qubits))
    target = n_controls

    # Build up controls layer by layer
    # First Toffoli: controls 0,1 -> ancilla[0]
    qc.ccx(ctrl_qubits[0], ctrl_qubits[1], ancilla_qubits[0])

    # Subsequent Toffolis: control[i], ancilla[i-2] -> ancilla[i-1]
    for i in range(2, n_controls):
        qc.ccx(ctrl_qubits[i], ancilla_qubits[i-2], ancilla_qubits[i-1])

    # Final Toffoli: last ancilla -> target
    qc.ccx(ctrl_qubits[-1], ancilla_qubits[-1], target)

    return qc

qc = multi_controlled_x(4)
print("4-controlled X gate:")
print(qc.draw('text'))
print(f"Depth: {qc.depth()}, Toffoli count: {qc.count_ops().get('ccx', 0)}")

7.12 The SWAP Gate and SWAP Networks

The SWAP gate exchanges two qubits:

$$\text{SWAP}|a, b\rangle = |b, a\rangle$$

Its matrix representation is:

$$\text{SWAP} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

Decomposition into CNOTs:

$$\text{SWAP} = \text{CNOT}_{a \to b} \cdot \text{CNOT}_{b \to a} \cdot \text{CNOT}_{a \to b}$$

q_0: ──●── X ──●──
       │   │   │
q_1: ── X ──●── X ──

Proof: Let's verify on each computational basis state:

• $\text{SWAP}|00\rangle = |00\rangle$: CNOT$_{0\to1}|00\rangle = |00\rangle$, CNOT$_{1\to0}|00\rangle = |00\rangle$, CNOT$_{0\to1}|00\rangle = |00\rangle$. ✓
• $\text{SWAP}|01\rangle = |10\rangle$: CNOT$_{0\to1}|01\rangle = |01\rangle$ (control=0), CNOT$_{1\to0}|01\rangle = |11\rangle$ (control=1, flips q0), CNOT$_{0\to1}|11\rangle = |10\rangle$ (control=1, flips q1). ✓
• $\text{SWAP}|10\rangle = |01\rangle$: CNOT$_{0\to1}|10\rangle = |11\rangle$ (control=1, flips q1), CNOT$_{1\to0}|11\rangle = |01\rangle$ (control=1, flips q0), CNOT$_{0\to1}|01\rangle = |01\rangle$ (control=0). ✓
• $\text{SWAP}|11\rangle = |11\rangle$: Similar verification. ✓

Cost: Each SWAP costs 3 CNOTs (6 CNOTs per SWAP if using a linear nearest-neighbor architecture). This is why qubit connectivity matters so much — SWAPs are expensive.

7.13 Advanced Circuit Patterns

7.13.1 The Quantum Adder

A quantum adder adds two n-bit numbers coherently — for all possible inputs simultaneously. The simplest adder uses the Cuccaro adder circuit, which implements $|a\rangle|b\rangle|0\rangle \to |a\rangle|a+b\rangle|0\rangle$ using Toffoli and CNOT gates.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

def create_ripple_carry_adder(n_bits):
    """Create a ripple-carry adder for n-bit numbers.
    Adds |a⟩|b⟩|0⟩ → |a⟩|a+b⟩|0⟩

    Qubit layout:
      q[0:n] = a (n qubits)
      q[n:2n] = b (n qubits, will hold the sum)
      q[2n] = carry in/out
    """
    n = n_bits
    total_qubits = 2 * n + 1
    qc = QuantumCircuit(total_qubits)

    # Ripple-carry addition
    # Major part (carry computation)
    for i in range(n):
        if i == 0:
            qc.cx(n, 2*n)  # b[0] → carry
            qc.cx(i, n)     # a[0] → b[0]
            qc.ccx(i, 2*n, n)  # carry computation
        else:
            qc.cx(i+n, 2*n)
            qc.cx(i, i+n)
            qc.ccx(i, i+n, 2*n)

    qc.cx(0, n)  # First sum bit

    # Minor part (sum computation)
    for i in range(1, n):
        qc.cx(i, i+n)  # Sum computation

    return qc

# Test the adder for 2-bit numbers
print("2-bit Quantum Adder Test")
print("=" * 40)
sim = AerSimulator()

for a in range(4):
    for b in range(4):
        qc = QuantumCircuit(5, 3)

        # Encode a
        if a & 1: qc.x(0)
        if a & 2: qc.x(1)

        # Encode b
        if b & 1: qc.x(2)
        if b & 2: qc.x(3)

        # Add using simple approach
        # Carry: c = a[0]&b[0] for LSB
        qc.ccx(0, 2, 4)  # carry from bit 0
        qc.cx(0, 2)       # sum bit 0 (without carry)
        qc.cx(1, 3)       # pass bit 1
        qc.ccx(1, 3, 4)   # carry from bit 1
        qc.cx(4, 3)        # add carry to bit 1

        qc.measure([2, 3, 4], [0, 1, 2])

        result = sim.run(qc, shots=1024).result()
        counts = result.get_counts()
        outcome = list(counts.keys())[0]
        sum_val = int(outcome[1:], 2)  # Convert from binary

        expected = (a + b) % 4
        carry = 1 if a + b >= 4 else 0
        print(f"  {a} + {b} = {sum_val} (carry={outcome[0]})", end="")
        print(f"  {'✓' if sum_val == (a+b)%4 else '✗'}")

7.13.2 The Quantum Multiplexer

A quantum multiplexer (also called a uniformly controlled rotation) applies different rotations to a target qubit depending on the state of control qubits. This is a building block for quantum arithmetic and quantum neural networks.

from qiskit import QuantumCircuit
from qiskit.circuit.library import UCRYGate
import numpy as np

# Uniformly controlled R_y gate: 2^k different rotations
# controlled by k qubits
angles = np.random.random(4) * np.pi  # 4 angles for 2 control qubits

qc = QuantumCircuit(3)
qc.append(UCRYGate(angles), [0, 1, 2])  # Controls: q0, q1; Target: q2

print("Uniformly controlled R_y circuit:")
print(qc.draw('text'))

# Verify: each control state applies a different rotation
from qiskit.quantum_info import Statevector

for ctrl_state in range(4):
    test_qc = QuantumCircuit(3)
    # Set control state
    if ctrl_state & 1: test_qc.x(0)
    if ctrl_state & 2: test_qc.x(1)
    test_qc.append(UCRYGate(angles), [0, 1, 2])

    sv = Statevector.from_instruction(test_qc)
    # The target qubit should be rotated by angles[ctrl_state]
    expected_angle = angles[ctrl_state]
    print(f"  Control {ctrl_state:02b}: angle={expected_angle:.4f}")

7.13.3 The Diagonal Gate

A diagonal gate applies a phase to each computational basis state:

$$U_{\text{diag}} = \text{diag}(e^{i\phi_0}, e^{i\phi_1}, \ldots, e^{i\phi_{2^n-1}})$$

This is useful for phase oracles, quantum walks, and quantum signal processing.

from qiskit import QuantumCircuit
from qiskit.circuit.library import Diagonal
import numpy as np

# Create a 2-qubit diagonal gate with specific phases
phases = [0, np.pi/4, np.pi/2, 3*np.pi/4]

diag_gate = Diagonal(phases)
qc = QuantumCircuit(2)
qc.append(diag_gate, [0, 1])

print("Diagonal gate circuit:")
print(qc.decompose().draw('text'))

7.13.4 Quantum Random Access Memory (QRAM)

QRAM is a circuit that addresses quantum memory: given an index qubit in superposition, it outputs the corresponding data in superposition.

$$\text{QRAM}: \frac{1}{\sqrt{N}} \sum_x |x\rangle |0\rangle \to \frac{1}{\sqrt{N}} \sum_x |x\rangle |f(x)\rangle$$

While true QRAM would require $O(N)$ physical memory elements, there are efficient constructions for structured data. The simplest is a lookup table:

from qiskit import QuantumCircuit

def qram_lookup_table(data):
    """Implement a simple QRAM lookup table.

    data: list of bit strings, e.g., ['00', '01', '10', '11']
    Maps |address⟩|00⟩ → |address⟩|data[address]⟩
    """
    n_address = int(np.log2(len(data)))
    n_data = len(data[0])

    qc = QuantumCircuit(n_address + n_data)

    for i, value in enumerate(data):
        # Apply X gates to set up the address
        address_bits = format(i, f'0{n_address}b')
        for j, bit in enumerate(address_bits):
            if bit == '0':
                qc.x(j)

        # Multi-controlled NOT for each data bit
        for k, data_bit in enumerate(value):
            if data_bit == '1':
                # Apply multi-controlled X on data qubit k
                controls = list(range(n_address))
                qc.mcx(controls, n_address + k)

        # Uncompute the X gates
        for j, bit in enumerate(address_bits):
            if bit == '0':
                qc.x(j)

    return qc

# Example: QRAM for a simple database
data = ['00', '01', '10', '11']  # data[0]=00, data[1]=01, etc.
qc_qram = qram_lookup_table(data)
print("QRAM circuit for database [00, 01, 10, 11]:")
print(qc_qram.draw('text'))
print(f"\nCircuit depth: {qc_qram.depth()}")
print(f"Gate count: {qc_qram.size()}")

Common Misconception. "QRAM provides exponential speedup for data lookup." Not necessarily. QRAM allows quantum parallel access to data, but the circuit depth is $O(N)$ in the worst case. True quantum advantage requires the data to have structure that quantum algorithms can exploit (as in Grover's search).

7.14 The Stinespring Dilation and Circuit Representations

Every quantum channel (including noisy channels) can be represented as a unitary on a larger system followed by partial trace. This is the Stinespring dilation theorem, and it provides a circuit-based perspective on noise.

Statement: For any completely positive trace-preserving (CPTP) map $\mathcal{E}: \mathcal{L}(\mathcal{H}_A) \to \mathcal{L}(\mathcal{H}_B)$, there exists an ancillary Hilbert space $\mathcal{H}_E$ and a unitary $U: \mathcal{H}_A \otimes \mathcal{H}_E \to \mathcal{H}_B \otimes \mathcal{H}_E$ such that:

$$\mathcal{E}(\rho_A) = \text{Tr}_E\left[U(\rho_A \otimes |0\rangle\langle 0|_E)U^\dagger\right]$$

Circuit representation:

Data qubit:    |ρ⟩ ────┌───────┐──── Tr ──── |𝓔(ρ)⟩
                      │       │
Ancilla:       |0⟩ ────┤   U   ├── Tr ──── (traced out)
                      │       │

The ancilla qubits capture the "environment" — tracing them out (partial trace over $E$) gives the noisy output.

Worked Example 7.9: Amplitude damping channel

The amplitude damping channel models energy relaxation (T1 decay): a qubit in $|1\rangle$ decays to $|0\rangle$ with probability $\gamma$.

$$\mathcal{E}(\rho) = E_0 \rho E_0^\dagger + E_1 \rho E_1^\dagger$$

where $E_0 = \begin{pmatrix} 1 & 0 \\ 0 & \sqrt{1-\gamma} \end{pmatrix}$ and $E_1 = \begin{pmatrix} 0 & \sqrt{\gamma} \\ 0 & 0 \end{pmatrix}$.

Circuit implementation: Using a controlled-Y rotation on an ancilla:

Data qubit:    |ρ⟩ ────●───────── M ────
                       │
Ancilla:       |0⟩ ──── R_y(θ) ──── (traced out)

where $\theta = 2\arccos(\sqrt{1-\gamma})$ and the measurement outcome determines whether damping occurred.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector, DensityMatrix, partial_trace
import numpy as np

def amplitude_damping_circuit(gamma, input_state):
    """Implement amplitude damping via Stinespring dilation."""
    qr = QuantumRegister(2, 'q')  # data + ancilla
    cr = ClassicalRegister(1, 'c')
    qc = QuantumCircuit(qr, cr)

    # Prepare input state on data qubit
    qc.initialize(input_state, qr[0])

    # Amplitude damping: controlled rotation on ancilla
    theta = 2 * np.arccos(np.sqrt(1 - gamma))
    qc.ry(theta, qr[1])
    qc.cx(qr[1], qr[0])

    # Trace out ancilla
    state = Statevector.from_instruction(qc.remove_final_measurements(inplace=False))
    rho = DensityMatrix(state)
    rho_data = partial_trace(rho, [1])

    return rho_data

# Test amplitude damping on |1⟩ with γ = 0.3
gamma = 0.3
rho_in = DensityMatrix([0, 1])  # |1⟩⟨1|
rho_out = amplitude_damping_circuit(gamma, [0, 1])
print(f"Input: |1⟩⟨1|")
print(f"Output (γ={gamma}):\n{np.round(rho_out.data, 4)}")
print(f"P(|0⟩) = {rho_out.data[0,0].real:.4f} (expected γ={gamma})")
print(f"P(|1⟩) = {rho_out.data[1,1].real:.4f} (expected 1-γ={1-gamma})")

7.15 Circuit Simulation: Classical Complexity

Not all quantum circuits can be efficiently simulated classically. Understanding which circuits can be simulated gives insight into where quantum advantage comes from.

7.15.1 Efficiently Simulable Circuit Classes

7.15.2 The Gottesman-Knill Theorem

The Gottesman-Knill theorem states that any quantum circuit composed of: 1. Preparation of qubits in computational basis states 2. Application of Clifford gates ($H$, $S$, $CNOT$) 3. Measurement in the computational basis

can be efficiently simulated on a classical computer in time $O(n^2)$.

This is why the $T$ gate (which is not Clifford) is essential for universal quantum computation. Without $T$, all circuits can be classically simulated.

The stabilizer formalism: A stabilizer state on $n$ qubits is described by $n$ Pauli operators that stabilize it. Each stabilizer is a product of Pauli matrices ($I$, $X$, $Y$, $Z$) on $n$ qubits. The action of Clifford gates on stabilizers can be computed efficiently by updating the stabilizer tableau.

from qiskit import QuantumCircuit
from qiskit.quantum_info import StabilizerState

# A Clifford circuit: H, CNOT, S
qc = QuantumCircuit(3)
qc.h(0)
qc.cx(0, 1)
qc.s(1)
qc.cx(1, 2)

# Compute the stabilizer state efficiently
stab = StabilizerState(qc)
print("Stabilizer generators:")
for gen in stab.stabilizer:
    print(f"  {gen}")
print(f"\nNumber of stabilizers: {len(stab.stabilizer)}")
print(f"This circuit can be classically simulated in O(n^2) time!")

7.15.3 When Is Quantum Advantage Possible?

Quantum advantage requires circuits that are hard to simulate classically. This typically means: 1. Non-Clifford gates ($T$, $R_z$ with arbitrary angles, etc.) 2. Sufficient depth ($d \gg 1$) 3. Sufficient entanglement (not just shallow or low-entanglement circuits)

The "golden zone" for quantum advantage is: - Deep enough to generate complex entanglement patterns - Wide enough to exceed classical simulation capacity ($n > 40-50$ qubits) - With enough non-Clifford gates to escape the Gottesman-Knill simulation

Recurring Theme. We're at the beginning. Current quantum computers can demonstrate small-scale advantages, but consistent, practical quantum advantage over the best classical algorithms remains an active frontier. Understanding circuit complexity is key to identifying where advantage lies.

7.16 Quantum Circuit Optimization Techniques

7.16.1 Peephole Optimization

Peephole optimization scans a small window of the circuit and applies local transformations:

1. Gate cancellation: Remove adjacent inverse pairs ($G \cdot G^\dagger = I$)
2. Gate merging: Combine adjacent rotations ($R_z(\theta) \cdot R_z(\phi) = R_z(\theta+\phi)$)
3. Gate commutation: Reorder gates to enable further cancellations
4. Template matching: Replace known subcircuit patterns with shorter equivalents

from qiskit import QuantumCircuit
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import (
    Optimize1qGatesDecomposition,
    CommutationAnalysis,
    CommutativeCancellation,
    RemoveDiagonalGatesBeforeMeasure
)

# Build a circuit with optimization opportunities
qc = QuantumCircuit(2)
qc.h(0)
qc.cx(0, 1)
qc.h(0)        # H after CNOT can be commuted
qc.cx(0, 1)    # CNOT after CNOT = identity? No, different control/target
qc.h(0)        # Three H's = H (since H^3 = H)
qc.z(0)
qc.z(0)        # Z^2 = I, cancels

print("Before optimization:")
print(qc.draw('text'))
print(f"Depth: {qc.depth()}, Gates: {qc.size()}")

# Apply peephole optimization
pm = PassManager([
    CommutativeCancellation(),
    Optimize1qGatesDecomposition(),
    RemoveDiagonalGatesBeforeMeasure()
])
qc_opt = pm.run(qc)

print("\nAfter optimization:")
print(qc_opt.draw('text'))
print(f"Depth: {qc_opt.depth()}, Gates: {qc_opt.size()}")

7.16.2 Template Matching

Template matching is a systematic approach: maintain a library of circuit templates (equivalent circuits with different gate counts) and search the circuit for instances of the longer template, replacing them with the shorter one.

Example template:

Template: ── H ── T ── H ── T ── H ──  =  ── S ── T† ──

This template identifies that $H \cdot T \cdot H \cdot T \cdot H = S \cdot T^\dagger$, reducing 5 gates to 2.

# Template matching example
from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
import numpy as np

# Original: 5 gates
qc_long = QuantumCircuit(1)
qc_long.h(0)
qc_long.t(0)
qc_long.h(0)
qc_long.t(0)
qc_long.h(0)

# Replacement: 2 gates
qc_short = QuantumCircuit(1)
qc_short.s(0)
qc_short.tdg(0)

# Verify equivalence
U_long = Operator(qc_long)
U_short = Operator(qc_short)
print(f"Equivalent? {np.allclose(U_long.data, U_short.data, atol=1e-10)}")
print(f"Long circuit: depth={qc_long.depth()}, gates={qc_long.size()}")
print(f"Short circuit: depth={qc_short.depth()}, gates={qc_short.size()}")

7.16.3 Resynthesis

Resynthesis takes a subcircuit, computes its unitary, and re-synthesizes it using a potentially different gate set with fewer gates. This is particularly effective for long sequences of single-qubit gates.

from qiskit import QuantumCircuit
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import UnitarySynthesis, Optimize1qGatesDecomposition

# A long single-qubit gate sequence
qc = QuantumCircuit(1)
qc.rz(0.3, 0)
qc.rx(0.7, 0)
qc.rz(1.2, 0)
qc.rx(0.1, 0)
qc.rz(0.5, 0)

print("Before resynthesis:")
print(qc.draw('text'))
print(f"Depth: {qc.depth()}, Gates: {qc.size()}")

# Optimize
pm = PassManager([Optimize1qGatesDecomposition()])
qc_opt = pm.run(qc)

print("\nAfter resynthesis:")
print(qc_opt.draw('text'))
print(f"Depth: {qc_opt.depth()}, Gates: {qc_opt.size()}")

The resynthesis pass reduces the 5-gate sequence to a minimum decomposition (typically 3 gates: $U(\theta, \phi, \lambda)$ using the Euler decomposition).