Introduction
Quantum computing begins with a simple mathematical question:
What changes if information is represented not by points in a finite set, but by vectors in a complex Hilbert space, and if the allowed transformations are constrained by the structure of quantum mechanics?
This question is not only a question about physics. It is also a question about linear algebra, probability, operator theory, group representations, Fourier analysis, computational complexity, coding theory, and algorithm design. For a mathematician, quantum computation is one of the clearest places where abstract structure becomes computational power.
The subject did not arise merely from trying to make faster hardware. One of its original motivations was the observation that quantum systems themselves appear difficult to simulate efficiently on ordinary classical computers. Feynman argued that a computing device governed by quantum mechanics might naturally simulate quantum systems more efficiently than a classical machine could (Feynman, 1982). Deutsch then formulated the idea of a universal quantum computer within a computational model, placing quantum theory beside the Church–Turing viewpoint on computation (Deutsch, 1985). Later, Shor’s polynomial-time quantum algorithms for integer factoring and discrete logarithms gave a striking indication that quantum computation could change the landscape of algorithmic number theory and cryptography (Shor, 1994). Grover’s search algorithm showed a different kind of advantage: a quadratic improvement for unstructured search, together with a clean geometric mechanism based on amplitude amplification (Grover, 1996).
This book develops quantum computing as a rigorous mathematical theory. It assumes that the reader is comfortable with graduate-level mathematical reasoning, but it does not assume prior knowledge of quantum mechanics. We will build the needed quantum formalism from finite-dimensional Hilbert spaces upward, because finite-dimensional quantum theory is the natural mathematical language of the circuit model of quantum computation.
Computation as structured transformation
At its most basic level, a computation is a controlled transformation of information.
In classical deterministic computation, information is often modeled as a finite string of bits. A bit is an element of the two-point set
\[ \{0,1\}. \]
A classical Boolean function on \(n\) bits is a map
\[ f:\{0,1\}^n \to \{0,1\}^m. \]
For example, the AND function is the map
\[ \operatorname{AND}:\{0,1\}^2 \to \{0,1\}, \qquad \operatorname{AND}(x,y)=xy. \]
This is a perfectly good mathematical model of input-output behavior. But if we ask how a computation is physically implemented, we must also ask which transformations are reversible, which transformations discard information, and how uncertainty enters.
Quantum computation changes the mathematical representation of information. A qubit is not an element of \(\{0,1\}\). In the standard model, a pure state of one qubit is a unit vector in the complex vector space \(\mathbb{C}^2\), considered up to multiplication by a complex scalar of modulus one. Thus a state may be written as
\[ \alpha |0\rangle + \beta |1\rangle, \qquad \alpha,\beta\in\mathbb{C}, \qquad |\alpha|^2+|\beta|^2=1. \]
Here \(|0\rangle\) and \(|1\rangle\) denote a fixed orthonormal basis of \(\mathbb{C}^2\). The notation \(|\psi\rangle\), called ket notation, is Dirac’s notation for vectors used throughout quantum theory. In this book it is only notation: \(|\psi\rangle\) is a vector, and \(\langle \psi|\) will denote the corresponding conjugate-linear functional.
The coefficients \(\alpha\) and \(\beta\) are called amplitudes. They are not probabilities. The probabilities arise only after applying the Born rule: if the state
\[ |\psi\rangle=\alpha |0\rangle+\beta |1\rangle \]
is measured in the standard basis, the outcome \(0\) occurs with probability \(|\alpha|^2\), and the outcome \(1\) occurs with probability \(|\beta|^2\). For example, the state
\[ \frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle \]
gives outcomes \(0\) and \(1\) with equal probability when measured in the standard basis. But the state is not merely “a random bit.” Before measurement, it is a vector that can interfere with other vectors under later unitary transformations.
This distinction is central. Quantum computation is not classical randomized computation with unusual notation. It is computation in which complex amplitudes evolve linearly and can interfere constructively or destructively.
Why Hilbert spaces enter
A Hilbert space is an inner product space that is complete with respect to the norm induced by its inner product. In this book, almost all Hilbert spaces are finite-dimensional, so completeness causes no technical difficulty: every finite-dimensional inner product space over \(\mathbb{C}\) is complete. The main structure we need is the complex inner product
\[ \langle \cdot,\cdot\rangle, \]
which allows us to speak of lengths, angles, orthogonality, projections, adjoints, and unitary transformations.
For quantum computation, the state space of \(n\) qubits is
\[ (\mathbb{C}^2)^{\otimes n}, \]
the \(n\)-fold tensor product of \(\mathbb{C}^2\) with itself. This space has dimension \(2^n\), with standard basis vectors
\[ |x\rangle \quad \text{for} \quad x\in\{0,1\}^n. \]
For example, two qubits live in
\[ \mathbb{C}^2\otimes \mathbb{C}^2 \cong \mathbb{C}^4, \]
with standard basis
\[ |00\rangle,\ |01\rangle,\ |10\rangle,\ |11\rangle. \]
A general pure two-qubit state has the form
\[ \alpha_{00}|00\rangle+\alpha_{01}|01\rangle +\alpha_{10}|10\rangle+\alpha_{11}|11\rangle, \]
where
\[ |\alpha_{00}|^2+|\alpha_{01}|^2 +|\alpha_{10}|^2+|\alpha_{11}|^2=1. \]
The tensor product is not a decorative operation. It is the mathematical operation that expresses composition of quantum systems. It also permits entanglement, meaning that a joint state may fail to factor as a tensor product of states of its parts. For instance,
\[ \frac{1}{\sqrt{2}}(|00\rangle+|11\rangle) \]
is not of the form
\[ |\phi\rangle\otimes|\chi\rangle \]
for one-qubit states \(|\phi\rangle\) and \(|\chi\rangle\). Entanglement will later become one of the structural resources of quantum information theory, but it should not be treated as a slogan that explains every quantum speedup. Algorithms also depend on interference, representation structure, measurement design, and the computational problem being solved.
Dynamics: unitary maps before measurement
In the closed-system circuit model, evolution before measurement is represented by a unitary operator. A linear operator
\[ U:H\to H \]
on a complex Hilbert space is unitary if
\[ U^*U=UU^*=I, \]
where \(U^*\) is the adjoint of \(U\), and \(I\) is the identity operator. Equivalently, \(U\) preserves inner products:
\[ \langle Uv,Uw\rangle=\langle v,w\rangle \]
for all \(v,w\in H\).
This condition implies norm preservation. If \(|\psi\rangle\) is a unit vector, then \(U|\psi\rangle\) is again a unit vector. This is why unitary maps are the natural transformations for pure quantum states in an isolated system.
A simple example is the one-qubit Hadamard gate,
\[ H=\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}. \]
It acts on the standard basis by
\[ H|0\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}}, \qquad H|1\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}}. \]
Applying \(H\) twice gives the identity:
\[ H^2=I. \]
This small matrix already shows the role of interference. If we start with \(|0\rangle\), apply \(H\), and then apply \(H\) again, the final state is exactly \(|0\rangle\). The intermediate state has equal measurement probabilities for \(0\) and \(1\), but the second unitary transformation recombines amplitudes so that the \(|1\rangle\) amplitude cancels.
This cancellation is not a metaphor. It is ordinary linear algebra over \(\mathbb{C}\).
Reversibility and classical computation inside quantum computation
Unitary transformations are invertible. Therefore, a quantum circuit cannot directly implement an arbitrary irreversible classical function
\[ f:\{0,1\}^n\to\{0,1\}^m \]
as a map \(|x\rangle\mapsto |f(x)\rangle\) unless that map is injective and dimensionally compatible. This is why reversible computation is foundational for quantum circuits.
A common reversible way to implement a classical function is
\[ U_f:|x\rangle|y\rangle\mapsto |x\rangle|y\oplus f(x)\rangle, \]
where \(\oplus\) denotes bitwise addition modulo \(2\). The input \(x\) is retained, and the value \(f(x)\) is written into a target register by reversible addition. If \(f(x)\) is a single bit and \(y\in\{0,1\}\), then
\[ |x\rangle|y\rangle\mapsto |x\rangle|y\oplus f(x)\rangle. \]
This map is reversible because applying it twice returns the original pair:
\[ y\oplus f(x)\oplus f(x)=y. \]
Thus ordinary classical functions can be embedded coherently into quantum computation, provided we keep enough information to make the transformation reversible. Later chapters will use this idea repeatedly, especially in phase estimation, Shor’s algorithm, and amplitude amplification.
Measurement: probability from geometry
Quantum computation ends, and sometimes proceeds, by measurement. Measurement is the operation that converts quantum information into classical data.
In the simplest case, measuring a state in an orthonormal basis
\[ \{|e_1\rangle,\dots,|e_d\rangle\} \]
produces outcome \(j\) with probability
\[ |\langle e_j|\psi\rangle|^2. \]
For example, if
\[ |\psi\rangle = \frac{1}{2}|0\rangle+\frac{\sqrt{3}}{2}|1\rangle, \]
then measurement in the standard basis gives
\[ \Pr(0)=\left|\frac{1}{2}\right|^2=\frac14, \qquad \Pr(1)=\left|\frac{\sqrt{3}}{2}\right|^2=\frac34. \]
The probabilities sum to one because \(|\psi\rangle\) has norm one.
Measurement is not merely passive observation in the mathematical model. After a projective measurement, the state is updated according to the observed outcome. If the standard-basis measurement above yields outcome \(1\), the post-measurement state becomes \(|1\rangle\). This update rule matters because later operations act on the post-measurement state, not on the pre-measurement superposition.
More general measurements will be introduced later using positive operator-valued measures and quantum operations. For now, the essential point is that quantum computation combines deterministic linear evolution of amplitudes with probabilistic extraction of classical outcomes.
What makes quantum algorithms different?
Quantum algorithms are not faster simply because a state of \(n\) qubits has \(2^n\) complex amplitudes. That statement is true as a dimension count, but by itself it does not imply computational advantage. A generic vector in a \(2^n\)-dimensional space cannot be read out completely from a single measurement, and preparing or manipulating arbitrary states may itself require exponential resources.
The power of a quantum algorithm comes from a more delicate arrangement:
- encode the problem into a quantum state or unitary operation;
- transform amplitudes so that wrong answers interfere destructively;
- make correct or useful information appear with sufficiently high probability after measurement;
- do all of this using a number of elementary operations bounded by a useful complexity estimate.
Shor’s factoring algorithm is a central example. It reduces factoring to order finding, expresses order finding through periodic structure, and uses the quantum Fourier transform and phase estimation to extract that structure efficiently (Shor, 1994). Grover’s algorithm is different: it works in an essentially two-dimensional invariant subspace and rotates amplitude toward the marked subspace, giving a quadratic improvement in query complexity for unstructured search (Grover, 1996).
These examples already show that there is no single mechanism behind every quantum speedup. Some algorithms exploit Fourier analysis over groups. Some use amplitude amplification. Some use Hamiltonian simulation, quantum walks, block encodings, or singular value transformation. Some proposed speedups depend strongly on how input data are made available. A serious mathematical treatment must always ask: What is the input model? What is the cost measure? What error probability is allowed? What is being compared?
Complexity: what counts as efficient?
To speak carefully about computational advantage, we need complexity theory. A problem is usually called efficiently solvable if it can be solved with resources bounded by a polynomial in the input size. In classical complexity theory, the class \(\mathrm{P}\) consists of decision problems solvable by deterministic polynomial-time algorithms, while \(\mathrm{BPP}\) consists of decision problems solvable by randomized polynomial-time algorithms with bounded error.
The quantum analogue is \(\mathrm{BQP}\), bounded-error quantum polynomial time. Informally, a decision problem lies in \(\mathrm{BQP}\) if a uniform family of polynomial-size quantum circuits decides it with error probability bounded away from \(1/2\). Bernstein and Vazirani developed foundational aspects of quantum complexity theory and formalized quantum Turing machine models that are polynomially equivalent to circuit-based formulations in the usual setting (Bernstein and Vazirani, 1997).
Bounded error is important. It does not mean that the algorithm is unreliable in practice. If the success probability is at least \(2/3\), independent repetition and majority vote can usually reduce the error probability exponentially, assuming the relevant algorithmic conditions allow repetition. This is similar in spirit to classical randomized computation.
Complexity theory also teaches caution. We do not know how to prove, unconditionally, that \(\mathrm{BQP}\) contains problems outside \(\mathrm{P}\). We have strong evidence, oracle separations, and algorithms that outperform the best known classical methods for important problems, but many separation questions remain open. This book will distinguish carefully between theorem, evidence, and expectation.
Noise and the need for error correction
Real quantum systems are not isolated perfectly. They interact with their environments, gates are imperfect, and measurements have errors. Mathematically, such noise is described not only by unitary operators on the computational system but also by more general maps on density operators, called quantum channels.
Quantum error correction is therefore not an optional engineering detail. It is a mathematical condition for scalable quantum computation. Classical error correction protects bits by redundancy, but quantum error correction must handle additional constraints: unknown quantum states cannot be copied arbitrarily, and errors may be continuous rather than merely bit flips. The no-cloning theorem and the linear structure of quantum states force a different design.
The remarkable fact is that quantum error correction is possible. The Knill–Laflamme conditions characterize when a subspace can correct a specified set of errors, giving a precise algebraic criterion for quantum codes (Knill and Laflamme, 1997). Later chapters will develop stabilizer codes, syndrome measurements, CSS codes, logical operators, and fault-tolerant computation from this foundation.
As a first hint, a quantum code does not learn the encoded quantum state. Instead, it learns an error syndrome: classical information about which error occurred, without measuring the protected logical information itself. This is one of the most beautiful mathematical ideas in the subject. It combines subspace geometry, operator algebras, and information-theoretic constraints.
The path of this book
The book begins with the mathematical shape of quantum computation, then develops the linear algebra needed to treat the subject rigorously. We will study finite-dimensional Hilbert spaces, tensor products, qubits, observables, measurement, density operators, partial trace, and quantum channels. These are not formalities; they are the grammar of the field.
After that foundation, we turn to circuits. We will see how reversible classical computation embeds into quantum computation, how elementary gates generate larger transformations, and what it means for a gate set to be universal. We will distinguish exact universality from approximate universality, because practical computation depends on approximation with controlled error.
The middle part of the book develops major algorithms. The quantum Fourier transform and phase estimation lead to Shor’s algorithm and the hidden subgroup perspective. Amplitude amplification leads to Grover search and its optimality properties. Later algorithmic paradigms—Hamiltonian simulation, quantum walks, linear systems algorithms, block encodings, singular value transformation, and variational methods—will be treated with attention to assumptions and input models.
The final part of the book studies complexity, information measures, error correction, stabilizer methods, fault tolerance, Hamiltonian models, adiabatic computation, and measurement-based computation. The goal is not only to teach standard results, but also to prepare you to read research papers critically: to identify what is proved, what is conjectured, what depends on an oracle or promise, and what depends on physical assumptions.
A mathematician’s attitude toward quantum computing
The right attitude is neither mysticism nor dismissal.
Quantum computing is not magic. Its basic formalism is finite-dimensional linear algebra, probability, and tensor products. At the same time, it is not merely classical computing in unfamiliar notation. The combination of complex amplitudes, unitary dynamics, entanglement, measurement, and computational complexity produces phenomena that have no direct classical counterpart.
A mathematician should ask precise questions:
- What is the state space?
- Which maps are allowed?
- What is measured, and in which basis or measurement model?
- What probability distribution is produced?
- What is the cost of implementing the required transformation?
- What error is tolerated?
- What theorem justifies the claimed advantage?
- What assumptions enter the comparison with classical computation?
These questions will guide the entire book.
If you read with this discipline, quantum computing becomes a coherent mathematical subject. Its objects are vectors, operators, tensor products, groups, circuits, codes, channels, and complexity classes. Its results are theorems about what can be transformed, estimated, protected, simulated, or verified under precise rules. Its open problems sit at the boundary of mathematics, physics, and computer science.
We now begin with the mathematical shape of quantum computation.
References
Bernstein, E., and Vazirani, U. (1997). “Quantum Complexity Theory.” SIAM Journal on Computing, 26(5), 1411–1473. https://doi.org/10.1137/S0097539796300921
Deutsch, D. (1985). “Quantum Theory, the Church–Turing Principle and the Universal Quantum Computer.” Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, 400(1818), 97–117. https://doi.org/10.1098/rspa.1985.0070
Feynman, R. P. (1982). “Simulating Physics with Computers.” International Journal of Theoretical Physics, 21, 467–488. https://doi.org/10.1007/BF02650179
Grover, L. K. (1996). “A Fast Quantum Mechanical Algorithm for Database Search.” In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 212–219. https://doi.org/10.1145/237814.237866
Knill, E., and Laflamme, R. (1997). “Theory of Quantum Error-Correcting Codes.” Physical Review A, 55(2), 900–911. https://doi.org/10.1103/PhysRevA.55.900
Shor, P. W. (1994). “Algorithms for Quantum Computation: Discrete Logarithms and Factoring.” In Proceedings 35th Annual Symposium on Foundations of Computer Science, 124–134. https://doi.org/10.1109/SFCS.1994.365700