Course Overview

1. Classical Complexity: P and NP
2. Circuit Families and Uniformity
3. Probabilistic Complexity: BPP and PP
4. Quantum Complexity: BQP
5. Quantum Verification: QMA
6. Oracle Separations and Grover

Problem Types

In theoretical computer science, we treat computations as procedures for rewriting strings. There are two main types of jobs: solve a function problem or a decision problem.

• Function problem: output a string based on an input string.
• Decision problem: output true/false for a logical proposition.

Why Decision Problems?

While both problem types are important, complexity theory focuses primarily on decision problems.

This is not a real restriction: any function problem can be solved by asking polynomially many decision questions. For example, to compute a function \(f\) with output length \(m(n)\), we can ask \(m(n)\) questions of the form “Is the \(i\)-th bit of \(f(x)\) equal to 1?”

Since this overhead is only polynomial, complexity classes defined for decision problems naturally extend to function problems.

Strings and Alphabets

We define strings in terms of an alphabet. An alphabet is simply a finite set of symbols. We frequently use the alphabet \(\mathbb{B} = \{0, 1\}\), which we call the binary alphabet.

A string is a sequence of characters from some specified alphabet. A ‘binary’ string (a.k.a. bitstring) is a string over the binary alphabet. The length of a string is the number of symbols in the string. The set of all strings over an alphabet \(\Sigma\) is denoted by \(\Sigma^*\).

Decision Problems and Languages

A language over an alphabet \(\Sigma\) is a set \(L \subseteq \Sigma^*\). Every decision problem corresponds to a language: the set of strings for which the answer is YES.

For example:

• PRIMES = {binary encodings of prime numbers}
• SAT = {encodings of satisfiable Boolean formulas}
• CONNECTED = {encodings of connected graphs}

The fundamental computational question becomes: is \(x \in L\)? This is called the membership problem for language \(L\).

Computational Models

To study what can be computed and how efficiently, we need a formal model of computation. The Turing machine, introduced by Alan Turing in 1936, provides this foundation.

A Turing machine is an idealized computing device that:

• reads and writes symbols on an infinite tape,
• transitions between states based on what it reads, and
• may halt in an accepting or rejecting state, or run forever.

Recognizing vs Deciding

A Turing machine recognizes a language \(L\) if it accepts exactly the strings in \(L\). It may reject or loop forever on strings not in \(L\).

A Turing machine decides a language \(L\) if it recognizes \(L\) and halts on all inputs. Machines that decide languages are called deciders.

For complexity theory, we focus exclusively on deciders, since we want to measure the time taken to solve problems.

Turing Machine Definition

TM Semantics

Informally, a Turing machine (TM) operates as follows.

• Starting configuration: the TM begins in state \(q_0\) and is located at the leftmost cell of the tape.
  • This is tape location \(0\) and the cell to the right of location \(n\) is location \(n+1\).
• Execution: repeatedly apply the transition function.
  • TM writes symbol to current tape cell, moves left/right, and changes state. All choices determined by present state and symbol on current tape cell.
• Halting: when the TM reaches either the state \(q_{\text{accept}}\) or \(q_{\text{reject}}\), the transition function is not applied and the machine stops immediately.

Computation

A configuration of a Turing machine is a complete description of its current state: the current state, the tape contents, and the head position.

A computation is a sequence of configurations, where each configuration follows from the previous one by applying the transition function \(\delta\). The machine starts in configuration \((q_0, x, 0)\) where \(x\) is the input string.

The machine accepts input \(x\) if the computation eventually reaches a configuration with state \(q_{\text{accept}}\). It rejects if it reaches state \(q_{\text{reject}}\). It loops if the computation never halts.

Recognizing and Deciding Languages

Notice that a decider is guaranteed to halt on all inputs.

Time Complexity

To analyze efficiency, we count the number of steps a Turing machine takes.

The Class P

Formally, \(L \in \mathsf{P}\) if there exists a decider \(M\) and polynomial \(p\) such that \[ T_M(n) = O(p(n)). \]

Big O Notation

Why Polynomials?

Two reasons:

Feasibility: polynomials grow moderately, unlike exponentials. Thus polynomial-time algorithms are, generally speaking, usable.

Composition: if \(p, q\) are polynomials, then so is \(p \circ q\). Thus composing two polynomial-time algorithms produces another polynomial-time algorithm.

The Class NP

\(L \in\mathsf{NP}\) if there exists a polynomial-time verifier \(V\) and polynomial \(p\) such that:

\[x \in L \iff \exists w \in \{0,1\}^{p(|x|)} : V(x,w) = 1\]

NP-Completeness

The hardest problems in NP:

Cook-Levin Theorem (1971): The SAT problem – determine if a logical proposition (collection of AND, OR, and NOT) can be satisfied by an assignment of truth values to atomic statements – is NP-complete

Canonical NP-complete problems

• SAT: Is a Boolean formula satisfiable?
• 3-SAT: SAT restricted to 3-CNF formulas
  
• CLIQUE: Does graph G have a k-clique?
• VERTEX-COVER: Does G have a vertex cover of size k?
• HAMILTONIAN-PATH: Does G have a path visiting each vertex once?
• 3-COLORING: Can G be colored with 3 colors?

Significance:

• If any NP-complete problem is in P, then P = NP
• Thousands of natural problems are NP-complete
• Reduction structure maps out computational difficulty

Beyond Turing Machines

While Turing machines are our canonical model, the Boolean circuit model offers some compelling advantages.

• Non-uniformity: Different circuits for different input sizes.
• Parallelism: Identify which operations logically depend on one another.
• Lower bounds: The rigidity of circuits makes it easier to assess constraints.

Boolean Circuits

The size of a circuit is the number of gates. The depth is the longest path from input to output.

Circuit Families

A single circuit handles inputs of fixed size. For languages, we need a family of circuits.

A circuit family decides language \(L\) if: \[x \in L \Rightarrow C_{|x|}(x) = 1 \text{ \& } x \notin L \Rightarrow C_{|x|}(x) = 0\]

Uniformity

Without restrictions, circuit families are too powerful—they can decide undecidable languages!

(This is because you can encode lookup tables.)

Key insight: Uniform circuit families ≈ Turing machines

Circuit Complexity Classes

Note: P/poly includes non-uniform families, so P ⊆ P/poly.

Also: ‘uniformity’ has various definitions in the literature, but consistently requires that circuits can be generated by an efficient algorithm.

The disagreements center on what notion of efficiency is appropriate - polynomial time, logarithmic space, or even more restricted classes.

Randomized Computation

Real algorithms often use randomness effectively. We model this by giving Turing machines access to random bits.

For PTM \(M\) and input \(x\):

• \(\Pr[M(x) = 1]\) = probability \(M\) accepts \(x\)
• Probability over all possible random tapes

Bounded-Error Probabilistic Polynomial Time

\(L \in\mathsf{BPP}\) if there exists polynomial-time PTM \(M\) such that:

• \(x \in L \Rightarrow \Pr[M(x) = 1] \geq 2/3\)
• \(x \notin L \Rightarrow \Pr[M(x) = 1] \leq 1/3\)

The constants 2/3 and 1/3 are arbitrary; any constants with a gap work. Choosing 2/3 and 1/3 is just a convention.

Error Amplification

The error probability in BPP can be made exponentially small:

Proof idea: Run the original algorithm multiple times and take majority vote.

Probabilistic Polynomial Time

\(L \in\mathsf{PP}\) if there exists polynomial-time PTM \(M\) such that:

• \(x \in L \Rightarrow \Pr[M(x) = 1] > 1/2\)
• \(x \notin L \Rightarrow \Pr[M(x) = 1] \leq 1/2\)

Note: The gap can be exponentially small!

Relationships

Known relationships among these classes:

1. \[\mathsf{P} \subseteq \mathsf{BPP} \subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}\]

2. \[\mathsf{NP} \subseteq \mathsf{PP}\]

Open Problems:

• Is BPP = P? (believed: yes)
• Is NP ⊆ BPP? (believed: no)

Merlin-Arthur

It is believed that MA = NP, and it is known that NP ⊆ MA ⊆ PP.

Quantum Computation Model

Quantum computers manipulate quantum states using unitary operations.

Key components:

• Quantum state: Unit vector in \(\mathbb{C}^{2^n}\)
• Quantum gates: Unitary matrices
• Measurement: Probabilistic collapse to computational basis

A quantum circuit is a sequence of quantum gates followed by measurement.

Quantum Circuits

Universal gate sets:

• {Hadamard, Phase, CNOT, Toffoli}
• {Hadamard, T, CNOT}
• Clifford + T

Bounded-Error Quantum Polynomial Time

\(L \in \mathsf{BQP}\) if there exists a uniform family of polynomial-size quantum circuits \(\{Q_n\}\) such that:

• \(x \in L \Rightarrow \Pr[Q_{|x|}(x) = 1] \geq 2/3\)
• \(x \notin L \Rightarrow \Pr[Q_{|x|}(x) = 1] \leq 1/3\)

BQP Properties

Key features:

• Error amplification works (like BPP)
• Includes all classical probabilistic computation: BPP ⊆ BQP
• Believed to be strictly larger than BPP

Known relationships: \[\mathsf{BPP} \subseteq \mathsf{BQP} \subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}\]

Quantum Speedups

Main proven quantum advantages:

1. Shor’s Algorithm (1994): Factors integers in BQP
   • Best known classical algorithm: sub-exponential
   • Breaks RSA cryptography
2. Grover’s Algorithm (1996): Inverts black-box function
   • Classical: \(O(N)\) oracle queries
   • Quantum: \(O(\sqrt{N})\) oracle queries
   • Note: this is an “oracle” separation. More on that later.

Note: Hamiltonian simulation is often noted as an advantage, but there is no proof of this. The difficulty is in formulating the computational problem. Too easy and it is in BPP. Too hard and it is not in BQP.

The Verification Problem

Can a classical verifier check quantum computations?

Challenge: Quantum states cannot be efficiently described classically

Solution: Quantum Merlin-Arthur games—the quantum analogue of MA (=NP?)

Quantum Merlin-Arthur

\(L \in \mathsf{QMA}\) if there exists polynomial-time quantum verifier \(V\) and polynomial \(p\) such that:

Completeness: \[x \in L \Rightarrow \exists |\psi\rangle \in \mathbb{C}^{2^{p(|x|)}}: \Pr[V(x, |\psi\rangle) = 1] \geq 2/3\]

Soundness: \[x \notin L \Rightarrow \forall |\psi\rangle \in \mathbb{C}^{2^{p(|x|)}}: \Pr[V(x, |\psi\rangle) = 1] \leq 1/3\]

QMA-Complete Problems

Local Hamiltonian Problem:

• Given: \(k\)-local Hamiltonian \(H = \sum_i H_i\)
• Promise: Smallest eigenvalue is either ≤ \(a\) or ≥ \(b\) (where \(b - a ≥ 1/\text{poly}(n)\))
• Decide: Is the smallest eigenvalue ≤ \(a\)?

This is the quantum analogue of SAT!

QMA Properties

Known relationships: \[\mathsf{NP} \subseteq \mathsf{QMA} \subseteq \mathsf{PP}\] \[\mathsf{BQP} \subseteq \mathsf{QMA}\]

Open problems:

• Is QMA = NP? (believed: no)
• Is QMA contained in NP? (believed: no)
• Can multiple provers help? (QMA vs QMA(2))

Oracle Machines

An oracle for language \(A\) is a “black box” that instantly answers membership queries.

Similarly define \(\mathsf{NP}^A\), \(\mathsf{BPP}^A\), \(\mathsf{BQP}^A\), etc.

Relativization

Implication: The P vs NP question doesn’t relativize—need non-relativizing techniques!

Quantum Oracle Separations

Simon’s Problem:

• Promise: Function \(f: \{0,1\}^n \to \{0,1\}^n\) is either 1-to-1 or 2-to-1 with hidden period \(s\)
• Find: The period \(s\)

Classical: Requires \(\Omega(2^{n/2})\) queries

Quantum: Requires \(O(n)\) queries

The Problem

Oracular Function Inversion Problem:

• Given: Oracle access to \(f: \{0,1\}^n \to \{0,1\}\)
• Promise: Exactly one \(x\) satisfies \(f(x) = 1\)
• Find: The satisfying assignment \(x\)

Grover’s Algorithm Details

Classical approach: Try values until finding \(f(x) = 1\)

• Expected queries: \(2^{n-1}\)
• Worst case: \(2^n - 1\)

Quantum approach (Grover):

1. Start with uniform superposition: \(|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_{x} |x\rangle\)
2. Repeat \(O(\sqrt{2^n})\) times:
   • Apply oracle: \(|x\rangle \mapsto (-1)^{f(x)} |x\rangle\)
   • Apply inversion about average
3. Measure to get solution with high probability

Result: Quadratic speedup for unstructured search!

Grover’s Algorithm - Geometric View

The key insight: Grover’s algorithm is a rotation in a 2D subspace

Define two orthogonal states:

• \(|α⟩\) = uniform superposition over non-solutions
• \(|β⟩\) = uniform superposition over solutions

For N items with 1 solution:

• \(|α⟩ = (1/\sqrt{N-1}) \sum_{x: f(x)=0} |x⟩\)
• \(|β⟩ = |x_{*}⟩\) where \(f(x_{*}) = 1\)

The 2D Subspace

Any state during Grover’s algorithm stays in \(\operatorname{span}\{|α⟩, |β⟩\}\):

\[|ψ⟩ = \cos(θ)|α⟩ + \sin(θ)|β⟩\]

Initial state: Uniform superposition \[|ψ₀⟩ = (1/√N) \sum_x |x⟩ = \sin(θ₀)|β⟩ + \cos(θ₀)|α⟩\]

Where: \(\sin(θ₀) = 1/\sqrt{N}, \cos(θ₀) = \sqrt{\frac{N-1}{N}}\)

So: \(θ₀ ≈ 1/\sqrt{N}\) (small angle for large \(N\))

Grover Operators as Reflections

Oracle operator: \(O|x⟩ = (-1)^{f(x)}|x⟩\)

• Reflects across \(|α⟩\) axis
• Flips the sign of \(|β⟩\) component
• Geometrically: \(θ → -θ\)

Diffusion operator: \(D = 2|ψ₀⟩⟨ψ₀| - I\)

• Reflects across \(|ψ₀⟩\)
• “Inversion about average”

Two Reflections = Rotation

Key geometric fact: Reflecting twice across lines separated by angle φ rotates by 2φ

In Grover:

1. Oracle reflects across \(|α⟩\)
2. Diffusion reflects across \(|ψ₀⟩\)
3. Angle between them: \(θ₀\)

Result: Each iteration rotates by \(2θ₀\)

After \(k\) iterations: \(θ_k = (2k + 1)θ₀\)

Optimal Number of Iterations

Goal: Rotate to θ ≈ π/2 (pointing at |β⟩)

(2k + 1)θ₀ ≈ π/2

Solving: k ≈ π/(4θ₀) - 1/2

Since θ₀ ≈ 1/√N:

k_optimal ≈ (π/4)√N

Measurement succeeds with high probability when θ ≈ π/2

Overshooting

If you run too many iterations:

• \(θ > π/2\) means rotating past \(|β⟩\)
• Success probability decreases
• At ≈ \((π/2)\sqrt{N}\) iterations: \(θ ≈ π\) (pointing at \(-|β⟩\))

Grover’s algorithm is periodic with period ≈ π√N

This is why knowing \(N\) (approximately) matters for the algorithm

Why Grover Can’t Be Improved

The initial angle θ₀ = arcsin(1/√N) is fixed by the problem

Each iteration can only rotate by O(θ₀) - Any unitary that doesn’t know the solution can’t rotate faster

To reach π/2 requires Ω(1/θ₀) = Ω(√N) iterations

This geometric view makes the √N bound obvious

Grover’s Optimality

Implications:

• Grover’s algorithm is optimal
• No exponential speedup for unstructured search
• Quantum computers don’t solve NP-complete problems efficiently (relative to oracle)

Complexity Class Hierarchy

\[\mathsf{P} \subseteq \mathsf{BPP} \subseteq \mathsf{BQP} \subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}\]

\[\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{QMA} \subseteq \mathsf{PP}\]

Major open questions:

• P vs NP
• BPP vs BQP
  
• NP vs QMA
• BQP vs PH (polynomial hierarchy)

Key Takeaways

1. Classical complexity provides the foundation (P, NP)
2. Randomness adds power (BPP, PP)
3. Quantum adds more power (BQP)
4. Quantum verification is harder than classical (QMA)
5. Oracle separations show quantum advantage exists
6. Grover shows the advantage has limits

Further Reading

Textbooks: - Nielsen & Chuang: Quantum Computation and Quantum Information - Arora & Barak: Computational Complexity: A Modern Approach - Watrous: The Theory of Quantum Information

Key Papers: - Shor (1997): Polynomial-time algorithms for factoring and discrete logarithms - Grover (1996): A fast quantum mechanical algorithm for database search - Kitaev (1999): Quantum NP and QMA-completeness