Quantum Computing: Lecture Notes

Ronald de Wolf

Source-linked AI summary

Quantum Computing: Lecture Notes

Ronald de Wolf

arXiv:1907.09415v6Jul 19, 2019quant-phcs.CCcs.DScs.ET

TL;DR

These lecture notes introduce quantum computation and information from a theoretical computer science perspective, covering quantum mechanics, algorithms, complexity, distributed settings, and newer topics. They explain quantum advantages through foundational constructions and algorithms, including Bernstein–Vazirani’s one-query versus n-query contrast and Shor’s reduction from factoring to period-finding. The notes also emphasize that scaling physical quantum computers remains an enormous task despite theoretical advances in error correction and fault tolerance.

Problem
The notes address how quantum-mechanical principles can provide computational capabilities beyond classical computers, including significant speedups and tasks impossible for classical computers.
Source: §1.1 · p. 14
Method
The notes present quantum states, measurements, and unitary operations before developing quantum algorithms, complexity, communication, machine learning, stabilizer circuits, and error correction.
Source: §1.1 · p. 13, §1.2 · p. 15, §1.2.1 · p. 15
Results
Bernstein–Vazirani solves its problem with 1 query and O(n) other operations, whereas classical algorithms require n queries; Shor’s approach reduces factoring to efficient period-finding.
Source: §2.4.2 · p. 31, §5.2 · p. 49
Takeaways & Limitations
The notes provide a theoretical computer science introduction to quantum computation while showing concrete algorithmic advantages and foundational limits of quantum information.
Source: §1.1 · p. 14, §15.2 · p. 141
Scaling fault-tolerant quantum computation from small experiments to thousands or millions of qubits remains an enormous task.
Source: §1.1 · p. 14

Abstract

from arXiv · show

This is a set of lecture notes suitable for a Master's course on quantum computation and information from the perspective of theoretical computer science. The first version was written in 2011, with many extensions and improvements in subsequent years. The first 10 chapters cover the circuit model and the main quantum algorithms (Deutsch-Jozsa, Simon, Shor, Hidden Subgroup Problem, Grover, quantum walks, Hamiltonian simulation and HHL). They are followed by 4 chapters about complexity, 4 chapters about distributed ("Alice and Bob") settings, a chapter about quantum machine learning, one about stabilizer states and Clifford circuits, and a final chapter about quantum error correction. Appendices A and B give a brief introduction to the required linear algebra and some other mathematical and computer science background. All chapters come with exercises, with some hints provided in Appendix C.

Preface from 2011

The notes originated as a 2011 University of Amsterdam quantum computing course and were organized around algorithms, complexity, distributed settings, and error correction.

Course structure

The 2011 course covered quantum algorithms in Chapters 1–7, quantum complexity in Chapters 8–9, Alice-and-Bob topics in Chapters 10–13, and error correction in Chapter 14.Each chapter was designed for a 2 × 45-minute lecture, with an additional 45-minute exercise and homework lecture.Source: Preface from 2011 · p. 3

Scope

The text was intended as a general introduction to quantum computation and information from a theoretical computer science perspective.The author aimed for a self-contained and consistent presentation while acknowledging that it remained rough in places.Source: Preface from 2011 · p. 3

Attribution, acknowledgments, subsequent updates

The notes combine material adapted from earlier thesis and survey work with substantial new chapters, and were repeatedly expanded through corrections, exercises, and new topics.

Attribution

Chapters 1–6 draw mainly from the author’s PhD thesis, while Chapters 7–9 and 13–14 were newly written or largely new.The additions include Simon’s lower bound, the Fourier transform, Grover’s geometric explanation, Hamiltonian simulation, HHL, and error correction-related material.Source: Attribution, acknowledgments,… · p. 3
Material from quantum proofs and non-locality surveys was substantially revised for Chapters 8, 10, 11, and 12.The source surveys include Drucker [105] and work with Buhrman, Cleve, and Massar [76].Source: Attribution, acknowledgments,… · p. 3

Acknowledgments

The author credits teaching assistants, collaborators, students, and other readers for comments that shaped the notes and exercises.Source: Attribution, acknowledgments,… · pp. 3–5

Subsequent updates

The notes received successive corrections, clarifications, and exercise additions from 2013 through 2022, including new chapters on the Hidden Subgroup Problem, Hamiltonian simulation, HHL, QMA, and quantum machine learning.The 2018, 2019, 2021, and 2022 updates specifically identify these additions.Source: Attribution, acknowledgments,… · pp. 3–4
The 2023 update added a chapter on the generalized adversary bound, while the 2026 update added stabilizer states and acknowledged extensive proofreading and feedback.Source: Attribution, acknowledgments,… · pp. 4–5

Quantum Computing

This section introduces quantum computation through the foundations of quantum states, measurements, unitary evolution, qubit registers, and elementary gates, highlighting superposition, entanglement, and interference. It also covers teleportation and the potential computational capabilities and implementation challenges of quantum systems.

1.1 Introduction

Quantum effects may enable enormous speedups, including exponential improvements for some computations, while quantum algorithms threaten classical cryptography and quantum cryptography can remain secure under idealizing assumptions.The field combines quantum mechanics with computer science and seeks algorithms significantly faster than classical alternatives.Source: §1.1 · p. 13
Large-scale quantum computing remains difficult because noise and decoherence require fault-tolerant error correction, whose scaling from small experiments to thousands or millions of qubits is formidable.Quantum communication applications such as teleportation and commercially available versions of BB84 have nevertheless been implemented with some success.Source: §1.1 · p. 14

1.2 Quantum mechanics

A pure quantum state is a normalized vector of amplitudes in a Hilbert space, representing a superposition of mutually exclusive classical basis states that can be combined through tensor products.The notes use Dirac notation, with basis states written as kets and conjugate-transposed vectors as bras.Source: §1.2 · p. 15, §1.2.1 · p. 15

Measurement in the computational basis

Computational-basis measurement returns one classical state with probability |αj|2 under Born’s rule and collapses the superposition to that state, discarding amplitude information.Multiplying a state by a global phase eiθ does not change measurement probabilities.Source: Measurement in the computational basis · p. 16

Projective measurement

Projective measurements use orthogonal projectors summing to identity, producing outcome j with probability ⟨ϕ|Pj|ϕ⟩ and a normalized post-measurement projection.Measurements in arbitrary orthonormal bases are included, and outcomes are certain when the state lies entirely in one projector’s subspace.Source: A projective measurement · pp. 16–17

Observables

Observables encode projective measurements as Hermitian matrices, with outcome expectations given by Tr(M|ϕ⟩⟨ϕ|); separate and joint measurements on bipartite systems can produce different post-measurement states.The Pauli matrices are examples, and a Bell-like state remains unchanged under the joint observable Z ⊗Z while separate Z measurements collapse it.Source: Observables · p. 17

POVM measurement

POVMs generalize projective measurements using positive semidefinite elements summing to identity and can unambiguously distinguish |0⟩ from |+⟩ with success probability 1/4 and an inconclusive outcome otherwise.For |0⟩, the correct outcome occurs with probability 1/4 and the inconclusive outcome with probability 3/4; the same probabilities hold symmetrically for |+⟩.Source: POVM measurement · p. 18

1.2.3 Unitary evolution

Closed-system quantum evolution is unitary: it preserves vector norms, is reversible through U−1 = U∗, and contrasts with irreversible measurement.An n-qubit register has 2n orthogonal computational-basis states, while a single qubit is a superposition in C2.Source: §1.2.3 · pp. 18–19, §1.3 · p. 19

1.3 Qubits and quantum memory

Quantum states can be entangled rather than tensor products, and complex or negative amplitudes enable interference beyond classical probability distributions.Measuring one qubit of an EPR-pair can fix the other, even when separated; amplitudes become probabilities only after squaring.Source: §1.3 · p. 20

1.4 Elementary gates

Elementary gates include bit-flips, phase-flips, phase rotations, Hadamard transforms, and controlled operations such as CNOT.Hadamard interference can cancel amplitudes, while CNOT negates its target exactly when the control qubit is 1.Source: §1.4 · p. 21

1.5 Example: quantum teleportation

Teleportation transfers an unknown qubit using a shared EPR-pair, Alice’s two-bit measurement result, and Bob’s conditional X- and Z-gates.Alice applies CNOT and Hadamard, measures two qubits, and sends ab; Bob’s corrections recover the original state and preserve its entanglement.Source: §1.5 · pp. 22–23
Teleportation destroys Alice’s original qubit rather than copying it, because copying an unknown qubit is impossible.The protocol moves the state to Bob instead of creating an additional copy.Source: §1.5 · p. 23

Exercises

The exercises reinforce quantum mechanics, gates, measurements, entanglement, communication protocols, and foundational limits through calculations, proofs, and protocol design.

Linear algebra and measurement

Exercises ask students to compute tensor products, Hadamard transforms, inner products, traces, and measurement observables.Source: Exercises · pp. 23–24

Quantum gates

Several exercises establish gate identities, including HXH = Z, Hadamard-conjugated CNOT behavior, and HR_θH = R_-θ.Source: Exercises · p. 23

Entanglement

The exercises develop entanglement through proving that EPR pairs cannot factor into separate qubits and analyzing their transformations.Source: Exercises · pp. 23–24

Measurements

Students analyze POVMs, including their validity, success probability, and the relation between general measurements and projective measurements.Source: Exercises · p. 24

Foundations

Foundational exercises address no-cloning, no-deleting, parity measurements, and information limits linked to Holevo’s theorem and superdense coding.Source: Exercises · pp. 23–24

Quantum communication

Communication exercises cover superdense coding, teleportation-like protocols, and the distinction between moving and copying an unknown qubit.Superdense coding uses one EPR pair and one transmitted qubit to communicate two classical bits, while the cited teleportation discussion emphasizes that the original qubit is destroyed.Source: Exercises · p. 24

The Circuit Model and the Deutsch-Jozsa Algorithm

This section introduces the quantum circuit model as unitary gate arrays with classical measurement outputs and develops oracle-based algorithms including Deutsch-Jozsa and Bernstein-Vazirani. It also examines exercises on query conversions, workspace effects and entanglement, randomized strategies, structured promises, and parity queries.

2.1 Quantum computation

The circuit model is polynomially equivalent to the quantum Turing-machine model under uniformity, and is emphasized here because it is more popular among researchers.Classical uniformly polynomial circuit families likewise characterize P, while randomized counterparts characterize BPP.Source: §2.1 · p. 25, §2.1.1 · pp. 25–26

2.1.1 Classical circuits

Classical circuits compute Boolean functions through finite directed acyclic graphs of gates, with uniformly polynomial families equivalent in power to polynomial-time deterministic Turing machines.Uniformity requires a logarithmic-space deterministic machine to output the circuit for each input size.Source: §2.1.1 · p. 25

2.1.2 Quantum circuits

A quantum circuit composes small-qubit unitary gates into a reversible evolution, producing a generally superposed final state that is measured in the computational basis for classical output.The circuit model uses gates on usually one, two, or three qubits; Toffoli gates are complete for classical reversible computation, and intermediate measurements can generally be deferred.Source: §2.1.2 · pp. 26–27

2.2 Universality of various sets of elementary gates

Universal quantum computation can use CNOT with arbitrary one-qubit gates, while the finite set {CNOT, H, T} approximates any one- or two-qubit unitary efficiently.Solovay-Kitaev gives polylog(1/ε) gate cost for error ε; Hadamard and Toffoli suffice for approximating real-entry unitaries.Source: §2.2 · p. 28

2.3 Quantum parallelism

Quantum parallelism evaluates f on all 2^n inputs within one superposition, but interference and entanglement are needed to obtain advantages beyond classical randomization.A reversible Toffoli circuit implements |z⟩|0⟩→|z⟩|f(z)⟩, while measurement reveals only one input-output pair.Source: §2.3 · pp. 28–29

2.4 The early algorithms

The early-algorithm framework treats inputs as black-box oracles, so its exponential quantum-classical query separations do not directly establish separations in the standard circuit model.For N=2^n, an oracle acts on an n-bit address and target qubit, supports superposed queries, and can encode input bits into phases.Source: §2.4 · pp. 29–30

2.4.1 Deutsch-Jozsa

Deutsch-Jozsa solves the constant-versus-balanced problem with certainty using 1 quantum query and O(n) other operations, whereas deterministic classical algorithms need at least N/2 + 1 queries.The quantum result follows because the final |0^n⟩ amplitude is ±1 for constant inputs and 0 for balanced inputs; randomized classical sampling removes the separation when error is allowed.Source: §2.4.1 · p. 31

2.4.2 Bernstein-Vazirani

Bernstein-Vazirani recovers the hidden n-bit string a with 1 query and O(n) other operations, while every classical algorithm needs n queries, even with small error.The algorithm applies the same Hadamard-query-Hadamard structure as Deutsch-Jozsa, transforming the phase pattern into the basis state |a⟩.Source: §2.4.2 · p. 31
The exercises ask for circuits converting standard queries into queries on modified inputs and for implementing standard queries from controlled or uncontrolled phase-queries.The modified inputs flip or reset the first bit, while the phase-query exercises compare controlled and uncontrolled constructions.Source: §2.4.2 · pp. 32–33
Unintended entanglement between address and workspace registers can thwart intended interference, motivating cleanup of workspace qubits before superposition-based computation.The exercise asks students to analyze how ignoring workspace affects output distributions and why subroutine workspace should be restored to |0⟩.Source: §2.4.2 · p. 33
The section asks for a randomized classical algorithm using only two queries that solves Deutsch-Jozsa with success probability at least 2/3 on every input.It also asks students to modify Deutsch-Jozsa to distinguish two specified structured cases of an N-bit input.Source: §2.4.2 · p. 33
A final exercise asks for a quantum algorithm computing any fixed Boolean function f(x) with one parity-query Q_x and unrestricted elementary gates.The parity query evaluates x · y modulo 2 into an auxiliary bit, using an (N + 1)-qubit unitary.Source: §2.4.2 · p. 33

Simon’s Algorithm

Simon’s problem asks for an unknown nonzero mask s defining the collisions of a 2-to-1 function. Simon’s quantum algorithm finds s with an expected O(n) queries, while classical bounded-error algorithms require Ω(2^n) queries.

3.1 The problem

Simon’s problem is to find the unknown nonzero s such that x_i=x_j exactly when i=j or i=j⊕s.The input function is 2-to-1, with collisions determined by s.Source: §3.1 · p. 35

3.2 The quantum algorithm

Each quantum run produces a uniformly random j satisfying s·j=0 mod 2, yielding a linear equation about s.The algorithm repeats until it obtains n−1 independent equations, then uses Gaussian elimination modulo 2.Source: §3.2 · p. 36
Simon’s algorithm finds s using an expected O(n) queries and polynomially many other operations.The expected O(n) runs suffice because each new sample is linearly independent with probability at least 1/2.Source: §3.2 · p. 36

3.3.1 Upper bound

A classical randomized upper-bound algorithm uses collisions among roughly 2^(n/2) random queries to recover s.The birthday-paradox argument implies that this many queries gives a collision with high probability.Source: §3.3.1 · pp. 36–37

3.3.2 Lower bound

Any classical randomized algorithm solving Simon’s problem with high probability requires Ω(2^(n/2)) queries, making the collision-based algorithm essentially optimal.For fewer queries, the transcript is typically indistinguishable between the s=0^n and s≠0^n cases.Source: §3.3.2 · pp. 37–38

Simon’s Algorithm

Simon’s result gives the first proven exponential query separation between quantum algorithms and classical bounded-error algorithms, though not an exponential separation in ordinary circuit size.The result inspired Shor’s factoring algorithm [243].Source: §3.3.2 · p. 37

Exercises

The exercises extend Simon’s algorithm through explicit state calculations, subspace generalizations, sampling tasks, and query-complexity comparisons. They also connect the construction to verification of quantum computation and related oracle problems.

Exercises

The exercises ask readers to derive Simon’s measurement projectors and analyze the output distribution when s=0^n.They also work through a concrete n=3 instance with s=111 and determine s from two sampled equations.Source: Exercises · pp. 38–39
A subspace generalization asks students to show that one run produces a vector orthogonal to the entire hidden subspace V.The usual problem is recovered when V={0,s}.Source: Exercises · p. 39
Another exercise constructs a quantum state that supports both finding a preimage of y and sampling vectors orthogonal to the difference of its two preimages.The two tasks need not be performed sequentially on the same state because one may disturb the state needed for the other.Source: Exercises · p. 39
The associated protocol was recently used to design an efficient classical verification procedure for checking whether a quantum computer works as intended [194].This connects the exercise’s state-generation tasks to verification of quantum computation.Source: Exercises · p. 39
Additional exercises compare quantum and classical query access for phase transformations and reconstructing an unknown N-bit string.They ask for quantum algorithms using at most T or N queries and classical lower bounds for success probability above 1/2.Source: Exercises · p. 39

The Fourier Transform

The notes develop classical and quantum Fourier transforms, showing how recursive structure yields fast classical computation, efficient quantum circuits, and phase estimation.

4.2 The Fast Fourier Transform

O(N log N) steps reduce Fourier-transform computation from the naive O(N^2) method through the recursive Fast Fourier Transform.The recursion computes separate transforms of even- and odd-indexed entries and combines them.Source: §4.2 · p. 42

4.3 Application: multiplying two polynomials

O(d log d) steps multiply two degree-d polynomials by transforming their coefficient vectors, multiplying Fourier coefficients pointwise, and applying the inverse transform.The coefficient vectors are padded to a power-of-two dimension before convolution is computed.Source: §4.3 · p. 43

4.4 The quantum Fourier transform

The quantum Fourier transform treats the Fourier matrix as an n-qubit unitary and produces transformed values as amplitudes rather than explicitly written entries.For N = 2^n, the QFT can be implemented with O(n^2) elementary gates, achieving a different task from the classical FFT.Source: §4.4 · pp. 43–44

4.5 An efficient quantum circuit

O(n log n) gates approximate the n-qubit QFT by omitting sufficiently small controlled-phase rotations, while reversing the circuit implements the inverse transform.The exact construction uses at most n^2 gates and applies a Hadamard followed by controlled rotations to each qubit, with final swaps correcting order.Source: §4.5 · pp. 44–45

4.6 Application: phase estimation

Phase estimation applies controlled powers of U, an inverse QFT, and measurement to estimate the phase ϕ of a known eigenstate’s eigenvalue.The controlled-U stage uses 2^n − 1 applications of U before inverse Fourier processing.Source: §4.6 · p. 46
With n-bit precision, phase estimation returns an exact phase with probability 1 when ϕ has n-bit representation and otherwise achieves additive error O(2^-n) with high probability.Estimating within ±ε uses n = ⌈log(1/ε)⌉ bits and O(1/ε) applications of U.Source: §4.6 · p. 46

Exercises

The exercises reinforce Fourier analysis, approximation, operator norms, convolution, and the QFT’s role in quantum circuits.

Fourier and convolution

The exercises ask students to prove that Fourier coefficients convert convolution into pointwise multiplication and to identify Fourier transforms of periodic vectors.They also connect convolution identities to coefficient formulas and periodicity structure.Source: Exercises · pp. 47–48

Distances and approximation

The exercises define total variation distance and operator norm, then relate circuit-operator error to closeness of final output distributions.Small operator-norm error keeps all output states close and therefore keeps measurement distributions close in total variation distance.Source: Exercises · p. 47

QFT approximation

Several exercises analyze how omitting phase gates changes a circuit and ask for an O(n log n)-gate circuit within distance 1/n of the Fourier transform.Other questions examine distances between identity and controlled phase gates.Source: Exercises · p. 47

Fourier-transform structure

The exercises study powers and eigenvalues of the Fourier transform, including the action of F_N^2 on computational basis states and the consequence of F_N^4 = I.These problems use the transform’s algebraic structure to characterize its spectrum.Source: Exercises · p. 48

Shor’s Factoring Algorithm

Shor’s algorithm reduces factoring to period-finding, solves the period problem with a quantum Fourier-transform procedure, and uses continued fractions to recover the period.

5.2 Reduction from factoring to period-finding

Factoring reduces efficiently to finding the period r of modular exponentiation, after which gcd(x^(r/2) ± 1, N) yields nontrivial factors under the stated conditions.For odd, non-prime-power N, the favorable even-period case occurs with probability at least 1/2.Source: §5.2 · pp. 49–50
O(log log N) evaluations of f and O(log log N) quantum Fourier transforms solve the period-finding problem, whereas classical bounded-error algorithms require Ω(N^(1/3)/√log N) evaluations in the stated comparison.The classical approach is inefficient because the period may be exponentially large in the input length log N.Source: §5.2 · p. 50
O((log N)^2(log log N)^2 log log log N) expected gates let Shor’s algorithm find a factor, using modular exponentiation and an O((log N)^2)-gate QFT.The modular-exponentiation implementation contributes the additional logarithmic factors.Source: §5.2 · pp. 50–51

5.3 Shor’s period-finding algorithm

Shor’s period-finding circuit creates a uniform superposition, evaluates f in quantum parallel, measures the second register, and applies a second QFT to the resulting periodic superposition.The post-measurement first register contains values separated by the unknown period r.Source: §5.3 · pp. 51–52
When r divides q, measurement returns b = cq/r, and repeated runs recover r by reducing b/q once c and r are coprime.An expected O(log log N) repetitions suffice, and candidate factors can be checked efficiently by division.Source: §5.3 · p. 52
When r does not divide q, measurement yields b within 1/2 of cq/r with probability at least 4/π^2, and continued fractions recover c/r from b/q.The denominator bound ensures c/r is the unique sufficiently close fraction with denominator at most N.Source: §5.3 · p. 53

5.4 Continued fractions

Continued-fraction convergents provide rapidly improving rational approximations, with denominators growing at least exponentially and each convergent best among fractions with bounded denominator.The recurrence defines numerator and denominator sequences for the convergents.Source: §5.4 · pp. 53–54

Exercises

These exercises develop RSA encryption and modular exponentiation, then apply Shor’s algorithm to find the period of a modular function.

Modular exponentiation

Repeated squaring computes x^(2^k) mod N for k = 0,...,n−1 in O(n^2 log(n) log log(n)) steps and supports computing x^a mod N within the same bound.Source: Exercises · p. 54

Shor’s algorithm

For f(a) = 7^a mod 10, the exercises ask students to determine its period and instantiate Shor’s period-finding algorithm with a Fourier transform over q = 128.Source: Exercises · p. 54

RSA encryption

Factoring N would let an adversary efficiently decrypt RSA ciphertexts, motivating the assumption that factoring large numbers is difficult.Source: Exercises · pp. 54–55
RSA uses public-key encryption C(m) = m^e mod N and decryption D(c) = c^d mod N, with the secret key containing d and N’s factorization.The modulus is N = p · q, and d satisfies de = 1 mod ϕ(N).Source: Exercises · p. 55

Hidden Subgroup Problem

This section presents the Hidden Subgroup Problem across Abelian and non-Abelian groups, including its connections to Simon’s problem, period-finding, discrete logarithms, and graph isomorphism. It also examines query-efficient identification of hidden subgroups and the potential computational cost of implementing the required measurements.

6.1.2 Definition and some instances of the HSP

The HSP asks for a subgroup H whose efficiently computable function is constant exactly on H’s cosets and distinct across different cosets.Because H may be large, finding H typically means finding a generating set.Source: §6.1.2 · p. 58
Simon’s problem, period-finding, and discrete logarithms are Abelian HSP instances, with the hidden subgroup generator encoding the target secret.For discrete logarithms, the hidden subgroup is generated by (a, 1), so finding its generator yields a.Source: §6.1.2 · pp. 58–59

6.2 An efficient quantum algorithm if G is Abelian

For efficiently computable functions on finite Abelian groups, the standard quantum algorithm solves the HSP efficiently, generalizing factoring and enabling discrete-log computation.The procedure uses coset states, the group’s QFT, and samples from H⊥ to obtain constraints determining generators of H.Source: §6.2 · p. 59, §6.2.2 · p. 61

6.2.1 Representation theory and the quantum Fourier transform

Representation theory identifies Abelian irreducible representations with characters, and the QFT maps computational basis states to the corresponding orthonormal character basis.For product groups, the QFT is the tensor product of cyclic-group QFTs; for Z2^n it is H⊗n.Source: §6.2.1 · pp. 59–60

6.2.2 A general algorithm for Abelian HSP

For Simon’s problem, O(n) samples provide n−1 independent equations g · s = 0 modulo 2, after which Gaussian elimination recovers s.The algorithm samples uniformly from H⊥, consisting of labels orthogonal to the hidden string s.Source: §6.2.2 · p. 61
For period-finding, measurements yield multiples of ϕ(N)/r, while replacing the unavailable exact QFT with a power-of-two QFT underlies Shor’s algorithm.For discrete logarithms, sampling H⊥ yields (c, −ac), allowing recovery of a when gcd(c, N) = 1.Source: §6.2.2 · p. 61

6.3.1 The symmetric group and the graph isomorphism problem

Graph isomorphism reduces to the HSP over S2n by hiding the automorphism group of the disjoint union of the input graphs; its generators decide isomorphism.If the graphs are isomorphic, the automorphism group contains a permutation swapping the two components; otherwise it does not.Source: §6.3.1 · p. 62

6.3.2 Non-Abelian QFT on coset states

Non-Abelian QFTs can be efficiently implemented in relevant cases, but the standard coset-state algorithm often reveals insufficient information, leaving general efficient HSP algorithms unknown.A query-efficient algorithm instead uses repeated coset states that become nearly orthogonal for different hidden subgroups.Source: §6.3.1 · p. 62, §6.3.2 · p. 63, §6.3.3 · p. 63

6.3.3 Query-efficient algorithm

m = O((log |G|)^2) copies make the hidden-subgroup states sufficiently orthogonal for a POVM to identify H with high probability.The POVM has one element for each possible hidden subgroup H.Source: §6.3.3 · p. 63
The algorithm requires only polylogarithmically many queries to the function f.This follows from choosing m = O((log |G|)^2).Source: §6.3.3 · p. 63
The POVM may not be efficiently implementable, potentially requiring polynomially many elementary gates in |G|.The implementation is assumed to use computational-basis measurement at the end.Source: §6.3.3 · p. 63

Exercises

These exercises connect hidden subgroup sampling to Deutsch-Jozsa and discrete logarithms, while also covering state discrimination and graph isomorphism.

Hidden subgroup problems

The Abelian hidden subgroup framework is used to formulate Deutsch-Jozsa and discrete-logarithm exercises, including explicit identification of G, f, H, and H⊥.Source: Exercises · p. 63

Cryptography

Diffie-Hellman lets Alice and Bob derive K = γ^ab from exchanged values, while an adversary able to compute discrete logarithms can recover the shared key.Source: Exercises · pp. 63–64

State discrimination

Projective measurement distinguishes pairwise orthogonal states perfectly, while a POVM is requested to distinguish pairwise almost orthogonal states with success probability at least 2/3.Source: Exercises · p. 64

Graph isomorphism

The graph-isomorphism exercise asks students to use efficiently prepared adjacency-matrix superpositions to decide whether two given graphs are isomorphic.Source: Exercises · p. 64

Grover’s Search Algorithm

This section develops Grover’s algorithm and its reflection-based generalization to amplitude amplification, establishing quadratic quantum speedups for unordered search and efficiently recognizable success events. It covers applications including search, counting, amplitude estimation, optimization, collision finding, graph connectivity, and Simon’s algorithm, along with improvements in gate complexity and quantum query complexity.

7.1 The problem

The search problem asks for an index of a 1 in an N = 2^n-bit string, or “no solutions” when its Hamming weight t is zero.It models searching an unordered database; Grover is described as offering a quadratic speed-up while remaining more widely applicable than Shor’s algorithm [132].Source: §7.1 · p. 65, Grover’s Search Algorithm · p. 65

7.2 Grover’s algorithm

After k Grover iterations, measuring yields solution probability P_k = sin((2k + 1)θ)^2; choosing k as the integer closest to π/(4θ) − 1/2 keeps failure probability small when t ≪ N.When t is unknown, the stopping point is unknown, but an algorithm using exponentially increasing guesses for k achieves an expected O(√(N/t)) queries.Source: §7.2 · pp. 67–68
For unknown t, Grover still finds a solution in expected O(√(N/t)) queries, detects t = 0 by checking the output, and reduces failure to ε using O(√(N log(1/ε))) queries.The logarithm lies inside the square root, improving over ordinary repetition.Source: §7.2 · p. 68

7.3 Amplitude amplification

Amplitude amplification raises a unitary algorithm’s success probability from p to nearly 1 using O(1/√p) runs of A and A−1, versus O(1/p) classically [68].The procedure uses two reflections whose product rotates amplitude toward the good subspace; A must be unitary because the reflection requires A−1.Source: §7.3 · pp. 69–70

7.4 Application: faster solution for satisfiability

Grover can encode Boolean satisfiability as a phase oracle and find a satisfying assignment with high probability in 2^n times a polynomial factor.The reversible computation computes ϕ, applies a phase flip, and uncomputes workspace; for TSP, Grover’s quadratic improvement over brute force remains slower than the classical 2^n dynamic program, while a more complex quantum algorithm is polynomially faster than the best known classical methods [17].Source: §7.4 · p. 70
The material also applies Grover-style techniques to satisfiability, including implementing an oracle-driven unitary and finding unique solutions with bounded query complexity.The search oracle has the usual form O_x: |i,b⟩ ↦ |i,b ⊕ x_i⟩, and the exercises ask for unique-solution algorithms and solution-measurement probabilities.Source: §7.4 · p. 72
Grover-based procedures address unknown-weight search, approximate counting, and amplitude estimation through phase-estimation rotations.The exercises specify bounded-error search and counting guarantees, while amplitude estimation uses O(1/ε) applications of the constructed rotation.Source: §7.4 · pp. 72–73
The notes extend the search framework to minimum finding, collision finding, and structured unique-search problems with query access to finite strings or numerical sequences.The supplied exercises include minimum finding with probability at least 2/3, collision finding for 2-to-1 inputs, and unique search over restricted index prefixes.Source: §7.4 · p. 73
A gate complexity of O(N log log N) improves on standard Grover’s O(N log N), with log log N reducible further to nearly constant [29].Source: §7.4 · p. 73
For graph connectivity, quantum search finds edges joining known components in expected O(n/√(c−1)) queries and decides connectivity using at most O(n^3/2) queries.Classical randomized connectivity testing requires Ω(n^2) queries, establishing a quantum query advantage.Source: §7.4 · p. 74
Finally, the exercises use quantum procedures to reduce Simon’s algorithm’s error probability to zero, finding a new orthogonal relation with O(1) queries and the hidden string with O(n) queries.Source: §7.4 · p. 74

Quantum Walk Algorithms

This section develops quantum-walk methods by connecting classical convergence and spectral gaps to unitary-walk search, with applications to Grover search, collision-finding, and triangle-finding. It also discusses the unresolved optimal query and time complexities for triangle-finding.

8.1 Classical random walks

For connected, non-bipartite regular graphs, classical random walks converge to the uniform distribution at a rate controlled by the spectral gap δ, reaching error η after k = ln(1/η)/δ steps.After convergence, a walk hits a marked vertex with probability roughly ε, while the procedure can use only O(log N) space when neighbors are efficiently computable.Source: §8.1 · pp. 75–76

8.2 Quantum walks

The quantum walk encodes directed edges in two registers and implements W(P) as reflections over neighbor-superposition subspaces, enabling Grover-like amplitude amplification between good and bad states.Phase estimation distinguishes eigenvalue-1 states from the others so the resulting reflection preserves stationary eigenvectors and negates the rest.Source: §8.2 · pp. 77–78
Quantum-walk search finds a marked vertex with cost O(S + (U/√δ + C)/√ε), square-rooting both ε and δ relative to classical search.The walk uses phase estimation to implement the reflection through the stationary state, requiring O(1/δ) applications of the walk operator.Source: §8.2 · pp. 78–79

8.3.1 Grover search

On the complete graph, the quantum-walk framework rederives Grover search using O(1/√ε) queries, including O(√N) queries in the worst case ε = 1/N.The complete graph has spectral gap δ ≈ 1, with setup and update costs zero and checking cost one query.Source: §8.3.1 · p. 79

8.3.2 Finding collisions

Quantum walks solve collision-finding in O(n^2/3) queries by walking on Johnson graphs, matching the optimal quantum query complexity.Choosing r = n^2/3 gives the bound; efficient data structures further yield time n^2/3(log n)^O(1).Source: §8.3.2 · p. 80

8.3.3 Finding a triangle in a graph

A Johnson-graph quantum walk finds a triangle using O(n^13/10) queries when r = n^3/5, with an inner quantum walk and Grover search supplying the checking procedure.The final measurement yields a set containing an edge of a triangle, after which Grover search finds the third vertex.Source: §8.3.3 · p. 81
The best known quantum time-complexity exponent for triangle-finding is 5/4 [172].The exponent 13/10 can be slightly improved further [43] [173] [152].Source: §8.3.3 · p. 81
The optimal quantum query complexity of triangle-finding is unknown, with only an Ω(n) lower bound established.Source: §8.3.3 · p. 81
The optimal quantum time complexity of triangle-finding also remains open.Source: §8.3.3 · p. 81

Exercises

The exercises develop quantum-mechanical tools and apply quantum walks to collision finding, matrix verification, and Boolean satisfiability. They also contrast classical and quantum query or time costs for these problems.

Projectors and reflections

The projector exercises characterize P on a subspace and show that R = 2P − I reflects vectors in that subspace while negating orthogonal vectors.They also ask for eigenvectors with eigenvalues 1 and −1 for a normalized adjacency matrix of a regular bipartite graph.Source: Exercises · pp. 81–82

Collision finding

A collision-finding exercise asks for a quantum walk on the Johnson graph J(n, r), storing data at each vertex and finding a marked vertex with O(n2/3) queries.A vertex is marked when an element inside it collides with an element outside it.Source: Exercises · p. 82

Matrix verification

The matrix-verification exercises compare classical randomized verification using O(n2) steps with a quantum query algorithm using O(n5/3) queries.The task is to decide whether AB = C with success probability at least 2/3.Source: Exercises · p. 82

3-SAT

The 3-SAT exercises use Schöning’s random walk, whose satisfiable-instance success probability is at least (3/4)^n/5n, to derive a classical algorithm running in time (4/3)^n · p(n) and ask for a quantum counterpart.The walk starts from a uniformly random assignment and flips a randomly chosen variable from a false clause.Source: Exercises · p. 82

Hamiltonian Simulation

This section develops quantum algorithms and complexity methods for Hamiltonian simulation, quantum linear systems, query complexity, and related computational problems. It also covers QMA and local Hamiltonians, quantum communication and nonlocality, cryptography, and quantum learning, together with associated lower bounds, protocols, and exercises.

9.1 Hamiltonians

A Hamiltonian determines time evolution through the Schrödinger equation; for time-independent H, the solution is the continuous unitary evolution e^{-iHt}.Hamiltonians commonly consist of many local terms, and simulation seeks a circuit ε-close to e^{iHt} for every input state under operator-norm error.Source: §9.1 · pp. 83–84

9.2 Method 1: Lie-Suzuki-Trotter methods

First-order Lie-Suzuki-Trotter simulation decomposes a sum of local Hamiltonian terms into products of short evolutions, achieving error ε with gate complexity polynomial in t and ε.For m terms, choosing r = O(m^2t^2/ε) yields error at most ε; the gate count depends quadratically on t, while higher-order variants can approach linear t-dependence.Source: §9.2 · p. 85

9.3 Method 2: Linear combination of unitaries (LCU)

LCU prepares a normalized M|ψ⟩ by combining controlled easy unitaries, postselecting an ancilla outcome, and using amplitude amplification when necessary.The success probability is p = ∥M|ψ⟩∥^2/∥α∥_1^2, and oblivious amplitude amplification handles the single-copy-state setting relevant to Hamiltonian simulation.Source: §9.3 · pp. 86–87

9.3.1 Hamiltonian simulation via LCU

LCU simulates local Hamiltonians with cost O(mt log(mt/ε)), linear in t and logarithmic in ε, improving on Lie-Suzuki-Trotter methods [56] [57] [58].For 2-local H, the method decomposes H into Pauli unitaries and uses time blocking with oblivious amplitude amplification.Source: §9.3.1 · pp. 87–88

9.4 Method 3: Transforming block-encoded matrices

Block-encoding represents an n-qubit matrix A as the top-left block of a larger unitary, generalizing LCU’s encoding of M/∥α∥_1.An a-qubit block-encoding U satisfies (⟨0^a| ⊗I)U(|0^a⟩⊗I) = A.Source: §9.4 · p. 89
Sparse access to an s-sparse Hermitian matrix A yields a block-encoding of A/s using superpositions over nonzero row and column locations.The construction assumes oracles for matrix entries and nonzero-entry locations, and uses O_A,loc together with O_A and O_A^-1.Source: §9.4 · p. 89
Polynomial transformations convert a block-encoding of Hermitian A into a block-encoding of P(A), using d queries to U and U^-1 plus O(ad) two-qubit gates [127].The technique generalizes to quantum singular-value transformation for arbitrary, non-Hermitian, and rectangular matrices [127].Source: §9.4 · p. 90

9.4.1 Hamiltonian simulation via transforming block-encoded matrices

ε-precise simulation of an s-sparse Hamiltonian H with ∥H∥≤1 uses O(st + log(1/ε)) queries to H and O(n(st + log(1/ε))) two-qubit gates.The method approximates e^ixt with a degree-O(t + log(1/ε)) polynomial, applies the block-encoding transformation, and uses oblivious amplitude amplification.Source: §9.4.1 · p. 90

10.1 The linear-system problem

The HHL chapter defines the quantum linear-system problem as preparing an n-qubit state whose amplitudes encode the normalized solution x=A^-1b, rather than outputting x itself.For simplicity, A is assumed invertible; without full rank, the method can invert A on its support using the Moore-Penrose pseudoinverse.Source: §10.1 · p. 95

10.2 The basic HHL algorithm for linear systems

The basic HHL construction applies phase estimation to e^{iA}, conditionally rotates an ancilla by an eigenvalue-dependent factor, uncomputes the estimate, and uses O(κ) amplitude-amplification rounds.This implements the inverse eigenvalue map on |b⟩ despite A^-1 not being unitary.Source: §10.2 · pp. 96–97
HHL prepares an ε-close quantum state |x⟩ for A|x⟩=|b⟩ using roughly κ^2s/ε queries and κ(sκn/ε+B) other two-qubit gates.The setup assumes efficient preparation of |b⟩, sparse access to A, and condition number at most κ.Source: §10.1 · p. 96, §10.2 · p. 97

10.3 Improving the efficiency of the HHL algorithm

The improved HHL algorithm uses singular-value transformation to approximate 1/x, achieving O(κ^2s log(κ/ε)) queries and O(κs(κn log(κ/ε)+B)) gates.Its logarithmic dependence on 1/ε improves on basic HHL, while variable-time amplitude amplification can reduce the κ dependence from quadratic to linear.Source: §10.3 · pp. 97–98
When s, κ, and B are polylogarithmic in N and ε ≥ 2^-polylog(N), improved HHL solves an N-dimensional linear system with polylog(N) queries and gates.The output is a quantum state encoding the normalized solution, and the method also supports applications such as approximately solving differential equations.Source: §10.1 · p. 95, §10.3 · p. 98

11.1 Introduction

Quantum query algorithms access input bits through an oracle, interleave queries with fixed unitaries, and measure the final state; query complexity counts oracle calls while treating fixed unitaries as free.The polynomial method shows that T-query algorithms have degree-T amplitude polynomials and degree-2T output-probability polynomials, yielding query lower bounds from approximating-polynomial degree.Source: §11.1 · pp. 101–102, §11.2 · pp. 102–103

11.2 The polynomial method

Grover’s algorithm is optimal up to a constant factor for bounded-error OR, but exact OR requires at least N/2 queries and loses the square-root speed-up.The polynomial method also shows that total symmetric functions admit at most quadratic quantum speed-ups, while arbitrary total functions admit at most power-6 speed-ups.Source: §11.2 · p. 104

11.3 The quantum adversary method

The polynomial method’s broad applicability is also a limitation because it permits arbitrary linear transformations, so it may miss stronger quantum query lower bounds.Arunachalam et al. [27] strengthened it toward an optimal lower-bound method by imposing additional polynomial constraints.Source: §11.3 · p. 104, §11.2 · p. 104
The quantum adversary method tracks how a query changes a progress measure over hard-to-distinguish input pairs, while input-independent unitaries preserve that measure.Choosing relations with large m0 and m1 but small ℓ0 and ℓ1 yields query lower bounds; Ambainis introduced the method, which exploits unitarity crucially.Source: §11.3 · pp. 105–106
For N-bit OR, the adversary method achieves the optimal Ω(N) lower bound, and for a 2-level AND-OR tree it gives an optimal lower bound more easily than approximate-degree methods.For the tree, the relation has m0 = m1 = k and ℓ0 = ℓ1 = 1.Source: §11.3 · p. 106

Exercises

The exercises apply polynomial, adversary, and hybrid methods to parity, majority, permutation inversion, sorting, block sensitivity, search, and general query-algorithm polynomials.They include proving N/2-query optimality for exact parity, Ω(N) bounded-error complexity for majority, and Ω(N) comparison complexity for sorting.Source: Exercises · pp. 106–107
The exercises establish that a T-query quantum algorithm’s acceptance probability is an N-variate multilinear polynomial of degree at most 2T and cannot distinguish uniform inputs from 2T-wise independent ones.The latter statement applies to any final binary measurement.Source: Exercises · p. 109

12.1 The generalized adversary bound

The generalized adversary bound gives optimal quantum query-complexity lower bounds for all Boolean functions and can produce matching algorithms.The method strengthens earlier polynomial and adversary bounds, which are not optimal for every function.Source: §12.1 · p. 111
For an adversary matrix Γ, every bounded-error algorithm requires Ω(∥Γ∥/max_i∥Γ_i∥) queries, recovering the familiar Ω(√N) search lower bound.The matrices Γ_i retain entries Γ_xy only when x_i ≠ y_i; for search, ∥Γ_i∥=1.Source: §12.1 · p. 112

12.2 The dual of the generalized adversary bound

Optimizing the adversary matrix defines ADV±(f) as a semidefinite program whose dual has equal value by strong duality.Primal feasible matrices provide lower bounds, while dual feasible vector families provide upper bounds on ADV±(f).Source: §12.2 · pp. 113–114

12.3 ADV± is an upper bound on quantum query complexity

A dual feasible solution with objective value A yields a bounded-error quantum algorithm using O(A) queries via phase estimation on a product of two reflections.The input-dependent reflection costs one query, while the other reflection is input-independent; the result concerns query complexity rather than general gate complexity.Source: §12.3 · pp. 114–116

12.4 Applications

For OR under the promise of at most one 1-bit, one-dimensional dual vectors give an O(√N)-query algorithm.The same dual framework has also produced algorithms for k-collisions, juntas, graph st-connectivity, and formula evaluation [42] [45] [18] [48] [221].Source: §12.4 · pp. 116–117

12.5 Perfect composition and AND-OR trees

Adversary-bound composition makes quantum query complexity multiplicative, yielding an optimal O(√N)-query algorithm for a two-level AND-OR tree and roughly √N queries for game-tree evaluation.The method composes adversary bounds rather than bounded-error algorithms, avoiding compounded error-probability issues.Source: §12.5 · p. 117
The generalized adversary bound can sometimes prove substantially stronger lower bounds than the polynomial method, and its negative-weights version can give substantially better bounds than the nonnegative-weights version.The polynomial method cannot prove a lower bound better than O(N), while restricting Γ gives at most Ω(2.5d).Source: §12.5 · p. 118

13.1 Most functions need exponentially many gates

Almost all Boolean functions require quantum circuits with Ω(2^n/n) elementary gates, so only very few computational problems are efficiently solvable on quantum computers.Counting circuits over a fixed finite gate set bounds the number of functions computable with C gates by C^O(C).Source: §13.1 · p. 121

13.2 Classical and quantum complexity classes

The complexity classes include BPP ⊆ BQP ⊆ PSPACE, QPSPACE = PSPACE, and QMA, with 2-local Hamiltonian ground-state estimation being QMA-complete.BQP is the accepted class for polynomial-time quantum computation with error at most 1/3, while factoring is in BQP and is generally believed not to be in BPP.Source: §13.2 · pp. 122–123

13.3 Classically simulating quantum computers in polynomial space

A polynomial-size quantum circuit can be simulated classically in polynomial space by computing each final-state amplitude and summing squared amplitudes for accepting basis states.This proves the inclusion BQP ⊆ PSPACE, though the simulation is not necessarily efficient in time.Source: §13.3 · pp. 124–125

Exercises

The exercises develop efficient matrix-entry calculations, BQP subroutine composition, amplitude-based computation tests, the inclusion BQP ⊆ PP, and NP-hardness consequences of efficient entanglement detection.These problems also use bounded-error quantum circuits with Hadamard and Toffoli gates and relate oracle-style BQP computations to ordinary polynomial-size circuits.Source: Exercises · pp. 125–126

14.1 Quantum Merlin-Arthur (QMA)

QMA consists of promise problems verified by polynomial-size quantum circuits using polynomial-size quantum witnesses, with completeness at least 2/3 and soundness at most 1/3.The definitions imply NP ⊆ MA ⊆ QCMA ⊆ QMA; QMA is believed larger than NP, while Marriott–Watrous amplification reduces error without increasing witness size [197].Source: §14.1 · pp. 127–128

14.2 The local Hamiltonian problem

SAT maps to a diagonal k-local Hamiltonian whose ground-state energy equals the minimum number of unsatisfied clauses, so satisfiability is equivalent to λmin = 0.The general problem distinguishes λmin ≤ a from λmin ≥ b under promise gap b − a ≥ 1/poly(n), and is NP-hard already for k ≥ 2.Source: §14.2 · pp. 129–130

14.3 Local Hamiltonian is QMA-complete

k-local Hamiltonian is QMA-complete, establishing a quantum analogue of the Cook–Levin theorem.Membership uses a ground-state witness, while hardness encodes an arbitrary QMA verifier into a Hamiltonian.Source: §14.3 · p. 130

14.3.1 Completeness and soundness

The history-state construction gives completeness λmin ≤ 1/[4T(T + 1)] and soundness λmin ≥ 2a for a := 1/[4T(T + 1)].A clock register penalizes initialization, incorrect gate propagation, and rejecting output; soundness follows because a low-energy state would imply incompatible computation states.Source: §14.3.1 · pp. 131–132
For x∈L0, λmin≥b, while for x∈L1, λmin≤a=1/(4T(T+1)); thus b−a=a≥1/poly(n).The history state witnesses the low-energy case.Source: §14.3.1 · p. 132

14.3.2 Reducing the locality

Unary clock encoding makes every Hamiltonian term 5-local, proving k-local Hamiltonian QMA-complete for k≥5, while Kempe, Kitaev, and Regev established QMA-completeness for k=2.The unary clock uses T qubits and penalizes invalid 1s-followed-by-0s strings.Source: §14.3.2 · p. 133
For gaps b−a≥Ω(m), k-local Hamiltonian is NP-hard for k≥2, but QMA-hardness remains open as the quantum PCP conjecture [7].The standard completeness results assume a polynomially small gap.Source: §14.3.2 · p. 133

14.4 Other interesting problems in QMA

Other QMA problems include physical local Hamiltonians, Non-Identity check, k-local density matrix consistency [180] [71], and group non-membership [257].Group non-membership is in QMA but is neither known QMA-complete nor known to be in NP.Source: §14.4 · pp. 133–134

14.5 Quantum interactive proofs

Quantum interactive proofs satisfy QIP=IP [150], and every QIP protocol can be reduced to three messages with constant-gap amplification [259].Adding quantum communication preserves the decidable language class while reducing the required messages from polynomial to constant.Source: §14.5 · pp. 134–135

Exercises

The exercises extend the Hamiltonian construction to a unary clock without simplifying assumptions, reducing the completeness–soundness gap to Ω(1/T^6), and ask for BQP procedures using phase estimation and Hamiltonian simulation.They also include proofs that k-local Hamiltonian lies in QMA and that a restricted eigenvalue problem is BQP-complete.Source: Exercises · pp. 135–136

15.1 Mixed states and general measurements

Mixed states are represented by trace-1 positive semidefinite density matrices, unitary evolution acts by conjugation, and projective or POVM measurements determine outcome probabilities via Tr(Piρ) or Tr(Eiρ).A mixed state is pure exactly when its density matrix has rank 1.Source: §15.1 · pp. 139–140

15.2 Quantum encodings and their limits

Holevo’s theorem limits information from m transmitted qubits to m bits without prior entanglement and 2m bits with prior entanglement, while m classical bits convey at most m bits [145].Thus an m-qubit encoding cannot yield more than m accessible bits without entanglement, or twice that with entanglement.Source: §15.2 · pp. 140–141
Quantum encodings of N classical values in dimension d have average decoding success at most d/N, while random-access codes can recover individual bits but generally cannot recover multiple bits from one disturbed state.For n random bits encoded into m qubits, the general decoding bound is 2^m/2^n; Nayak’s lower bound is achievable up to an additive O(log n) term even classically.Source: §15.2 · pp. 141–142
Nayak’s theorem states that encoding n-bit strings into m qubits with per-bit recovery probability p requires m ≥ (1 − H(p))n.The bound applies when success probability is averaged over uniformly chosen inputs and measurement randomness; it follows from the information gained about each independent bit.Source: §15.2 · p. 142

15.3 Lower bounds on locally decodable codes

The Hadamard code has length N = 2^n and is a (2, δ, 1/2 − 2δ)-locally decodable code, recovering each bit by querying paired positions.The two queried positions differ by the bit index, and their mod-2 sum gives the target bit whenever both queried symbols are uncorrupted.Source: §15.3 · p. 143
For 2-query locally decodable codes, Theorem 5 proves the exponential codelength lower bound N ≥ 2^{Ω(δ^2ε^4n)}, making the exponential-length Hadamard code essentially optimal.The proof encodes each codeword into log N qubits, turns the decoder’s query structure into a quantum random-access code, and applies Nayak’s theorem.Source: §15.3 · pp. 143–144

Exercises

The exercises reinforce density-matrix and Bloch-sphere representations, quantum random-access codes, teleportation limits, Fourier-transform circuits, and measurements distinguishing mixed states.They include a 2-bit-to-1-qubit random-access code with success probability p ≥ 0.85 and ask for an upper bound of 1/2 + O(1/√n) when encoding n bits into one qubit.Source: Exercises · pp. 144–145

16.1 Classical communication complexity

Quantum communication complexity studies the minimum communication Alice and Bob need to compute a function f(x, y) when each receives part of the input.The classical setup takes inputs x ∈ X and y ∈ Y with (x, y) in the domain, and communication is required because f generally depends on both inputs.Source: §16.1 · p. 147
Classical communication complexity measures worst-case communicated bits, with deterministic protocols requiring correctness on every input and bounded-error protocols succeeding with probability at least 2/3.Randomness can reduce equality testing to O(log n) private-coin communication, whereas deterministic equality requires n bits.Source: §16.1 · pp. 147–148

16.2 The quantum question

Quantum communication models exchange qubits, use shared EPR-pairs with classical communication, or combine both, with teleportation relating their costs up to a factor of 2.Quantum communication can outperform classical communication because the parties need only determine f(x,y), not transmit all information contained in the classical protocol.Source: §16.2 · pp. 148–149

16.3 Example 1: Distributed Deutsch-Jozsa

Distributed Deutsch-Jozsa uses log n qubits with zero error, versus at least 0.007n classical bits for errorless protocols under its promise, but bounded-error classical communication drops to O(log n).Bob applies phase encoding and a Hadamard transform; the |0^log n⟩ amplitude distinguishes equal inputs from inputs differing in exactly n/2 positions.Source: §16.3 · pp. 149–150

Quantum communication advantages

Quantum protocols achieve exponential, quadratic, and logarithmic communication advantages for distributed Deutsch-Jozsa, Intersection, vector-in-subspace, and fingerprinting problems.The advantages arise from quantum superposition, Grover search, compact quantum representations, and nearly orthogonal fingerprints.Source: §16.3 · p. 150, §16.4 · p. 151, §16.5 · p. 151

16.4 Example 2: The Intersection problem

Grover-based Intersection communication uses O(√n log n) qubits, while bounded-error classical protocols need about n bits and quantum protocols require about √n qubits.Alice and Bob simulate each phase query with two messages of O(log n) qubits, and Razborov’s lower bound shows the √n dependence is necessary.Source: §16.4 · pp. 150–151

16.5 Example 3: The vector-in-subspace problem

For vector-in-subspace, Alice sends a log m-qubit state that Bob measures perfectly under the promise, whereas every bounded-error classical protocol needs Ω(m^1/3) bits.The quantum advantage comes from representing an m-dimensional unit vector as a log m-qubit state; after discretization, the input length is n = O(m^2 log m).Source: §16.5 · p. 151

16.6 Example 4: Quantum fingerprinting

In the simultaneous-message model, equality needs Ω(√n) classical bits but only O(log n) quantum fingerprint qubits per message.Fingerprints derived from error-correcting codes have pairwise inner products at most 0.02, and the SWAP test distinguishes equality with arbitrarily small error after repetition.Source: §16.6 · pp. 152–153

Exercises

The exercises ask students to prove one-way quantum and classical lower bounds, design bounded-error intersection protocols, analyze restricted search, and extend quantum fingerprinting constructions.They include an Ω(n) one-way lower bound for disjointness, an O((n/r) log n) protocol with r rounds, and an O(k log n) protocol for inputs of Hamming weight k.Source: Exercises · pp. 153–154
The exercises cover quantum fingerprinting, communication lower bounds, hidden matching, subgroup testing, and protocols contrasting quantum and classical communication.They include O(log n)-qubit fingerprinting, a quantum protocol for hidden matching, and an Ω(m^c)-bit classical lower bound for a related problem.Source: Exercises · pp. 155–156

17.1 Quantum non-locality

Bell experiments produce entanglement-based correlations that cannot be reproduced by any local realist theory, although they do not establish quantum mechanics itself.Aspect and later experiments observed the predicted correlations; the result disproves the conjunction of locality and realism, rather than locality alone.Source: §17.1 · p. 158

17.2 CHSH: Clauser-Horne-Shimony-Holt

In CHSH, classical shared-randomness strategies achieve at most 3/4 success, whereas entanglement achieves cos(π/8)^2 ≈0.85, the optimal quantum value shown by Tsirelson.The quantum strategy uses a shared entangled two-qubit state and input-dependent local rotations and measurements.Source: §17.2 · pp. 159–160

17.3 Magic square game

In the magic square game, the best classical strategy succeeds with probability 8/9, while a quantum strategy using two entangled qubit pairs always succeeds.The quantum protocol measures commuting Pauli-product observables by rows and columns, enforcing the parity constraints and agreement at their intersection.Source: §17.3 · pp. 160–161
In the magic square game, shared entanglement produces measurement outcomes satisfying the required parity relation ay ⊕ bx = 0.The derivation uses two EPR-pairs and establishes ay = bx from two distinct outcome parities.Source: §17.3 · p. 162

17.4 A non-local version of distributed Deutsch-Jozsa

The non-local Deutsch-Jozsa problem is solved perfectly without communication using log n EPR-pairs, whereas any perfect classical protocol requires Ω(n) communication.The quantum strategy succeeds with probability 1, while the communication lower bound is C ≥ 0.007n − log n = Ω(n).Source: §17.4 · pp. 162–163

Exercises

The exercises extend the discussion to CHSH, GHZ, and EPR-pair protocols, including an operator-based derivation of the quantum winning probability.They ask for classical and quantum strategies, entanglement transformations, measurement distributions, and the best possible CHSH success probability.Source: Exercises · pp. 164–165

18.1 Saving cryptography from Shor

Quantum cryptography is presented as an alternative to post-quantum cryptography that can provide information-theoretic security, though honest users require simple quantum computers.The motivation is that Shor’s algorithm breaks RSA and Diffie-Hellman when large quantum computers become available.Source: §18.1 · p. 167

18.2 Quantum key distribution

BB84 detects eavesdropping through information disturbance, producing a raw key after basis comparison and testing, followed by reconciliation and privacy amplification.The protocol communicates n qubits and O(n) classical bits overall, yielding a shared key with linear communication overhead.Source: §18.2 · pp. 168–169

18.3 Reduced density matrices and the Schmidt decomposition

The Schmidt decomposition represents every bipartite pure state using unique Schmidt rank and coefficients, while reduced density matrices describe each party’s local state after tracing out the other.For an EPR pair, the local state is maximally mixed and the Schmidt rank is 2; local density matrices share the squared Schmidt coefficients as eigenvalues.Source: §18.3 · pp. 170–171

18.4 The impossibility of perfect bit commitment

A perfectly concealing quantum bit-commitment protocol cannot be binding, because Alice can locally switch between commitments after the commit phase.Equal reduced states on Bob’s side imply Schmidt decompositions with shared coefficients and Bob states, allowing Alice’s unitary to change her committed bit.Source: §18.4 · p. 172

18.5 More quantum cryptography

Quantum cryptography supports partially secure commitment, nearly perfect weak coin flipping under quantum or bounded-storage assumptions, secure multiparty computation, device-independent protocols, and experimentally accessible key distribution.Device-independent approaches use Bell-inequality violations to certify entanglement, while quantum key distribution requires preparing, transmitting, and measuring qubits but remains vulnerable to implementation imperfections.Source: §18.5 · p. 172

Exercises

The exercises apply these ideas to BB84 measurement disturbance, Schmidt rank and decomposition, purification, quantum one-time pads, entanglement, and computational tests for pure-state entanglement.For mixed states, deciding entanglement is noted to be NP-hard and therefore probably not polynomial-time solvable.Source: Exercises · pp. 173–174

19.1 Introduction

Quantum machine learning studies how quantum computers can learn from classical or quantum data across supervised, unsupervised, and reinforcement-learning settings.The chapter focuses on representative supervised and unsupervised methods, mostly with classical output.Source: §19.1 · p. 175

19.2.1 The PAC model of learning

The PAC model formalizes supervised learning as producing a hypothesis for a Boolean target drawn from a concept class, with generalization error measured under the data distribution.Examples are independently sampled from an unknown distribution D, while the target function belongs to a restricted concept class C.Source: §19.2.1 · p. 176
PAC learning seeks hypotheses with small generalization error, while sample and time complexity quantify the data and computation required; distribution-independent learners must work for every distribution.Efficient learners exist for some classes, such as k-CNF formulas and regular languages with membership queries, but many concept classes are not efficiently learnable.Source: §19.2.1 · pp. 176–177

19.2.2 Learning from quantum examples under the uniform distribution

Quantum examples yield major uniform-distribution gains: linear functions are learned exactly with high probability using O(1) examples and O(n) gates, while s-term DNF is learnable in polynomial time via Fourier sampling and boosting.For linear functions, one Fourier sample identifies the hidden vector, versus Θ(n) classical examples under the uniform distribution; quantum examples are available only in special settings.Source: §19.2.2 · pp. 177–178

19.2.3 Learning from quantum examples under all distributions

Quantum examples provide no asymptotic sample-complexity advantage for distribution-independent PAC learning, because the classical VC-dimension characterization remains necessary and sufficient up to constant factors.Sufficiency follows by measuring the examples and using a classical learner; necessity follows from a reduction involving quantum measurement copies.Source: §19.2.3 · p. 178

19.2.4 Learning quantum states from classical data

An unknown n-qubit state can be learned from classical measurement data as a predictor of probabilities using O(n) examples, despite requiring exponentially many copies to approximate the state itself in trace distance.The learned function is f(M)=Tr(Mρ), and the stated sample bound has polynomial dependence on γ and ε but exponential time complexity.Source: §19.2.4 · p. 179

19.3 Unsupervised learning from quantum data

Quantum PCA prepares top eigenstates of a correlation matrix by phase estimation on a mixed state proportional to that matrix, learning the largest eigenvalues and corresponding principal components in poly(k) repetitions.The method assumes efficient state preparation, concentrated top-k eigenvalues, and eigenvalue gaps of at least 1/poly(k); it is heuristic and produces quantum rather than explicit classical basis vectors.Source: §19.3 · pp. 179–180, §19.4 · p. 180

19.4 Optimization

Optimization with classical data may use quantum subroutines, but practical benefit depends on how inputs are encoded and whether outputs must be classical.Examples include quantum linear algebra, gradient estimation, and algorithms for graph, convex, linear, semidefinite, SVM, regression, and PCA problems.Source: §19.4 · p. 180, §19.4.2 · p. 182

19.4.1 Variational quantum algorithms

Variational quantum algorithms minimize measured observables with a classical parameter-optimization loop; VQE applies this to approximate Hamiltonian ground energies using a problem-specific parametrized Ansatz.The approach suits small near-term devices but is heuristic because performance depends strongly on the chosen Ansatz, while general ground-state energy estimation is QMA-hard.Source: §19.4.1 · p. 181, §19.4.2 · p. 181

19.4.2 Some provable quantum speed-ups for optimization

Provable quantum optimization speed-ups use Grover-based routines, quantum linear algebra, or quantum gradient methods, but often rely on strong access assumptions or produce quantum-state outputs that limit practicality.The notes cite shortest paths, minimum cuts, graph sparsification, linear systems, convex optimization, and PCA with classical output as examples.Source: §19.4.2 · p. 182

Exercises

For PAC learning, an inaccurate hypothesis remains consistent with m examples with probability below (1 −ε)^m, motivating m = ⌈log(3|C|)/ log(1/(1 −ε))⌉ and an O(d log(N)/ε) sample bound.The exercises also ask for a lower bound based on a distribution concentrated on one shattered point, requiring Ω((d −1)/ε) examples to observe many remaining points.Source: Exercises · p. 183
A quantum algorithm computes the gradient of a linear f:R^d→R using one application each of O_f and O_f^{-1}; variants approximate gradients of sufficiently smooth nonlinear functions.The linear gradient is the coefficient vector (b_1, . . . , b_d), and the approach is due to Jordan [153] and further analyzed by Gilyén et al. [126].Source: Exercises · p. 184
Applying U^t=e^{iρt} to σ can be approximated within trace-norm error ε using O(t^2/ε) copies of ρ.The method uses a small-step expansion and a controlled-swap-based interaction whose first-order term is iη(ρσ−σρ), with O(η^2) error.Source: Exercises · p. 184
The exercises ask quantum computers to estimate |⟨ϕ|ψ⟩| to additive error 1/100 using O(1) copies and O(n) elementary gates, and to estimate state distance under real-positive overlap.For real overlap, the squared distance satisfies ∥|ϕ⟩−|ψ⟩∥^2 = 2−2⟨ϕ|ψ⟩; the exercises also ask whether |ϕ⟩ and −|ϕ⟩ can be distinguished from arbitrarily many copies.Source: Exercises · p. 184

Stabilizer States, Clifford Circuits, and One-Way Quantum Computing

This section develops stabilizer states, Clifford circuits, non-Clifford resources, one-way quantum computing, and quantum error correction, including fault-tolerant computation below an error threshold. It also provides mathematical foundations and exercise guidance spanning quantum computation, coding, complexity, information, and related topics.

20.1 Stabilizer states

A stabilizer state is uniquely determined, up to global phase, by n independent commuting Pauli stabilizers and may be a basis, superposition, or entangled state.Each independent stabilizer halves the state subspace dimension, leaving dimension 1 after n constraints; EPR pairs provide entangled examples.Source: §20.1 · p. 185

20.2 Clifford circuits

Clifford circuits are generated by Pauli, Hadamard, S, and CNOT gates, exactly preserving the Pauli group under conjugation; measurement-controlled variants add adaptive Pauli measurements and classical control.Intermediate measurements can produce a probability distribution over stabilizer states rather than one deterministic final state.Source: §20.2 · pp. 186–187

20.3 Efficient simulation of Cliffords: Gottesman-Knill theorem

The Gottesman-Knill theorem gives a classical polynomial-time algorithm that samples the same final stabilizer-state distribution as any measurement-controlled Clifford circuit starting from a basis state.The simulator stores n stabilizers using O(n^2) bits, updates them through Clifford gates and measurements, and outputs a classical stabilizer description.Source: §20.3 · pp. 187–188

20.4 T-gates and magic states

Adding a single non-Clifford T gate to {H, S, CNOT} yields universal quantum computation, while magic states allow T gates to be simulated using measurement-controlled Clifford circuits.Magic states can be prepared beforehand or generated on demand by a magic-state factory, shifting the non-Clifford cost into resource preparation.Source: §20.4 · p. 189

20.5 Efficient simulation of circuits with few T-gates

Circuits with t T gates can be classically simulated by decomposing |T⟩^⊗t into r stabilizer states, with runtime r times a polynomial in the circuit size.The best known stabilizer-rank upper bound is 3^t/4 ≈ 2^0.3963t, implying polynomial-time simulation for O(log n) T gates.Source: §20.5 · pp. 189–190

20.6 One-way quantum computing

One-way quantum computing avoids two-qubit operations during computation by starting with an entangled cluster state and performing adaptive single-qubit measurements.The cluster state may be prepared in advance or grown during computation, analogous to pre-preparing magic states.Source: §20.6 · p. 190

One-way quantum computing.

Cluster-state measurements implement universal single-qubit and CZ gates, with earlier outcomes adapting later measurement bases and leaving only trackable Pauli corrections.An n-qubit depth-d circuit maps to an n×(d+1) cluster state; final computational-basis measurements absorb or classically correct the accumulated Paulis.Source: §20.6 · pp. 191–192, One-way quantum computing · p. 192

Exercises

The exercises develop Clifford conjugation, binary Pauli representations, magic-state T-gate implementation, stabilizer-rank bounds, and one-way computation constructions.They also ask why Clifford-only algorithms such as Deutsch-Jozsa and Simon do not contradict the Gottesman-Knill theorem.Source: Exercises · pp. 193–194

21.1 Introduction

If operation errors are reasonably small, around 1%, and weakly correlated across qubits, quantum error correction and fault tolerance can support near-perfect computation for arbitrarily long durations [130] [249].The introduction is intentionally succinct and sketchy, highlighting the main ideas rather than covering the full subject or surface code.Source: §21.1 · p. 195

21.2 Classical error-correction

For independent bit-flip noise, three-bit repetition reduces the error rate from p to less than 3p^2, and concatenation below p≤1/3 suppresses errors double-exponentially while increasing code length exponentially.With k = 2 log log n concatenation levels, polynomially many protected bits and time-steps have negligible total failure probability with only a polylogarithmic physical-bit overhead.Source: §21.2 · p. 196

21.3 Quantum errors

Quantum error correction is harder because no-cloning prevents simple repetition, errors form a continuous family, and direct correctness measurements can collapse states.Expanding arbitrary errors in the Pauli basis means correcting bit flips, phase flips, and their product suffices to correct all single- and multi-qubit errors by linearity.Source: §21.3 · pp. 196–197

21.4 Quantum error-correcting codes

Shor’s 9-qubit code encodes one logical qubit and corrects any single-qubit Pauli error by measuring bit- and phase-error syndromes, then applying conditional X and Z corrections.Syndrome measurement discretizes general errors into Pauli cases, but encoding and correction add qubits and error locations, so the physical error rate must be sufficiently low to yield a net benefit.Source: §21.4 · pp. 197–199

21.5 Fault-tolerant quantum computation

Fault-tolerant computation must operate directly on encoded qubits and prevent correction procedures from spreading more errors than they remove.Steane’s 7-qubit code [245] supports transversal logical H and CNOT operations, while fault-tolerant T gates require additional magic-state techniques and careful error containment.Source: §21.5 · pp. 199–200

21.6 Concatenated codes and the threshold theorem

O(log log T) concatenation levels reduce logical errors below 1/T for T = poly(n), with only polylogarithmic overhead in qubits and computation time.The logical error rate becomes O((CDp)2^k), while the overhead is 2^O(log log T) = (log T)^O(1).Source: §21.6 · p. 200
Below a noise-model-, gate-set-, and code-dependent constant threshold, quantum error correction and fault-tolerant computing enable long computations without serious errors [8, 168].The threshold theorem is identified as a central response to skepticism about scalable quantum computing, though implementation is an extremely hard engineering problem.Source: §21.6 · pp. 200–201

Exercises

The exercises apply quantum codes to correct bit- and phase-flip errors, analyze Steane and Shor codes, characterize Pauli-error syndromes, and derive limits on correctable errors.They also examine depolarizing noise, concatenation, and orthogonality of corrupted codewords.Source: Exercises · pp. 201–202

21.6 Concatenated codes and the threshold theorem

Rigorous threshold lower bounds are around 0.1% under reasonable noise assumptions, while numerical evidence suggests that a few percent might be tolerable.More efficient base codes, with smaller C and D, improve the threshold; correlated noise can make protection substantially harder.Source: Exercises · p. 201

Some Useful Linear Algebra

The linear-algebra appendix introduces vector spaces, subspaces, bases, dimension, matrices, inner products, norms, and unitary maps as prerequisites for quantum computation.It defines unitaries through preservation of inner products and norms, with eigenvalues of unitary matrices having absolute value 1.Source: §A.1 · p. 205, §A.2 · p. 205, §A.3 · p. 206

A.5 Diagonalization and singular values

The appendix presents eigenvalues, similarity, Schur triangularization, diagonalization, spectral decomposition, and the equivalence between normality and unitary diagonalizability.A matrix is diagonalizable exactly when it has a linearly independent eigenbasis, and unitarily diagonalizable exactly when it has an orthonormal eigenbasis.Source: §A.5 · p. 207
The SVD decomposes any m × n matrix as A = UΣV⁻¹, with unitary U and V and nonnegative singular values in Σ.The singular values are the square roots of the eigenvalues of A∗A, and rank equals the number of nonzero singular values.Source: §A.5 · p. 208, §A.8 · p. 209

A.6 Tensor products

Tensor products combine m × n and m′ × n′ matrices into mm′ × nn′ matrices and combine d- and d′-dimensional spaces into a dd′-dimensional space.Applying A and B separately corresponds to applying A ⊗ B on the tensor-product space, with adjoints and inverses factoring componentwise.Source: §A.6 · pp. 208–209

A.7 Trace and A.8 Rank

Trace is cyclic, equals the sum of eigenvalues, and satisfies Tr(Avv∗) = v∗Av, while matrix invertibility is equivalent to full rank.The rank also equals the number of nonzero singular values, counting multiplicity.Source: §A.7 · p. 209, §A.8 · p. 209

A.9 The Pauli matrices

Pauli matrices are unitary, Hermitian, self-inverse, and pairwise anticommuting when distinct; n-qubit Paulis form an orthonormal basis for 2^n × 2^n matrices.Consequently, every such matrix has a unique expansion in the 4^n n-qubit Paulis, with real coefficients for Hermitian matrices.Source: §A.9 · p. 210

A.10 Dirac notation

Dirac notation represents states as kets and bras, expresses unitary diagonalization as sums of eigenprojectors, and preserves tensor-factor ordering under adjoints.The notes also warn against ambiguous omission of tensor-product symbols and nesting kets inside bras or kets.Source: §A.10 · p. 210

B.1 Some notation, equalities and inequalities

The mathematical preliminaries define complex-number notation, Cauchy–Schwarz, geometric-series identities, trigonometric identities, and the bound 1 + x ≤ e^x.They also introduce [n], truth-value notation, and logarithms to base 2.Source: §B.1 · pp. 211–212

B.2 Algorithms and probabilities

Asymptotic notation expresses algorithmic running-time bounds, while union and linearity of expectation, together with Markov and Chebyshev inequalities, support probabilistic analysis.Source: §B.2 · pp. 212–213
Randomized or quantum error ≤1/3 is a worst-case per-input guarantee; expected runtime can be converted to runtime 3T with error ≤1/3, and repetition reduces error to ε using n = O(log(1/ε)) trials.The union bound preserves success probability under dependent subroutine failures when each failure probability is at most 1/(3T).Source: §B.2 · p. 213

Chapter 8

Quantum-walk exercises use Johnson-graph walks for matrix comparison and amplitude amplification to search over random-walk inputs.The matrix-comparison walk marks subsets containing entries where AB and C differ, while the random-walk algorithm is treated as a deterministic computation with an auxiliary input searched by Grover or amplitude amplification.Source: Chapter 8 · p. 217

Chapters 9, 12–18

Additional hints cover Hamiltonian simulation, adversary and semidefinite-programming methods, satisfiability reductions, interactive protocols, entanglement, and nonlocal games.These passages provide techniques including Trotter-style bounds, operator-norm inequalities, primal-dual feasibility, Holevo’s theorem, singular-value decomposition, and spectral arguments.Source: Chapter 9 · p. 217, Chapter 12 · p. 218, Chapter 13 · p. 218

Chapter 10

Polynomial-method exercises derive quantum query lower bounds by symmetrizing algorithms and comparing low-degree polynomial expectations under carefully chosen input distributions.The hints identify majority, sorting, block sensitivity, and distinguishing inputs of weights N/2 and N/2 + 1 as applications.Source: Chapter 10 · p. 218

Chapter 19

Clifford-circuit exercises represent Paulis by 2n-bit strings and analyze how S, H, and CNOT gates transform those representations.The hints also state that these Clifford gates generate the relevant matrices and suggest Chernoff-bound analysis for one exercise.Source: Chapter 19 · p. 221

Chapter 21

Quantum-error-correction exercises use Pauli orthogonality, dual classical codes, and Hadamard conjugation to relate phase-flip and bit-flip errors.For an unknown encoded qubit, the suggested recovery splits 2k qubits into two k-qubit sets to recover two copies.Source: Chapter 21 · p. 221

TL;DR

Abstract

Preface from 2011

Course structure

Scope

Further reading

Attribution, acknowledgments, subsequent updates

Attribution

Acknowledgments

Subsequent updates

Quantum Computing

1.1 Introduction

1.2 Quantum mechanics

Measurement in the computational basis

Projective measurement

Observables

POVM measurement

1.2.3 Unitary evolution

1.3 Qubits and quantum memory

1.4 Elementary gates

1.5 Example: quantum teleportation

Exercises

Linear algebra and measurement

Quantum gates

Entanglement

Measurements

Foundations

Quantum communication

The Circuit Model and the Deutsch-Jozsa Algorithm

2.1 Quantum computation

2.1.1 Classical circuits

2.1.2 Quantum circuits

2.2 Universality of various sets of elementary gates

2.3 Quantum parallelism

2.4 The early algorithms

2.4.1 Deutsch-Jozsa

2.4.2 Bernstein-Vazirani

Simon’s Algorithm

3.1 The problem

3.2 The quantum algorithm

3.3.1 Upper bound

3.3.2 Lower bound

Simon’s Algorithm

Exercises

Exercises

The Fourier Transform

4.2 The Fast Fourier Transform

4.3 Application: multiplying two polynomials

4.4 The quantum Fourier transform

4.5 An efficient quantum circuit

4.6 Application: phase estimation

Exercises

Fourier and convolution

Distances and approximation

QFT approximation

Fourier-transform structure

Shor’s Factoring Algorithm

5.2 Reduction from factoring to period-finding

5.3 Shor’s period-finding algorithm

5.4 Continued fractions

Exercises

Modular exponentiation

Shor’s algorithm

RSA encryption

Hidden Subgroup Problem

6.1.2 Definition and some instances of the HSP

6.2 An efficient quantum algorithm if G is Abelian

6.2.1 Representation theory and the quantum Fourier transform

6.2.2 A general algorithm for Abelian HSP

6.3.1 The symmetric group and the graph isomorphism problem

6.3.2 Non-Abelian QFT on coset states

6.3.3 Query-efficient algorithm

Exercises

Hidden subgroup problems

Cryptography

State discrimination

Graph isomorphism

Grover’s Search Algorithm

7.1 The problem

7.2 Grover’s algorithm