Introduction to Quantum Computing: Qubits, Quantum Gates, and Quantum Circuits
Introduction to Quantum Computing: Qubits, Quantum Gates, and Quantum Circuits
Quantum computing is the application of quantum mechanical phenomena — superposition, entanglement, and interference — to information processing. Where classical computers encode information in bits taking values $0$ or $1$, quantum computers use qubits, two-level quantum systems whose state is a superposition $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ with $|\alpha|^2 + |\beta|^2 = 1$. This is not merely a matter of "being 0 and 1 simultaneously" — rather, it is a precise mathematical statement that a qubit lives in the two-dimensional complex Hilbert space $\mathbb{C}^2$, and this structure, when exploited through carefully designed quantum algorithms, enables computational speedups that are provably impossible with classical hardware.
The fundamental resource advantage of quantum computing lies in quantum parallelism and interference. An $n$-qubit register initialized to $|0\rangle^{\otimes n}$ and passed through Hadamard gates is in a uniform superposition of all $2^n$ basis states simultaneously. A quantum algorithm then applies a unitary transformation that encodes the problem's structure. Crucially, the transformation must be designed so that amplitudes corresponding to correct answers interfere constructively, while amplitudes for wrong answers interfere destructively — a process of quantum amplitude amplification. Without this interference step, measurement would yield a random basis state with no useful information.
Single-qubit gates are $2\times2$ unitary matrices acting on $\mathbb{C}^2$. The Hadamard gate $H = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ creates equal superpositions: $H|0\rangle = |+\rangle$, $H|1\rangle = |-\rangle$. The Pauli gates $X$, $Y$, $Z$ implement rotations by $\pi$ about the $x$, $y$, $z$ axes of the Bloch sphere. The phase gate $S = \begin{pmatrix}1&0\\0&i\end{pmatrix}$ and $T = \begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}$ gates implement $\pi/2$ and $\pi/4$ phase rotations. The continuous family $R_z(\theta) = e^{-i\theta Z/2} = \begin{pmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{pmatrix}$ (and similarly $R_x, R_y$) generates all single-qubit unitaries: any $U \in SU(2)$ can be written as $U = R_z(\alpha)R_y(\beta)R_z(\gamma)$ (Euler angle decomposition).
Two-qubit gates are $4\times4$ unitary matrices on $\mathbb{C}^2 \otimes \mathbb{C}^2$. The most important is the CNOT (controlled-NOT): $\text{CNOT}|c\rangle|t\rangle = |c\rangle|t\oplus c\rangle$, which flips the target qubit iff the control qubit is $|1\rangle$. In matrix form: $\text{CNOT} = \begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}$. The CZ gate applies $Z$ to the target iff the control is $|1\rangle$. The SWAP gate exchanges two qubits: $\text{SWAP} = \frac{1}{2}(I\otimes I + X\otimes X + Y\otimes Y + Z\otimes Z)$. The Toffoli (CCNOT) gate flips the target iff both controls are $|1\rangle$ and is universal for classical reversible computation.
Universality is a central theorem of quantum computing: the gate set $\{H, T, \text{CNOT}\}$ is universal for quantum computation — any $n$-qubit unitary can be approximated to precision $\epsilon$ using $O(\text{poly}(n, \log(1/\epsilon)))$ gates from this set. The Solovay-Kitaev theorem makes this precise: the number of gates needed grows as $O(\log^c(1/\epsilon))$ for some constant $c < 4$. This means that despite the continuous nature of quantum gates, a finite discrete gate set suffices for all practical purposes.
Physical implementations of qubits span several distinct platforms. Superconducting qubits (used by Google, IBM, Rigetti) exploit Josephson junction nonlinearity to create anharmonic oscillators with addressable two-level structure; gate times are $\sim 10$-$100$ ns, $T_1 \sim T_2 \sim 100\,\mu$s, and single/two-qubit gate fidelities exceed $99.9\%$/$99\%$. Trapped ion qubits (IonQ, Honeywell) use electronic or hyperfine states of laser-cooled ions; they achieve $T_2 > 1$ s and two-qubit gate fidelities $>99.9\%$ but are slower ($\mu$s gate times) and harder to scale. Photonic qubits use polarization or path degree of freedom of photons; they are naturally room-temperature and communicate at the speed of light, but two-qubit gates require measurement-based probabilistic schemes. Silicon spin qubits leverage decades of semiconductor fabrication expertise and may offer the best scalability path.
Circuit complexity and fidelity are the key practical metrics. Circuit depth is the number of sequential layers of gates (parallel gates count once); deeper circuits accumulate more error. Gate error rate $\epsilon_g \sim 10^{-3}$ for superconducting qubits sets a limit: circuits with more than $\sim 1/\epsilon_g = 1000$ gates per qubit cannot be executed reliably without quantum error correction. Quantum error correction (QEC) encodes a logical qubit in many physical qubits (e.g., the surface code uses $\sim d^2$ physical qubits for distance $d$, achieving logical error rate $\sim (p/p_{\text{th}})^{(d+1)/2}$ where $p_{\text{th}} \approx 1\%$ is the threshold). Fault-tolerant quantum computing — universal computation with arbitrarily low logical error rate — requires $\sim 1000$ physical qubits per logical qubit with current hardware, motivating the development of large-scale quantum processors.
Key quantum algorithms demonstrate computational advantages. Grover's search algorithm finds a marked item in an unstructured database of $N$ items in $O(\sqrt{N})$ queries vs $O(N)$ classically — a quadratic speedup. Shor's algorithm factors an $n$-bit integer using $O(n^3)$ quantum gates vs the best classical algorithm's $\exp(n^{1/3})$, an exponential speedup that threatens current RSA cryptography. The Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear systems of equations offers exponential speedup under certain conditions. The variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) are hybrid classical-quantum algorithms designed for near-term noisy devices, targeting quantum chemistry and combinatorial optimization.
A qubit is the quantum unit of information — a two-level quantum system with Hilbert space $\mathcal{H} = \mathbb{C}^2$ and computational basis $\{|0\rangle, |1\rangle\}$. General state: $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, $|\alpha|^2 + |\beta|^2 = 1$. In Bloch sphere form: $|\psi\rangle = \cos(\theta/2)|0\rangle + e^{i\phi}\sin(\theta/2)|1\rangle$. An $n$-qubit register has Hilbert space $(\mathbb{C}^2)^{\otimes n} \cong \mathbb{C}^{2^n}$ with $2^n$ computational basis states $|x_1 x_2\cdots x_n\rangle$, $x_i \in \{0,1\}$. A general $n$-qubit state is $|\Psi\rangle = \sum_{x\in\{0,1\}^n} c_x|x\rangle$ with $\sum_x|c_x|^2 = 1$ — an exponentially large superposition described by $2^n$ complex amplitudes.
A quantum gate on $n$ qubits is a unitary operator $U: (\mathbb{C}^2)^{\otimes n} \to (\mathbb{C}^2)^{\otimes n}$, i.e., $UU^\dagger = U^\dagger U = I$. Single-qubit gates are elements of $U(2)$; gates in $SU(2)$ (determinant $+1$) form the special unitary group. Key single-qubit gates:
$$H = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\; X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\; Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\; Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$$
$$S=\begin{pmatrix}1&0\\0&i\end{pmatrix},\; T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix},\; R_z(\theta)=\begin{pmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{pmatrix}$$
The gate set $\mathcal{G} = \{H, T, \text{CNOT}\}$ is universal for quantum computation: for any $n$-qubit unitary $U \in U(2^n)$ and any $\epsilon > 0$, there exists a circuit $V$ over $\mathcal{G}$ with $\|U - V\| \leq \epsilon$ and circuit size $\text{poly}(n, 1/\epsilon)$. The Solovay-Kitaev theorem further guarantees that the number of gates required is $O(\log^c(1/\epsilon))$ for $c < 4$ (empirically $c \approx 2$). The $T$ gate (or equivalently $\pi/8$ gate) is the crucial non-Clifford gate: $\{H, \text{CNOT}, S\}$ generates the Clifford group (efficiently simulable classically), while adding $T$ achieves universal quantum computation.
The CNOT gate in the $\{|00\rangle,|01\rangle,|10\rangle,|11\rangle\}$ basis acts as $\text{CNOT}|c,t\rangle = |c, t\oplus c\rangle$, where $\oplus$ is addition modulo 2 (XOR). Matrix representation:
$$\text{CNOT} = \begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}$$
The Bell state preparation circuit applies $H$ to the first qubit then $\text{CNOT}$: $|00\rangle \xrightarrow{H\otimes I} \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)|0\rangle \xrightarrow{\text{CNOT}} \frac{1}{\sqrt{2}}(|00\rangle+|11\rangle) = |\Phi^+\rangle$. This is the prototypical entanglement-generating circuit.
Apply the Hadamard gate to $|0\rangle$ and $|1\rangle$. Then verify that $H^2 = I$ (Hadamard is its own inverse).
$H|0\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix} = \frac{|0\rangle+|1\rangle}{\sqrt{2}} = |+\rangle$.
$H|1\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\-1\end{pmatrix} = \frac{|0\rangle-|1\rangle}{\sqrt{2}} = |-\rangle$.
$H^2$: $H^2 = \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} = I$. ✓
Hadamard is Hermitian ($H^\dagger = H$) and unitary ($H^\dagger H = I$), hence $H^2 = I$ — the Hadamard gate is its own inverse. Geometrically, it is a reflection on the Bloch sphere about the axis bisecting $x$ and $z$.
Apply the $T$ gate followed by $H$ to the state $|0\rangle$. Find the output state and its Bloch sphere coordinates $(\theta, \phi)$.
Step 1 — Apply $T$ to $|0\rangle$: $T|0\rangle = \begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix} = |0\rangle$. (The $T$ gate leaves $|0\rangle$ invariant up to global phase.)
Step 2 — Apply $H$: $H|0\rangle = |+\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix}$.
Bloch coordinates of $|+\rangle$: $\alpha = 1/\sqrt{2}$, $\beta = 1/\sqrt{2}$. Then $\cos(\theta/2) = 1/\sqrt{2}$, so $\theta/2 = \pi/4$, $\theta = \pi/2$. And $e^{i\phi}\sin(\pi/4) = 1/\sqrt{2}$, so $e^{i\phi} = 1$, $\phi = 0$.
Final state: $\theta = \pi/2$, $\phi = 0$ — the $|+\rangle$ state on the equator of the Bloch sphere pointing along the $+x$ axis. $P(\uparrow) = \cos^2(\pi/4) = 1/2$.
Construct the quantum circuit to prepare the Bell state $|\Phi^+\rangle$ and verify the output state explicitly.
Circuit: Two qubits start in $|00\rangle$. Apply $H$ to qubit 1 (control), then CNOT with qubit 1 as control and qubit 2 as target.
Step 1: $H\otimes I|00\rangle = H|0\rangle\otimes|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\otimes|0\rangle = \frac{1}{\sqrt{2}}(|00\rangle+|10\rangle)$.
Step 2: $\text{CNOT}(H\otimes I|00\rangle) = \frac{1}{\sqrt{2}}(\text{CNOT}|00\rangle + \text{CNOT}|10\rangle) = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = |\Phi^+\rangle$. ✓
This is a maximally entangled Bell state. If qubit 1 is measured in the $z$-basis and gives $|0\rangle$, qubit 2 is immediately in $|0\rangle$; if qubit 1 gives $|1\rangle$, qubit 2 is in $|1\rangle$ — perfect correlation across arbitrary distances.
A superconducting quantum processor has a two-qubit gate fidelity of $\mathcal{F} = 99.5\%$ (error rate $\epsilon = 0.005$ per gate). Estimate the maximum circuit depth (two-qubit gate layers) before the logical error rate exceeds $10\%$, and estimate the number of physical qubits needed to encode one error-corrected logical qubit using the surface code with code distance $d=5$.
Maximum depth without error correction: For $n$ gate layers, error accumulates as $P_{\text{error}} \approx 1-(1-\epsilon)^n \approx n\epsilon$ for small $\epsilon$. Setting $n\epsilon = 0.10$: $n = 0.10/0.005 = 20$ layers. Circuits deeper than $\sim 20$ two-qubit gate layers have $>10\%$ logical error rate on one qubit — severely limiting useful computation.
Surface code encoding: Distance-$d$ surface code requires $d^2$ data qubits and $(d^2-1)$ ancilla qubits for syndrome measurement. For $d=5$: $25 + 24 = 49$ physical qubits per logical qubit. Logical error rate: $\sim (p/p_{\text{th}})^{(d+1)/2} = (0.005/0.01)^3 = (0.5)^3 = 0.125$ per error correction cycle. For $d=7$: $(0.5)^4 = 0.0625$ per cycle with $49+48=97$ physical qubits. To reach $10^{-6}$ logical error rate would require $d \sim 17$ ($\sim 578$ physical qubits per logical qubit).
Practice Problems
Show Answer Key
1. $|+\rangle = \frac{1}{\sqrt{2}}\binom{1}{1}$. $X|+\rangle = \frac{1}{\sqrt{2}}\binom{1}{1} = |+\rangle$. $Z|+\rangle = \frac{1}{\sqrt{2}}\binom{1}{-1} = |-\rangle$. Geometrically: $X$ is a $180°$ rotation about the $x$-axis, leaving $|+\rangle$ (on the $+x$ equator) invariant. $Z$ is a $180°$ rotation about $z$, mapping $|+\rangle \to |-\rangle$ (reflection through the $x=0$ plane).
2. $HXH = \frac{1}{2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\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} = Z$. ✓ By symmetry $HZH = X$. This shows $H$ conjugates Pauli $X \leftrightarrow Z$, implementing a basis change between $\{|0\rangle,|1\rangle\}$ ($z$-basis) and $\{|+\rangle,|-\rangle\}$ ($x$-basis).
3. $H|0\rangle = |+\rangle = \frac{1}{\sqrt{2}}\binom{1}{1}$. $S|+\rangle = \frac{1}{\sqrt{2}}\binom{1}{i}$. $H\cdot\frac{1}{\sqrt{2}}\binom{1}{i} = \frac{1}{2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\binom{1}{i} = \frac{1}{2}\binom{1+i}{1-i}$. This equals $\frac{1}{\sqrt{2}}e^{i\pi/4}\binom{e^{-i\pi/4}}{e^{i\pi/4}} = e^{i\pi/4}R_z(\pi/2)|0\rangle$ — the $|+y\rangle$ state on the Bloch sphere equator at $\phi = \pi/2$.
4. $\text{CNOT}^2|c,t\rangle = \text{CNOT}|c,t\oplus c\rangle = |c,(t\oplus c)\oplus c\rangle = |c,t\oplus(c\oplus c)\rangle = |c,t\oplus 0\rangle = |c,t\rangle$ since $c\oplus c = 0$ for any bit $c$. So $\text{CNOT}^2 = I$. ✓
5. $|\Psi^-\rangle = \frac{1}{\sqrt{2}}(|01\rangle-|10\rangle)$. Circuit: Apply $X$ to qubit 1 (giving $|10\rangle$), then $H\otimes I$ (giving $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)|0\rangle$), then $\text{CNOT}_{1\to2}$ (giving $\frac{1}{\sqrt{2}}(|00\rangle-|11\rangle) = |\Phi^-\rangle$). Alternatively: $H\otimes I|00\rangle \to |\Phi^+\rangle$, then $I\otimes X \to |\Psi^+\rangle$, then $I\otimes Z \to |\Psi^-\rangle$. (One additional single-qubit gate suffices.)
6. $Z|+\rangle = |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Then $H|-\rangle = H\cdot\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) = \frac{1}{\sqrt{2}}(H|0\rangle - H|1\rangle) = \frac{1}{\sqrt{2}}(|+\rangle - |-\rangle) = \frac{1}{\sqrt{2}}\cdot\frac{1}{\sqrt{2}}[(|0\rangle+|1\rangle)-(|0\rangle-|1\rangle)] = |1\rangle$. The $H$-gate converts phase differences into amplitude differences: the $-$ between $|0\rangle$ and $|1\rangle$ in $|-\rangle$ becomes destructive interference for $|0\rangle$ and constructive interference for $|1\rangle$, yielding $|1\rangle$ with certainty. This is quantum interference in action.
7. The Clifford group maps Pauli operators to Pauli operators under conjugation: $CPС^\dagger \in \mathcal{P}_n$ for $P \in \mathcal{P}_n$. The Gottesman-Knill theorem: any Clifford circuit on a computational basis input can be simulated classically in $O(n^2)$ time by tracking the stabilizer generators (Pauli operators that stabilize the state). Adding $T$: $THT^\dagger \notin \mathcal{P}_1$, so $T$ exits the Clifford group and enables states with $T$-count $\geq 1$ that cannot be stabilizer states — these require $2^n$ amplitudes to represent classically.
8. Optimal iterations: $k = \lfloor\frac{\pi}{4}\sqrt{N}\rfloor = \lfloor\frac{\pi}{4}\cdot 4\rfloor = \lfloor\pi\rfloor = 3$. Success probability after $k$ iterations: $P = \sin^2((2k+1)\arcsin(1/\sqrt{N})) = \sin^2(7\arcsin(1/4))$. $\arcsin(0.25) \approx 0.2527$ rad, so $7\times0.2527 = 1.769$ rad, $\sin^2(1.769) = \sin^2(\pi - 1.769) = \sin^2(1.373) \approx 0.978$. Success probability $\approx 97.8\%$.
9. $R_z(\pi/2)R_x(\pi)R_z(-\pi/2)$. $R_z(\pm\pi/2) = \begin{pmatrix}e^{\mp i\pi/4}&0\\0&e^{\pm i\pi/4}\end{pmatrix}$. $R_x(\pi) = -iX$. Product: $R_z(\pi/2)(-iX)R_z(-\pi/2) = -i\begin{pmatrix}e^{-i\pi/4}&0\\0&e^{i\pi/4}\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}e^{i\pi/4}&0\\0&e^{-i\pi/4}\end{pmatrix} = -i\begin{pmatrix}0&e^{-i\pi/2}\\e^{i\pi/2}&0\end{pmatrix} = -i\begin{pmatrix}0&-i\\i&0\end{pmatrix} = \begin{pmatrix}0&-1\\1&0\end{pmatrix}$... accounting for global phase gives $Y = \begin{pmatrix}0&-i\\i&0\end{pmatrix}$ up to global phase convention. ✓
10. $\mathcal{F} = (1-\epsilon)^{100} \approx e^{-100\epsilon} = e^{-0.1} \approx 0.905$. Total fidelity $\approx 90.5\%$ — about $9.5\%$ error probability in the full circuit. This illustrates the severe challenge of deep quantum circuits without error correction.
11. Superconducting: $T_2/t_{\text{gate}} = 100\,\mu\text{s}/100\,\text{ns} = 1000$ gates within $T_2$. Trapped ion: $T_2/t_{\text{gate}} = 1\,\text{s}/1\,\text{ms} = 1000$ gates within $T_2$. Despite the vast difference in raw coherence time, both platforms execute $\sim 1000$ two-qubit gates within $T_2$ — superconducting wins on speed, ions win on connectivity and individual qubit fidelity.
12. QFT on $n$ qubits requires $O(n^2)$ gates — a polynomial number in the number of qubits $n$. Classical FFT on $N = 2^n$ elements requires $O(N\log N) = O(n\cdot 2^n)$ operations — exponential in $n$. The QFT achieves this because the $2^n$ Fourier amplitudes are encoded implicitly in the quantum state $|\tilde{\psi}\rangle = \sum_k \hat{c}_k|k\rangle$, requiring only $n$ qubits to store, and the circuit exploits quantum parallelism to compute all $2^n$ overlaps simultaneously. The catch: only $O(1)$ or $O(\text{poly}(n))$ amplitudes can be readout — the speedup is only useful when combined with algorithms (like phase estimation) that extract the relevant information efficiently.