Quantum Computing and Advanced

Theoretical Physics Notes

Comprehensive Foundations and Research-Level Concepts

Prepared for students and researchers in

Quantum Information Science, Quantum Error Correction, Quantum Algorithms,
and Physical Realization of Quantum Devices

t il
Pa
ay
Ud

Author:
Uday Patil
September 2025
 Copyright © 2025 Uday Patil

il
All rights reserved. No part of this publication may be reproduced, stored in a retrieval
system, or transmitted, in any form or by any means, electronic, mechanical,
t
photocopying, recording, or otherwise, without the prior written permission of the
Pa
author, except in the case of brief quotations embodied in critical articles or reviews.

The information contained herein is provided for educational and research purposes
only. While every effort has been made to ensure the accuracy and completeness of the
ay

content, the author assumes no responsibility for errors or omissions, or for damages
resulting from the use of the information contained in this work.
Ud

For permission requests, inquiries, or other correspondence, please contact:

Uday Patil
Email: [email protected]
Quantum Computing Notes 2

Contents

1 Foundations Recap: From Advanced to Research Level 4

1.1 Quantum States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Bloch Representation (Single Qubit) . . . . . . . . . . . . . . . . . . . . 4
1.3 Evolution of Quantum States . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Quantum Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Stabilizer Formalism and the Pauli Group 6

2.1 Pauli Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Stabilizer Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Logical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Example: 3-Qubit Bit-Flip Code . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 General CSS Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Quantum Error Correction and Fault Tolerance 7

3.1 Error Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Knill–Laflamme Condition . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Error Syndromes and Recovery . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Examples of Quantum Codes . . . . . . . . . . .
t
3.5 Fault-Tolerant Quantum Computation . . . . . . il .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
9
Pa
3.6 Quantum Accuracy Threshold Theorem . . . . . . . . . . . . . . . . . . . 9

4 Quantum Complexity Theory 9

4.1 Classical Complexity Classes (Recap) . . . . . . . . . . . . . . . . . . . . 10
ay

4.2 Quantum Polynomial Time (BQP) . . . . . . . . . . . . . . . . . . . . . 10

4.3 Quantum Verification (QMA) . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4 Containment Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Ud

4.5 Quantum PCP Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4.6 Other Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5 Quantum Algorithms Beyond the Basics 12

5.1 Grover’s Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Quantum Phase Estimation (QPE) . . . . . . . . . . . . . . . . . . . . . 13
5.3 Shor’s Algorithm for Factoring . . . . . . . . . . . . . . . . . . . . . . . . 13
5.4 HHL Algorithm for Linear Systems . . . . . . . . . . . . . . . . . . . . . 13
5.5 Variational Quantum Algorithms (VQAs) . . . . . . . . . . . . . . . . . . 14

6 Simulation of Quantum Systems 16

6.1 Hamiltonians in Physics . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.2 Trotter–Suzuki Product Formulas . . . . . . . . . . . . . . . . . . . . . . 17
6.3 Linear Combination of Unitaries (LCU) . . . . . . . . . . . . . . . . . . . 17
6.4 qDRIFT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.5 Modern Advances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Quantum Computing Notes 3

7 Physical Realizability and Noise Models 19

7.1 Sources of Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.2 Noise as Quantum Channels . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.3 Open-System Dynamics: Lindblad Equation . . . . . . . . . . . . . . . . 20
7.4 Noise in Physical Platforms . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.5 Noise Characterization Techniques . . . . . . . . . . . . . . . . . . . . . . 21

8 Fault-Tolerant Architectures and Quantum Error Correction in Prac-

tice 21
8.1 Logical vs. Physical Qubits . . . . . . . . . . . . . . . . . . . . . . . . . 21
8.2 Surface Code Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.3 Magic-State Distillation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.4 Architectural Proposals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.5 Resource Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

9 Quantum Algorithms Beyond the Standard Paradigms 23

9.1 Variational Quantum Algorithms (VQAs) . . . . . . . . . . . . . . . . . . 24
9.2 Quantum Approximate Optimization Algorithm (QAOA) . . . . . . . . . 24
9.3 Quantum Linear Algebra Primitives . . . . . . . . . . . . . . . . . . . . . 25
9.4 Quantum Machine Learning (QML) . . . . . . . . . . . .

il
9.5 Hybrid and Heuristic Algorithms . . . . . . . . . . . . .
t .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
25
Pa
10 Outlook and Open Problems 26
10.1 Scalability and Hardware Challenges . . . . . . . . . . . . . . . . . . . . 27
10.2 Error Correction and Fault Tolerance . . . . . . . . . . . . . . . . . . . . 27
10.3 Algorithmic Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
ay

10.4 Complexity-Theoretic Questions . . . . . . . . . . . . . . . . . . . . . . . 27

10.5 Interdisciplinary Connections . . . . . . . . . . . . . . . . . . . . . . . . 27
Ud
Quantum Computing Notes 4

1 Foundations Recap: From Advanced to Research Level

Before advancing to research-level concepts, we briefly review the rigorous mathematical
framework of quantum information theory. The goal is to move beyond the standard
“advanced” picture of pure states and unitary gates, and instead describe systems using
density matrices, open-system dynamics, and quantum channels.

1.1 Quantum States

Definition 1.1 (Hilbert Space). A quantum system is associated with a Hilbert space H
over C. A pure state is represented by a normalized vector |ψ⟩ ∈ H, i.e.

⟨ψ|ψ⟩ = 1.

For a single qubit (H ∼

= C2 ), any state is expressed as

|ψ⟩ = α |0⟩ + β |1⟩ , α, β ∈ C, |α|2 + |β|2 = 1.

Definition 1.2 (Density Operator). A density operator ρ on H is a positive semidefinite

operator with unit trace:

Remark 1.1.
ρ ≥ 0, Tr(ρ) = 1.
t il
• Pure states correspond to rank-one projectors: ρ = |ψ⟩ ⟨ψ|.
Pa
• Mixed states describe classical probability distributions over pure states:

ρ= pi ≥ 0, pi = 1.
X X
pi |ψi ⟩ ⟨ψi | ,
i i
ay

1.2 Bloch Representation (Single Qubit)

Ud

Any single-qubit density operator ρ can be expressed in the Bloch representation:

1
ρ= (I + ⃗r · ⃗σ ) ,
2
where ⃗σ = (σx , σy , σz ) are Pauli matrices, and ⃗r ∈ R3 is the Bloch vector with ∥⃗r∥ ≤ 1.

• ∥⃗r∥ = 1: pure state.

• ∥⃗r∥ < 1: mixed state.

This representation allows for a geometric visualization of qubit states as points inside
the Bloch sphere.

1.3 Evolution of Quantum States

Closed Systems. The time evolution of a closed quantum system with Hamiltonian
H is governed by the Schrödinger equation. For pure states:

|ψ(t)⟩ = U (t) |ψ(0)⟩ , U (t) = e−iHt/ℏ .

For density matrices:

ρ(t) = U (t)ρ(0)U † (t).
Quantum Computing Notes 5

Open Systems. Realistic quantum systems interact with their environment. Their
dynamics are governed by the Lindblad master equation:
i X 
ρ̇(t) = − [H, ρ] + Lk ρL†k − 21 {L†k Lk , ρ} ,
ℏ k

where Lk are Lindblad operators (noise channels) and {A, B} = AB + BA is the anti-
commutator.

1.4 Quantum Channels

Definition 1.3 (Quantum Channel). A quantum channel is a completely positive trace-
preserving (CPTP) linear map

E : B(H) → B(H),

such that

1. (Complete positivity) (E ⊗ In )(ρ) ≥ 0 for all ρ, n.

il
2. (Trace preservation) Tr(E(ρ)) = Tr(ρ) for all ρ.
t
Kraus Representation. Every quantum channel admits a representation
Pa
E(ρ) = Ki ρKi† , Ki† Ki = I,
X X

i i

where {Ki } are Kraus operators.

a y

Examples of Noise Models.

Ud

• Bit-flip channel:
E(ρ) = (1 − p)ρ + pXρX.

• Phase-flip channel:
E(ρ) = (1 − p)ρ + pZρZ.

• Depolarizing channel:

E(ρ) = (1 − p)ρ + p3 (XρX + Y ρY + ZρZ).

• Amplitude damping channel with parameter γ:

√ !
1 √ 0 0
!
γ
K0 = , K1 = .
0 1−γ 0 0

Remark 1.2. This framework of density operators, open-system dynamics, and CPTP
channels provides the rigorous foundation for research in quantum error correction, fault
tolerance, and quantum algorithms.
Quantum Computing Notes 6

2 Stabilizer Formalism and the Pauli Group

Quantum error correction and many quantum algorithms can be rigorously described
using the stabilizer formalism. This framework relies on the algebraic structure of the
Pauli group and provides a powerful language for describing quantum codes.

2.1 Pauli Group

Definition 2.1 (Pauli Group). The single-qubit Pauli matrices are defined as
0 1 0 −i 1 0 1 0
! ! ! !
σx = , σy = , σz = , I= .
1 0 i 0 0 −1 0 1
The n-qubit Pauli group Pn is defined as
Pn = {ωP1 ⊗ P2 ⊗ · · · ⊗ Pn : ω ∈ {±1, ±i}, Pj ∈ {I, X, Y, Z}}.
Remark 2.1. • Pn is a non-abelian group under matrix multiplication.
• Any two elements of Pn either commute or anticommute.
• |Pn | = 4n+1 .

2.2 Stabilizer Groups t il

Definition 2.2 (Stabilizer Group). Let S ⊆ Pn be an abelian subgroup of the Pauli group
Pa
that does not contain −I. Then S is called a stabilizer group. The associated codespace
is
n
C = {|ψ⟩ ∈ C2 : g |ψ⟩ = |ψ⟩ , ∀g ∈ S}.
ay

Theorem 2.1 (Dimension of Codespace). If S has n − k independent generators, then

dim C = 2k . In other words, the code encodes k logical qubits into n physical qubits.
Ud

2.3 Logical Operators

Definition 2.3 (Logical Operators). An operator L ∈ Pn is called a logical operator for
a stabilizer code with stabilizer group S if
1. Lg = gL ∀g ∈ S (commutes with all stabilizers),
2. L ∈
/ S (acts non-trivially on the codespace).
Logical X and Z operators implement Pauli operations on encoded qubits.

2.4 Example: 3-Qubit Bit-Flip Code

The 3-qubit bit-flip code encodes one logical qubit (k = 1) into n = 3 physical qubits.
The encoding is
|0⟩L = |000⟩ , |1⟩L = |111⟩ .
The stabilizer group is generated by
g1 = Z1 Z2 , g2 = Z2 Z3 .
• The codespace C is the simultaneous +1 eigenspace of g1 and g2 .
• Logical operators are
XL = X1 X2 X3 , ZL = Z1 Z2 Z3 .
Quantum Computing Notes 7

Error Detection. If a bit-flip Xi occurs on the i-th qubit, measuring the stabilizers
produces a unique syndrome:

Error (g1 , g2 )
I (+1, +1)
X1 (−1, +1)
X2 (−1, −1)
X3 (+1, −1)
Thus, the error can be identified and corrected.

2.5 General CSS Codes

Calderbank-Shor-Steane (CSS) codes are an important family of stabilizer codes.
Definition 2.4 (CSS Codes). A CSS code is constructed from two classical linear codes
C1 , C2 ⊆ Fn2 such that C2⊥ ⊆ C1 . Stabilizers are generated by
• Z-type operators from codewords in C1 ,
• X-type operators from codewords in C2 .

t il
Example: Steane Code. The 7-qubit Steane code is a CSS code constructed from
the classical [7, 4, 3] Hamming code. It encodes 1 logical qubit into 7 physical qubits and
Pa
corrects any single-qubit error.
Remark 2.2. The stabilizer formalism provides the algebraic foundation for quantum
error correction. It allows for efficient description of large codes and is used extensively
y

in fault-tolerant quantum computation.

a

3 Quantum Error Correction and Fault Tolerance

Ud

Quantum systems are inherently noisy and prone to decoherence. To perform reliable
quantum computation, we must encode logical qubits into many physical qubits, detect
errors, and correct them without disturbing the encoded information. This is achieved
using quantum error-correcting codes (QECCs) and fault-tolerant protocols.

3.1 Error Models

In quantum mechanics, noise processes can be expressed as elements of the Pauli group.
Since {I, X, Y, Z} form a basis for 2×2 matrices, any single-qubit error can be decomposed
as a linear combination of Pauli errors.
Definition 3.1 (Weight of an Error). For E ∈ Pn , the weight wt(E) is the number of
qubits on which E acts non-trivially.
Definition 3.2 ([[n, k, d). ]code]An[[n, k, d]] quantum code encodes k logical qubits into
n physical qubits and has distance d. Equivalently:
• It can detect any error that acts nontrivially on at most d − 1 physical qubits (i.e.
any error of weight < d).
• It can correct any error that acts nontrivially on at most ⌊(d−1)/2⌋ physical qubits.
Quantum Computing Notes 8

3.2 Knill–Laflamme Condition

Theorem 3.1 (Knill–Laflamme). A code with projector P can correct a set of errors
{Ea } if and only if
P Ea† Eb P = cab P, ∀a, b,
where cab are the entries of a Hermitian matrix.
Remark 3.1. The condition states that within the codespace, distinct errors act indistin-
guishably up to a scalar. Thus, error syndromes reveal the error without destroying the
encoded logical information.

3.3 Error Syndromes and Recovery

For a stabilizer code with stabilizer group S, each error E either commutes or anticom-
mutes with the generators gi ∈ S. Measuring {gi } yields eigenvalues ±1, forming the
error syndrome.
Definition 3.3 (Syndrome and Recovery). • The syndrome of E is the vector of
outcomes (±1, . . . , ±1).

il
• A recovery operator R is then applied such that RE |ψL ⟩ = |ψL ⟩, restoring the
logical state. t
Pa
3.4 Examples of Quantum Codes
Shor Code ([[9, 1, 3]]). Encodes 1 logical qubit into 9 physical qubits, protecting
against arbitrary single-qubit errors. It combines:
y

• Bit-flip repetition (|0⟩ 7→ |000⟩),

a

• Phase-flip repetition (|+⟩ 7→ | + ++⟩).

Ud

Steane Code ([[7, 1, 3]]). A CSS code built from the classical [7, 4, 3] Hamming code.
• Encodes 1 logical qubit.
• Corrects any single-qubit error.
• Logical Clifford gates implemented transversally.

5-Qubit Code ([[5, 1, 3]]). The smallest possible code that corrects arbitrary single-
qubit errors. Stabilizer generators are cyclic permutations of XZZXI.

Surface Code. A topological stabilizer code defined on a 2D lattice:

• Z-type plaquette operators,
• X-type star operators.
Errors correspond to string-like operators on the lattice, detected by syndromes at their
endpoints. Decoding uses minimum-weight perfect matching.
Remark 3.2. Surface codes achieve high thresholds (∼ 1%) and are the leading candi-
dates for scalable fault-tolerant quantum computing.
Quantum Computing Notes 9

3.5 Fault-Tolerant Quantum Computation

Definition 3.4 (Fault-Tolerant Gate). A logical gate is fault-tolerant if any single phys-
ical error during its implementation results in at most one error per logical block, which
remains correctable.

Techniques for Fault Tolerance.

• Transversal gates: Apply the same gate independently on each physical qubit of
a block. Prevents error propagation.

• Error-correcting teleportation: Use entanglement and Bell measurements to

both implement gates and correct errors.

• Magic-state distillation: Produces high-fidelity non-Clifford states (e.g. T-gate

resource states), enabling universal quantum computation.

3.6 Quantum Accuracy Threshold Theorem

Theorem 3.2 (Threshold Theorem). There exists a constant pth > 0 such that if the

il
physical error rate per gate p < pth , arbitrarily long quantum computations can be per-
formed with only polylogarithmic overhead in resources.
t
Pa
Remark 3.3. For practical codes like the surface code, numerical estimates give pth ≈
1%. Thus, scalable quantum computation is possible in principle, provided noise rates are
below threshold.

Remark 3.4. The accuracy threshold theorem is the cornerstone of fault-tolerant quan-
y

tum computing, showing that quantum information can be protected against decoherence
a

indefinitely with finite overhead.

Ud

Summary of Section
• Errors modeled as Pauli operators with weight.

• Knill–Laflamme condition characterizes correctable error sets.

• Stabilizer measurement yields error syndromes for recovery.

• Explicit codes: Shor, Steane, 5-qubit, surface code.

• Fault tolerance ensures errors do not spread uncontrollably.

• Threshold theorem guarantees reliable long computations below noise threshold.

4 Quantum Complexity Theory

Quantum computing is not only about building algorithms, but also about understanding
their inherent limitations. Complexity theory provides a rigorous framework for classify-
ing computational problems and analyzing what quantum computers can and cannot do
efficiently.
Quantum Computing Notes 10

4.1 Classical Complexity Classes (Recap)

Definition 4.1 (P). The class P contains decision problems solvable by a deterministic
Turing machine in polynomial time.

Definition 4.2 (NP). The class NP contains decision problems for which a given “yes”
instance has a polynomial-size certificate that can be verified in polynomial time by a
deterministic Turing machine.

Remark 4.1. The P vs NP problem remains one of the central open questions in theo-
retical computer science.

4.2 Quantum Polynomial Time (BQP)

Definition 4.3 (BQP). The class BQP (Bounded-Error Quantum Polynomial Time)
consists of all decision problems solvable by a uniform family of polynomial-size quantum
circuits such that

Pr[algorithm accepts yes-instance] ≥ 32 , Pr[algorithm accepts no-instance] ≤ 31 .

Remark 4.2. The constants 2/3 and 1/3 can be amplified to 1 − ϵ and ϵ for any ϵ > 0
by repetition. t il
Pa
Examples.

• Factoring ∈ BQP (Shor’s algorithm).

• Discrete logarithm ∈ BQP.

ay

• Simulation of local quantum systems is believed to be in BQP.

Ud

4.3 Quantum Verification (QMA)

Definition 4.4 (QMA). The class QMA (Quantum Merlin-Arthur) consists of decision
problems for which:

1. For yes-instances, there exists a polynomial-size quantum proof state |ψ⟩ such that
a polynomial-time quantum verifier accepts with probability at least 2/3.

2. For no-instances, all proofs are rejected with probability at least 2/3.

Remark 4.3. QMA is the quantum analogue of NP. Instead of a classical proof string,
Merlin provides a quantum state as a witness, and Arthur verifies using a quantum circuit.

Complete Problems.

• Local Hamiltonian problem (quantum analogue of SAT): Given a k-local Hamilto-

nian H = i Hi on n qubits, decide whether the ground state energy is ≤ a or ≥ b,
P

promised b − a ≥ 1/poly(n).

• It is QMA-complete for k ≥ 2 (Kitaev’s theorem).

Quantum Computing Notes 11

4.4 Containment Relations

P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE.

• BQP contains P and BPP (classical probabilistic polytime).

• It is unknown whether NP ⊆ BQP.

• BQP is contained in PP and hence in PSPACE.

4.5 Quantum PCP Conjecture

Definition 4.5 (Quantum PCP Conjecture). The conjecture states that approximating
the ground state energy of a local Hamiltonian within a constant additive error remains
QMA-hard.

Remark 4.4. This would imply that even verifying approximate solutions to many-body
quantum problems is intractable, analogous to the classical PCP theorem for NP.

4.6 Other Complexity Classes

QIP (Quantum Interactive Proofs).
t il
• QIP = PSPACE (Jain, Ji, Upadhyay, Watrous 2010).
Pa
• Quantum interactive proofs are no more powerful than PSPACE.

QMA(2).
ay

• QMA with two unentangled provers.

Ud

• Important in studying entanglement and separability.

PostBQP.

• Quantum polynomial time with postselection.

• Equivalent to PP (Aaronson 2005).

Summary of Section
• BQP captures quantum polynomial-time computation.

• QMA is the quantum analogue of NP, with the Local Hamiltonian problem as a
complete problem.

• BQP lies between BPP and PP.

• The Quantum PCP conjecture extends hardness of approximation to quantum sys-

tems.

• Quantum interactive proof classes connect quantum complexity with PSPACE.

Quantum Computing Notes 12

QMA PSPACE

PP
BQP

BPP

NP (unknown relation)

Known containments: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE.

Unknown: NP vs BQP, QMA vs NP.

puting. Dashed boundaries indicate unknown relations.

t il
Figure 1: Containment relations among important complexity classes in quantum com-
Pa
5 Quantum Algorithms Beyond the Basics
While basic algorithms like Deutsch–Jozsa or Simon’s illustrate quantum advantage, prac-
tical and research-relevant algorithms exploit interference and entanglement to achieve
ay

exponential or quadratic speedups. In this section, we present the rigorous framework of

the most important quantum algorithms.
Ud

5.1 Grover’s Search Algorithm

Problem. Given an unstructured database of N = 2n items and an oracle f : {0, 1}n →
{0, 1} with a unique marked item x∗ such that f (x∗ ) = 1, find x∗ .

Algorithm. Grover’s algorithm uses the iteration operator

G = (2 |ψ⟩ ⟨ψ| − I)(I − 2 |x∗ ⟩ ⟨x∗ |),

where |ψ⟩ = √1 |x⟩ is the uniform superposition.

P
N x

Analysis. Each application

√ of G rotates the state vector in a 2D subspace spanned by
{|x ⟩ , |ψ⊥ ⟩}. After O( N ) iterations, the state has amplitude close to 1 on |x∗ ⟩.
∗

Theorem √ 5.1 (Grover’s Lower Bound). Any quantum algorithm for unstructured search
requires Ω( N ) queries.

Remark 5.1. Grover’s algorithm is optimal for unstructured search and can be general-
ized to amplitude amplification.
Quantum Computing Notes 13

5.2 Quantum Phase Estimation (QPE)

Problem. Given a unitary U with eigenvector |u⟩ and eigenvalue e2πiθ , estimate θ to
m bits of precision.

Algorithm.
1. Prepare |0⟩⊗m ⊗ |u⟩.

2. Apply Hadamards on the first register.

3. Apply controlled-U 2 gates.

j

4. Apply inverse Quantum Fourier Transform (QFT).

5. Measure the first register to obtain an m-bit estimate of θ.

Applications.
• Order finding (basis of Shor’s algorithm).

• Eigenvalue estimation in quantum chemistry.

• Hamiltonian simulation.
t il
Pa
5.3 Shor’s Algorithm for Factoring
Problem. Given integer N , find its prime factorization.
ay

Reduction. Factorization reduces to order finding: for random a coprime to N , find

r = ordN (a), the least integer such that ar ≡ 1 (mod N ).
Ud

Quantum Part. Order finding is solved using QPE on the unitary

U : |x⟩ 7→ |ax mod N ⟩ .

Complexity. Runs in time poly(n), where n = log N , exponentially faster than the
best known classical algorithms.

5.4 HHL Algorithm for Linear Systems

Problem. Given a sparse, well-conditioned N × N matrix A and vector |b⟩, solve for
|x⟩ in A |x⟩ = |b⟩.

Algorithm Outline.
1. Encode |b⟩ as a quantum state.

2. Perform QPE on A to extract eigenvalues.

3. Apply conditional rotations |λ⟩ 7→ λ−1 |λ⟩.

4. Uncompute QPE to obtain |x⟩ ∝ A−1 |b⟩.

Quantum Computing Notes 14

Complexity. Time polylogarithmic in N , exponential improvement over classical algo-

rithms. However, overhead depends on condition number κ and sparsity.

Applications. Quantum machine learning (kernel methods), PDE solving, optimiza-

tion.

5.5 Variational Quantum Algorithms (VQAs)

In the Noisy Intermediate-Scale Quantum (NISQ) era, variational hybrid algorithms offer
near-term applicability.

Variational Quantum Eigensolver (VQE).

• Ansatz |ψ(θ)⟩ prepared on quantum hardware.

• Classical optimizer updates parameters θ to minimize

E(θ) = ⟨ψ(θ)| H |ψ(θ)⟩ .

• Approximates ground state energy of Hamiltonians (quantum chemistry).

t
Quantum Approximate Optimization Algorithm (QAOA). il
Pa
• For combinatorial optimization problem with cost Hamiltonian C, alternate uni-
taries:
U (γ, β) = e−iβB e−iγC ,
ay

where B = Xi .
P
i

• Parameters γ, β optimized variationally.

Ud

Remark 5.2. VQAs trade formal guarantees for practical implementability. Their per-
formance remains an active area of research.

Summary of Section
• Grover’s algorithm: quadratic speedup for unstructured search, provably optimal.

• QPE: key primitive for order finding, Hamiltonian simulation, eigenvalue problems.

• Shor’s algorithm: exponential speedup for factoring, threatens RSA cryptography.

• HHL algorithm: exponential improvement for linear systems under conditions.

• VQAs (VQE, QAOA): hybrid approaches for NISQ devices.

Quantum Computing Notes 15

Grover’s Algorithm Pseudocode

Algorithm 1: Grover’s Search Algorithm

Input: Oracle Of with marked item x∗ , N = 2n items
Output: Marked item x∗
Initialize uniform superposition |ψ⟩ = √1N N
P −1
x=0 |x⟩;
√
Compute number of iterations R = ⌊ π4 N ⌋;
for i ← 1 to R do
Apply oracle: Of |x⟩ = (−1)f (x) |x⟩;
Apply diffusion operator: D = 2 |ψ⟩ ⟨ψ| − I;
Measure in computational basis to obtain x∗ ;

|0⟩⊗n H ⊗n D ···
Of
|0⟩ ···

Quantum Phase Estimation Pseudocode

Algorithm 2: Quantum Phase Estimation

Input: Unitary U with eigenvector |u⟩, precision m
Output: Estimate θ̃ of phase θ
t il
Pa
Initialize |0⟩⊗m ⊗ |u⟩;
Apply Hadamards to first m qubits;
for j ← 0 to m − 1 do
Apply controlled-U 2 on target |u⟩;
j
ay

Apply inverse QFT on first register;

Measure first register → θ̃;
Ud

|0⟩ H •

|0⟩ H •
QF T †
.. .. .. .. ..
. . . . .
|0⟩ H •

|u⟩ U U2
m−1
Quantum Computing Notes 16

Quantum Approximate Optimization Algorithm (QAOA) Pseudocode

Algorithm 3: QAOA for Combinatorial Optimization

Input: Cost Hamiltonian C, depth p
Output: Approximate solution x
Initialize uniform state |ψ0 ⟩ = H ⊗n |0n ⟩;
for k ← 1 to p do
Apply cost unitary UC (γk ) = e−iγk C ;
Apply mixing unitary UB (βk ) = e−iβk B , B = i Xi ;
P

Measure final state |ψp ⟩ in computational basis;

Classical optimizer updates parameters (γ, β) to maximize ⟨C⟩;

6 Simulation of Quantum Systems

One of the most powerful applications of quantum computers is the simulation of quantum
systems, originally envisioned by Feynman. The goal is to efficiently approximate the time
evolution operator
U (t) = e−iHt , H Hermitian,
for physically relevant Hamiltonians. t il
Pa
6.1 Hamiltonians in Physics
Local Hamiltonians. In quantum many-body systems, the Hamiltonian typically de-
composes into local terms:
y

m
H=
X
∥Hj ∥ ≤ α,
a

Hj ,
j=1
Ud

where each Hj acts on at most k qubits (“k-local” Hamiltonian).

Examples.

• Heisenberg model:
H= (Xi Xj + Yi Yj + Zi Zj ).
X

⟨i,j⟩

• Hubbard model:

H = −t (a†iσ ajσ + h.c.) + U

X X
ni↑ ni↓ .
⟨i,j⟩,σ i

• Quantum chemistry Hamiltonians: expressed in second quantization using

fermionic creation/annihilation operators.
Quantum Computing Notes 17

6.2 Trotter–Suzuki Product Formulas

Theorem 6.1 (First-Order Trotter Formula). For H = A + B,
 r
e−iHt = lim e−iAt/r e−iBt/r .
r→∞

Theorem 6.2 (Second-Order Suzuki Formula).

 r
e−iHt = r→∞
lim e−iAt/(2r) e−iBt/r e−iAt/(2r) .

Remark 6.1. Higher-order decompositions improve accuracy at the cost of more expo-
nentials. For local Hamiltonians, gate complexity scales as poly(n, t, 1/ϵ).

6.3 Linear Combination of Unitaries (LCU)

The LCU technique simulates Hamiltonians by expressing them as a weighted sum of
unitary operators:
H= αj > 0.
X
αj Uj ,
j

Algorithm Idea.
1. Prepare superposition
P q
j αj /Λ |j⟩.
t il
Pa
2. Perform controlled-Uj .
3. Use amplitude amplification to obtain evolution under H.
Remark 6.2. LCU leads to optimal Hamiltonian simulation algorithms with complexity
ay

Õ(t∥H∥1-sum ), where
 
Ud

X 
∥H∥1-sum = min |αj | : H =
X
αj Uj .
 
j j

6.4 qDRIFT Algorithm

Definition 6.1 (qDRIFT). qDRIFT is a randomized Hamiltonian simulation algorithm:
1. Express H =
P
j hj .
2. Choose term hj at random with probability pj = ∥hj ∥/∥H∥1 , where ∥H∥1 = ∥hj ∥.
P
j
−1
3. Apply e−ihj (tpj /N )
for N steps.
Theorem 6.3 (qDRIFT Error Bound). qDRIFT simulates e−iHt with error
!
t2 ∥H∥21
ϵ=O .
N

6.5 Modern Advances

Quantum Signal Processing (QSP). Uses single-qubit rotations to implement poly-
nomial approximations of functions of H, yielding optimal Hamiltonian simulation with
complexity Õ(t∥H∥ + log(1/ϵ)).
Quantum Computing Notes 18

Quantum Walk Methods. Simulate Hamiltonians using Szegedy-type quantum walks,

useful for sparse Hamiltonians.

Applications.

• Simulation of condensed matter models.

• Quantum chemistry (molecular electronic structure).

• High-energy physics (lattice gauge theories).

Summary of Section
• Goal: approximate e−iHt for physically relevant H.

• Trotter–Suzuki: systematic product formulas.

• LCU: linear combination of unitaries with amplitude amplification.

• qDRIFT: randomized algorithm with rigorous error bound.

• QSP: near-optimal simulation scaling.

il
t
• Applications span physics, chemistry, and materials science.
Pa
Algorithm: Trotter–Suzuki Simulation

Algorithm 4: First-Order Trotter Simulation

ay

Input: Hamiltonian H = m j=1 Hj , time t, steps r

P

Output: Approximation to U (t) = e−iHt

for k ← 1 to r do
Ud

for j ← 1 to m do
Apply Uj = e−iHj t/r ;
Return product of unitaries as approximation U (t) ≈ e−iHj t/r ;
Qr Qm
k=1 j=1

Algorithm: qDRIFT Hamiltonian Simulation

Algorithm 5: qDRIFT Simulation

Input: Hamiltonian H = m j=1 hj , time t, number of steps N
P

Output: Approximation to U (t) = e−iHt

Compute probabilities pj = ∥hj ∥/∥H∥1 , where ∥H∥1 = j ∥hj ∥;
P

for k ← 1 to N do
Sample index j with probability pj ;
−1
Apply unitary Uj = e−ihj (tpj /N )
;
Return product of N unitaries as approximation to e−iHt ;
Quantum Computing Notes 19

Method Scaling Error Notes

Trotter–Suzuki O(mr), r = O(t /ϵ)
2 2
O(t /r) Simple, system-
atic; but costly
for high preci-
sion
qDRIFT O(N ), N = O(t2 ∥H∥21 /ϵ) O(t2 ∥H∥21 /N ) Randomized,
easy; less effi-
cient for large t
LCU Õ(t∥H∥1-sum + log(1/ϵ)) Exponential precision Provably ef-
ficient; needs
ancillas +
amplitude am-
plification
QSP/QSVT Õ(t∥H∥ + log(1/ϵ)) Optimal Asymptotically
best; hard to
implement in
practice

time, ϵ = error tolerance.

t il
Table 1: Compact comparison of Hamiltonian simulation methods. m = local terms, t =
Pa
7 Physical Realizability and Noise Models
In practice, quantum information is carried by physical systems such as superconduct-
ay

ing qubits, trapped ions, photons, or spins. Unlike the idealized mathematical model of
unitary evolution, real devices are subject to decoherence, control errors, and environ-
mental interactions. This section formalizes noise models and connects them to physical
Ud

realizability.

7.1 Sources of Noise

Decoherence. Loss of quantum coherence due to entanglement with uncontrolled en-
vironment degrees of freedom.

Relaxation (T1 decay). Spontaneous emission from excited to ground state, |1⟩ →
|0⟩, with characteristic time T1 .

Dephasing (T2 decay). Random phase kicks cause off-diagonal terms in ρ to decay
with time constant T2 .

Gate imperfections. Over/under-rotation, crosstalk, and calibration errors in unitary

gates.

Measurement errors. Imperfect projective measurement, state-dependent detection

efficiency.
Quantum Computing Notes 20

7.2 Noise as Quantum Channels

Noise processes are described as completely positive trace-preserving (CPTP) maps.

Bit-flip channel.
E(ρ) = (1 − p)ρ + pXρX.

Phase-flip channel.
E(ρ) = (1 − p)ρ + pZρZ.

Depolarizing channel.

E(ρ) = (1 − p)ρ + p3 (XρX + Y ρY + ZρZ).

Amplitude damping (energy relaxation).

√ !
1 √ 0 0
!
γ
K0 = , K1 = , E(ρ) = K0 ρK0† + K1 ρK1† .
0 1−γ 0 0

7.3 Open-System Dynamics: Lindblad Equation

t il
Theorem 7.1 (Lindblad Master Equation). The most general Markovian dynamics of a
Pa
quantum state ρ(t) is given by

dρ X 
= −i[H, ρ] + Lk ρL†k − 12 {L†k Lk , ρ} ,
dt
ay

where Lk are Lindblad operators.

√
Ud

Remark 7.1. • Lk = γ σ− models amplitude damping.

√
• Lk = γ Z models pure dephasing.

• This framework underlies quantum optics and solid-state decoherence theory.

7.4 Noise in Physical Platforms

Superconducting Qubits.

• Dominant noise: relaxation (T1 ∼ 50–200 µs), dephasing (T2 ∼ 50–200 µs).

• Two-qubit gates: 10−3 to 10−2 error rates.

• Measurement: 95–99% fidelity.

Trapped Ions.

• Long coherence times (T2 ∼ 1–10 seconds).

• High-fidelity gates (∼ 10−3 ).

• Slow gate speed compared to superconducting qubits.

Quantum Computing Notes 21

Photonic Qubits.

• Robust to decoherence (no T1 /T2 issues).

• Main challenge: photon loss, imperfect detectors.

• Natural for quantum communication.

Spin Qubits (NV centers, quantum dots).

• Long coherence at low temperatures.

• Coupling to nuclear spin bath induces dephasing.

7.5 Noise Characterization Techniques

Quantum Process Tomography (QPT). Full reconstruction of channel E by prepar-
ing basis states and measuring outputs. Exponential overhead.

Randomized Benchmarking (RB). Applies random Clifford sequences to estimate

average gate fidelity. Scales efficiently.
t il
Cross-Entropy Benchmarking (XEB). Used in quantum supremacy experiments
Pa
to quantify fidelity of random circuit sampling.

Summary of Section
ay

• Noise arises from decoherence, control imperfections, and measurement errors.

• Noise channels modeled as CPTP maps; amplitude damping and depolarizing chan-
Ud

nels are standard.

• Lindblad equation gives general Markovian open-system dynamics.

• Noise differs by platform: superconducting qubits, trapped ions, photons, spins.

• Characterization via tomography, benchmarking, and cross-entropy fidelity.

8 Fault-Tolerant Architectures and Quantum Error Correction

in Practice
Having developed the theory of quantum error correction and noise, we now discuss
practical architectures for fault-tolerant quantum computing (FTQC). The central idea is
to encode logical qubits into error-correcting codes and design architectures that maintain
error rates below threshold.

8.1 Logical vs. Physical Qubits

Definition 8.1 (Logical Qubit). A logical qubit is encoded into multiple physical qubits
using a quantum error-correcting code. Logical operations are implemented by fault-
tolerant gate constructions.
Quantum Computing Notes 22

Overhead. To achieve target logical error rate pL , the required number of physical
qubits per logical qubit scales as
 
nphys = O d2 ,

for surface codes, where d is the code distance.

8.2 Surface Code Architecture

Structure.

• Qubits placed on a 2D square lattice.

• Stabilizers: plaquette (Z-type) and star (X-type) operators.

• Syndrome extraction via repeated measurements.

Threshold. The surface code has a high accuracy threshold

pth ≈ 1%.

d:
t il
If physical error rate p < pth , logical errors are suppressed exponentially in code distance
Pa
! d+1
p 2
pL ≈ .
pth

Decoding. Minimum-weight perfect matching (MWPM) identifies error chains from

ay

syndrome patterns. Efficient classical algorithms allow real-time decoding.

Ud

8.3 Magic-State Distillation

Clifford gates are transversal in many stabilizer codes, but universal quantum computa-
tion requires a non-Clifford gate, such as T = eiπZ/8 .

Magic States. A noisy |T ⟩ state can be purified using distillation protocols to yield
high-fidelity |T ⟩.

Overhead. Magic-state distillation is resource-intensive, requiring thousands of physi-

cal qubits per logical T gate at current noise levels.

8.4 Architectural Proposals

Superconducting Surface Code Lattices.

• 2D arrays of transmons with nearest-neighbor connectivity.

• Demonstrated small-distance surface codes (distance d = 3).

• Scaling roadmap: millions of qubits for practical FTQC.

Quantum Computing Notes 23

Trapped-Ion Modular Architectures.

• Chains of ions as logical qubit registers.

• Photonic interconnects for modular scaling.

Photonic Fault Tolerance.

• Cluster-state quantum computing.

• Error correction via bosonic codes (cat codes, GKP codes).

8.5 Resource Estimates

Example: Factoring a 2048-bit RSA modulus.

• Requires ∼ 108 physical qubits using surface code with realistic error rates (10−3 ).

• Runtime: months on early FTQC devices.

il
Example: Quantum Chemistry Simulation (FeMoco).
t
• Estimated ∼ 106 –107 physical qubits for chemically relevant precision.
Pa
Summary of Section
• Logical qubits are encoded in large blocks of physical qubits.
y

• Surface codes dominate due to high threshold (∼ 1%) and locality.

a

• Fault tolerance requires both transversal Clifford gates and magic-state distillation
for universality.
Ud

• Practical architectures: superconducting lattices, trapped-ion modules, photonic

cluster states.

• Current resource estimates: millions to hundreds of millions of qubits for useful

FTQC tasks.

9 Quantum Algorithms Beyond the Standard Paradigms

Having discussed foundational algorithms, we now survey advanced and emerging quan-
tum algorithms that extend beyond the standard paradigms of search and Fourier-based
techniques. These methods leverage hybrid quantum–classical schemes, variational prin-
ciples, and linear-algebraic primitives.
Quantum Computing Notes 24

Legend:
Data qubit (edge)
X-star stabilizer (vertex)
Z-plaquette stabilizer (face)

Figure 2: Surface-code fragment (3×3 plaquettes). Qubits live on edges (small circles).
Blue face boxes denote Z-type plaquette stabilizers (product of Z on the four adjacent
edge qubits). Red star symbols denote X-type vertex (star) stabilizers (product of X on
adjacent edge qubits).

9.1 Variational Quantum Algorithms (VQAs)

Motivation. Near-term devices (NISQ era) cannot support full error correction, but

with classical optimization.

t il
can implement shallow circuits. VQAs exploit parametrized quantum circuits combined
Pa
Definition 9.1 (Parameterized Quantum Circuit). A variational ansatz is a circuit
p
U (θ) = e−iθj Hj ,
Y
ay

j=1

with tunable parameters θ optimized to minimize an objective.

Ud

Variational Quantum Eigensolver (VQE).

1. Prepare state |ψ(θ)⟩ = U (θ) |0⟩.

2. Measure expectation ⟨H⟩θ for Hamiltonian H.

3. Update θ via classical optimizer (gradient-based or gradient-free).

Applications. Quantum chemistry (ground-state energies), condensed-matter models.

Limitations. Barren plateaus (vanishing gradients), optimizer noise sensitivity.

9.2 Quantum Approximate Optimization Algorithm (QAOA)

Structure. Given cost Hamiltonian C and mixer Hamiltonian B, define
p
|ψ(γ, β)⟩ = e−iβj B e−iγj C |+⟩⊗n .
Y

j=1

Applications. Combinatorial optimization: Max-Cut, portfolio optimization, schedul-

ing.
Quantum Computing Notes 25

Performance. Provable guarantees for shallow depth (p = 1) on special cases, heuristic

otherwise.

9.3 Quantum Linear Algebra Primitives

Harrow–Hassidim–Lloyd (HHL) Algorithm. Solves A⃗x = ⃗b in time polylogarith-

mic in dimension N under sparsity and condition-number assumptions.

Theorem 9.1 (HHL Complexity). For A sparse and well-conditioned, HHL outputs |x⟩
such that A |x⟩ ≈ |b⟩ in time
O(κ2 polylog(N )/ϵ),
where κ is condition number.

Applications. Machine learning (least-squares, SVMs), differential equations.

Limitations. Input/output bottleneck: state preparation and readout scale poorly.

9.4 Quantum Machine Learning (QML)

t il
Kernel Methods. Quantum circuits define implicit feature maps

ϕ : x 7→ |ψ(x)⟩ ∈ H,
Pa
allowing quantum kernel estimation.

Quantum Neural Networks (QNNs). Parameterized quantum circuits trained anal-

ay

ogously to classical neural networks. Still exploratory due to barren plateau issues.
Ud

Hybrid QML. Combine classical pre-/post-processing with quantum feature extrac-

tion.

9.5 Hybrid and Heuristic Algorithms

Quantum-Inspired Classical Algorithms. Some ideas from quantum algorithms
(e.g., randomized linear algebra) yield new classical algorithms with improved efficiency.

Quantum Heuristics. Many NISQ algorithms lack rigorous guarantees but show em-
pirical speedups in small experiments.

Summary of Section
• VQAs (VQE, QAOA) bridge near-term hardware with useful tasks.

• HHL and linear-algebraic primitives underpin potential exponential speedups in

scientific computing.

• QML explores quantum-enhanced kernels, quantum neural networks, and hybrid

models.
Quantum Computing Notes 26

• Current algorithms face challenges: barren plateaus, noise, and input/output bot-
tlenecks.

• Long-term promise lies in fault-tolerant algorithms, but near-term innovation in

hybrid schemes may yield practical advantage.

Algorithm: Variational Quantum Eigensolver (VQE)

Algorithm 6: VQE for Ground-State Energy Estimation

Input: Hamiltonian H, parametrized ansatz U (θ), initial parameters θ0
Output: Approximate ground-state energy E0
Initialize θ ← θ0 ;
while not converged do
Prepare trial state |ψ(θ)⟩ = U (θ) |0⟩;
Measure expectation value E(θ) = ⟨ψ(θ)| H |ψ(θ)⟩;
Use classical optimizer (e.g., gradient descent, Nelder–Mead) to update θ;
Return E(θ) as approximation to ground-state energy E0 ;

Algorithm: Harrow–Hassidim–Lloyd (HHL)

t il
Algorithm 7: Quantum Algorithm for Solving Linear Systems A⃗x = ⃗b
Pa
Input: Sparse Hermitian matrix A, normalized vector |b⟩, error tolerance ϵ
Output: Quantum state |x⟩ proportional to A−1 |b⟩
1. Prepare input state |b⟩.
ay

2. Apply Quantum Phase Estimation (QPE) on A to obtain eigenvalues λj in an

ancilla register.
Ud

q
3. Perform controlled rotation on ancilla: |λj ⟩ 7→ 1 − (C/λj )2 |0⟩ + (C/λj ) |1⟩,
where C is a normalization constant.

4. Uncompute QPE to disentangle eigenvalue register.

5. Measure ancilla qubit; post-select on outcome |1⟩.

Output state is
X βj
|x⟩ ∝ |uj ⟩ ,
j λj
where A |uj ⟩ = λj |uj ⟩ and |b⟩ = βj |uj ⟩.
P
j

10 Outlook and Open Problems

Quantum computing has reached a stage where theoretical foundations are well devel-
oped, experimental demonstrations are advancing rapidly, and the first signs of quantum
advantage have appeared. Yet, many open challenges remain before fault-tolerant quan-
tum computing becomes a practical reality.
Quantum Computing Notes 27

10.1 Scalability and Hardware Challenges

• Qubit scaling. Current devices have 50–1000 qubits, while fault-tolerant applica-
tions require millions.

• Connectivity. Many platforms (e.g., superconducting qubits) have limited nearest-

neighbor connectivity; scalable architectures must address routing overhead.

• Cryogenics and infrastructure. Large-scale superconducting processors require

complex cooling and wiring at milliKelvin temperatures.

10.2 Error Correction and Fault Tolerance

• Threshold improvements. Surface codes dominate, but better codes (LDPC
quantum codes, holographic codes) promise lower overhead.

• Decoding algorithms. Efficient, parallel decoders are essential for real-time fault-
tolerant operation.

• Resource reduction. Magic-state distillation remains a major bottleneck for

universal quantum computation.

10.3 Algorithmic Directions

t il
Pa
• Hybrid algorithms. Variational methods (VQE, QAOA) need rigorous complex-
ity guarantees and better optimization strategies.

• Quantum machine learning. Understanding when and why quantum models

ay

outperform classical ML remains an open question.

• Quantum simulation. Developing near-term algorithms for condensed matter,

Ud

quantum chemistry, and high-energy physics is a central goal.

10.4 Complexity-Theoretic Questions

• Quantum supremacy vs. practical advantage. Random circuit sampling has
shown separation, but finding problems of real-world value with clear complexity-
theoretic justification remains open.

• Classical simulation boundaries. Identifying precisely where classical tensor-

network or Monte Carlo methods fail is crucial.

• Relationship of BQP to classical classes. It is unknown whether BQP ⊆ PH

or whether BQP truly extends beyond the Polynomial Hierarchy.

10.5 Interdisciplinary Connections

• High-energy physics. Quantum simulation of lattice gauge theories could provide
new insights into confinement and QCD.

• Condensed matter. Studying strongly correlated systems remains a central mo-

tivation for quantum simulation.
Quantum Computing Notes 28

• Quantum gravity and information. Connections between holography, entan-

glement, and quantum error correction are fertile ground for research.

Summary of Section
• Hardware: scaling to millions of qubits with robust connectivity is a fundamental
challenge.

• Fault tolerance: surface codes dominate, but new codes and decoding methods are
actively explored.

• Algorithms: hybrid, machine learning, and simulation methods need better theo-
retical guarantees and benchmarks.

• Complexity: quantum supremacy is demonstrated, but practical quantum advan-

tage with clear theoretical justification is still elusive.

• Interdisciplinary impact: quantum computing is tightly connected to condensed

matter, high-energy physics, and quantum gravity.

Concluding Remarks
t il
Quantum computing stands today at a remarkable crossroads. On the one hand, the
Pa
mathematical foundations are rigorous, the power of quantum algorithms is established,
and experimental demonstrations are steadily advancing. On the other hand, immense
challenges remain in scaling devices, controlling noise, and proving practical quantum
advantage.
y

For students and researchers, this duality is both a challenge and an opportunity. The
a

challenge is to push beyond current limitations in hardware, error correction, and algo-
rithm design. The opportunity is to participate in a scientific and technological revolution
Ud

that not only promises new computational power but also reshapes our understanding of
quantum physics itself.
The path to fault-tolerant quantum computation is long, but the progress of the past
three decades suggests that it is achievable. As theory and experiment continue to inform
each other, quantum computing is poised to transform fields from chemistry and materials
science to optimization, cryptography, and fundamental physics. These notes have aimed
to provide a rigorous but accessible foundation for this journey, equipping the reader with
the tools and perspective to contribute to the unfolding future of quantum technologies.

Exercises
The following exercises are designed to reinforce key concepts and provide practice in
both theoretical and practical aspects of quantum computing.

Basic Exercises
Exercise 10.1. Show that the Hadamard gate H satisfies H 2 = I and determine its
eigenvalues and eigenvectors.
Quantum Computing Notes 29

Exercise 10.2. Prove that any single-qubit unitary can be expressed (up to global phase)
as
U (α, β, γ) = eiα Rz (β)Rx (γ)Rz (δ).
Exercise 10.3. Compute the matrix representation of the Pauli group on one qubit. Show
explicitly that {I, X, Y, Z} form a basis for 2 × 2 Hermitian matrices.
Exercise 10.4. Show that the Bell state |Φ+ ⟩ = √12 (|00⟩ + |11⟩) is maximally entangled
by computing the reduced density matrix of one qubit.
Exercise 10.5. Verify that the CNOT gate is both unitary and Hermitian. What is its
eigenvalue spectrum?
Exercise 10.6. Demonstrate that measurement in the computational basis destroys co-
herence by applying it to the state √12 (|0⟩ + |1⟩).
Exercise 10.7. Write the quantum circuit for the 2-qubit Deutsch algorithm and compute
the output states for constant and balanced oracles.

Intermediate Exercises

1
il
Exercise 10.8. Use the Baker–Campbell–Hausdorff formula to show that
t
e−iAt e−iBt = e−i(A+B)t− 2 [A,B]t
2 +O(t3 )
.
Pa
Exercise 10.9. Simulate Grover’s algorithm for√n = 4 qubits and a marked state |1011⟩.
Verify the number of iterations predicted by π/4 N .
Exercise 10.10. Show that the Kraus operators for amplitude damping satisfy the com-
y

pleteness relation
a

K0† K0 + K1† K1 = I.
Ud

Exercise 10.11. Derive the expression for the error probability of a distance-d repetition
code under independent bit-flip noise of probability p.
Exercise 10.12. Prove that the QFT (Quantum Fourier Transform) on n qubits can be
implemented using O(n2 ) gates.

Advanced Exercises
Exercise 10.13. Implement the Lindblad master equation numerically for a single qubit
√
with Hamiltonian H = ω2 Z and pure dephasing L = γZ. Plot the decay of off-diagonal
elements of ρ(t).
Exercise 10.14. Consider the surface code on a d = 3 lattice. Enumerate the stabilizer
generators and logical operators. Show explicitly that there are two logical operators X, Z.
Exercise 10.15. Analyze the complexity of the HHL algorithm when the condition number
κ scales polynomially vs. exponentially with system size N .
Exercise 10.16. Derive the gradient expression for a parametrized quantum circuit
(ansatz) using the parameter-shift rule:
∂ 1 
⟨0|U † (θ)HU (θ)|0⟩ = f (θ + π2 ) − f (θ − π2 ) .
∂θ 2
Quantum Computing Notes 30

Exercise 10.17. Discuss why quantum machine learning models can suffer from barren
plateaus. Provide a proof sketch that the variance of gradients decays exponentially with
n for deep random circuits.

Exercise 10.18. Show that Shor’s factoring algorithm requires O((log N )3 ) elementary
gates for an N -bit integer (ignoring error correction). Discuss the practical bottlenecks
when implemented on near-term hardware.

References

References
[1] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information,
Cambridge University Press, 2010.

[2] J. Preskill, Lecture Notes for Physics 229: Quantum Information and Computation,
California Institute of Technology, 1998.

[3] D. Gottesman, Stabilizer Codes and Quantum Error Correction, Ph.D. Thesis, Cal-
tech, 1997.
t il
[4] P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” Phys.
Pa
Rev. A, vol. 52, no. 4, pp. R2493–R2496, 1995.

[5] A. M. Steane, “Error correcting codes in quantum theory,” Phys. Rev. Lett., vol. 77,
no. 5, pp. 793–797, 1996.
ay

[6] A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,”

Phys. Rev. A, vol. 54, pp. 1098–1105, 1996.
Ud

[7] E. Knill and R. Laflamme, “Theory of quantum error-correcting codes,” Phys. Rev.
A, vol. 55, no. 2, pp. 900–911, 1997.

[8] D. Aharonov and M. Ben-Or, “Fault-tolerant quantum computation with constant

error,” in Proc. 29th ACM Symposium on Theory of Computing, pp. 176–188, 1997.

[9] D. Gottesman, “Theory of fault-tolerant quantum computation,” Phys. Rev. A, vol.

57, no. 1, pp. 127–137, 1998.

[10] R. Raussendorf, J. Harrington, and K. Goyal, “Fault-tolerant quantum computation

with high threshold in two dimensions,” Phys. Rev. Lett., vol. 98, p. 190504, 2007.

[11] A. Kitaev, “Fault-tolerant quantum computation by anyons,” Annals of Physics, vol.

303, no. 1, pp. 2–30, 2003.

[12] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: To-

wards practical large-scale quantum computation,” Phys. Rev. A, vol. 86, p. 032324,
2012.

[13] S. Bravyi and A. Kitaev, “Quantum codes on a lattice with boundary,” arXiv:quant-
ph/9811052, 1998.
Quantum Computing Notes 31

[14] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proc.
28th ACM Symposium on Theory of Computing, pp. 212–219, 1996.

[15] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete loga-
rithms on a quantum computer,” SIAM J. Comput., vol. 26, no. 5, pp. 1484–1509,
1997.

[16] A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorithm for linear systems
of equations,” Phys. Rev. Lett., vol. 103, p. 150502, 2009.

[17] A. Peruzzo et al., “A variational eigenvalue solver on a quantum processor,” Nature

Commun., vol. 5, p. 4213, 2014.

[18] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization

algorithm,” arXiv:1411.4028, 2014.

[19] R. P. Feynman, “Simulating physics with computers,” Int. J. Theor. Phys., vol. 21,
pp. 467–488, 1982.

[20] S. Lloyd, “Universal quantum simulators,” Science, vol. 273, no. 5278, pp. 1073–1078,
1996.

Phys., vol. 294, pp. 581–603, 2010.

t il
[21] A. M. Childs, “Simulating quantum systems by quantum walks,” Commun. Math.
Pa
[22] D. W. Berry, A. M. Childs, R. Cleve, et al., “Simulating Hamiltonian dynamics with
a truncated Taylor series,” Phys. Rev. Lett., vol. 114, p. 090502, 2015.
ay

[23] B. Schumacher and M. A. Nielsen, “Quantum data processing and error correction,”
Phys. Rev. A, vol. 54, no. 4, pp. 2629–2635, 1996.
Ud

[24] S. J. Devitt, W. J. Munro, and K. Nemoto, “Quantum error correction for beginners,”
Rep. Prog. Phys., vol. 76, p. 076001, 2013.

[25] P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for con-
catenated distance-3 codes,” Quantum Inf. Comput., vol. 6, no. 2, pp. 97–165, 2006.

[26] S. Aaronson, “Quantum computing, postselection, and probabilistic polynomial-

time,” Proc. R. Soc. A, vol. 461, pp. 3473–3482, 2005.

[27] R. Jain, Z. Ji, S. Upadhyay, and J. Watrous, “QIP = PSPACE,” J. ACM, vol. 58,
no. 6, p. 30, 2011.

[28] M. B. Hastings, J. Haah, et al., “Quantum LDPC codes with good soundness,”
Nature Phys., vol. 17, pp. 1166–1171, 2021.

[29] E. T. Campbell, B. M. Terhal, and C. Vuillot, “Roads towards fault-tolerant universal

quantum computation,” Nature, vol. 549, pp. 172–179, 2017.