# Lecture Outline: Quantum Complexity Theory

## Table of Contents

## 1 What is (Computational) Complexity Theory?

Complexity theory and quantum computing

Computational complexity theory focuses on classifying **computational problems**
according to their *resource usage*, and relating classes of problems to each other.
(Wikipedia)

### 1.1 Examples of computational problems

**Multiplication**. Given a pair of integers \((m,n)\) as input, compute their product**Factoring**. Given a composite number \(n\) as input, decompose \(n\) into a product of smaller integers**Satisfaction**(SAT). Given a set of constraints on a set of Boolean variables, decide if the constraint system is satisfiable or not\((x_1 \lor x_3 \lor \neg x_4) \land (x_1 \lor \neg x_2 \lor \neg x_3 \lor x_4) \land \cdots\)

\(\lor\) Input Output \(\land\) Input Output \(\neg\) Input Output 00 0 00 0 0 1 01 1 01 0 1 0 10 1 10 0 11 1 11 1 **Counting**(#SAT). Given a set of constraints on a set of Boolean variables, compute the number of different solutions to the constraint system**True Quantified Boolean Formula**. Given a formula in quantified propositional logic where every variable is quantified by either existential or universal quantifiers at the beginning of the formula, decide if the formula evaluates to true\(\forall x_1 \exists x_2 \forall x_3 \forall x_4 ((x_1 \lor x_3 \lor \neg x_4) \land (x_1 \lor \neg x_2 \lor \neg x_3 \lor x_4) \land \cdots)\)

#### 1.1.1 Remarks

- A
*family*of problem instances, indexed by the input size Decision problems, search problems, promise problems

Decision problem: a set \(A \subseteq \Sigma^*\) where \(\Sigma = \{0,1\}\)

Promise problem: disjoint sets \(A_{yes}, A_{no} \subseteq \Sigma^*\)

### 1.2 Computational resources

#### 1.2.1 Time, space, depth, …

#### 1.2.2 Computational models

Turing machines

A brief discussion of TMs

Transition rule \(\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}\)

Configuration of a TM

- Current state \(q\)
- Current tape content
- Current head position

Classical and quantum

*circuit models*Classical circuits are not necessarily reversible

#### 1.2.3 Efficient computation

Polynomial-time (mathematically simple, model-independent)

### 1.3 P vs NP

- \(\class{P}\): A promise problem \(A\) is in \(\class{P}\) if and only if there
exists a polynomial-time
*deterministic*Turing machine that accepts every string \(x \in A_{yes}\) and rejects every string \(x \in A_{no}\) \(\class{NP}\):

*Non-deterministic*polynomial-timeNon-deterministic transition rule \(\delta: Q \times \Gamma \rightarrow 2^{Q \times \Gamma \times \{L, R\}}\)

A non-deterministic Turing machine accepts if there exists an accepting computational path

Configurations of a non-deterministic TM

A proof-verification perspective of \(\class{NP}\)

### 1.4 Church-Turing thesis

A problem is (*efficiently*) computable by an **effective method** if and only if it
is (*efficiently*) computable by a Turing machine.

Quantum computing is a candidate that disproves the *extended* Church-Turing thesis

### 1.5 Exercise 1

Let \(n\) be a composite number. It is then easy to see that \(n\) has a factor at most \(\sqrt{n}\). Does this fact give us an efficient algorithm for factoring?

### 1.6 Exercise 2

The decision version of the factoring problem asks if \(n\) has a factor less than \(k\) when given \((n, k)\) as input. Show that the factoring problem is efficiently reducible to this decision version. That is, if there is an efficient algorithm for the decision version, there is also an efficient algorithm for the standard version.

## 2 BQP: Efficient Quantum Computation

### 2.1 Definition

Let \(A = (A_{yes}, A_{no})\) be a promise problem and let \(c,s: \mathbb{N}
\rightarrow [0,1]\) be functions. Then \(A \in \class{BQP}(c,s)\) if and only if
there exists a *polynomial-time uniform family of quantum circuits* \(\{Q_n: n\in
\mathbb{N}\}\), where \(Q_n\) takes \(n\) qubits as input and outputs 1 bit, such
that

- if \(x \in A_{yes}\) then \(\Pr [ Q_{|x|}(x) = 1 ] \geq c(|x|)\), and
- if \(x \in A_{no}\) then \(\Pr [ Q_{|x|}(x) = 1 ] \leq s(|x|)\).

The class \(\class{BQP}\) is defined as \(\class{BQP} = \class{BQP}(2/3,1/3)\).

### 2.2 Error reduction for BQP

**Theorem**. Let \(p: \mathbb{N} \rightarrow \mathbb{N}\) be a polynomially bounded
function satisfying \(p(n) \ge 2\) for all \(n\). Then it holds that \(\class{BQP}\)
= \(\class{BQP}(1-2^{-p}, 2^{-p})\).

### 2.3 BQP subroutine theorem

**Theorem**. \(\class{BQP}^{\class{BQP}} = \class{BQP}\).

### 2.4 Complexity classes of oracle machines

An oracle is a subset \(B \subseteq \Sigma^*\), an oracle Turing machine with
oracle \(B\) attached is a Turing machine which may call the oracle \(B\) at
intermediate computational steps and the call counts as a **single** step.

\(\class{P}^B\), \(\class{NP}^B\), …

Oracles in the circuit model: in addition to the usual gates, we have a family of big gates \(\{O_m\}\) such that

\begin{equation*} O_{|y|}(y) = \begin{cases} 1 & y \in B,\\ 0 & y \not\in B. \end{cases} \end{equation*}For a complexity class \(\class{C}\), we define

\begin{equation*} \class{P}^{\class{C}} = \bigcup_{B \in \class{C}} \class{P}^B. \end{equation*}\(\class{NP}^\class{NP}\) and the polynomial hierarchy

In the quantum case, we adopt the form of the oracle access as \(O_m : \ket{y,a} = \ket{y, a \oplus O_m(y)}\)

### 2.5 Proof

What do we need to prove?

Two difficulties:

- The output of a BQP circuit is probabilistic
- We need to simulate the behaviour of the \(O_m\) gate on all qubits

### 2.6 Relation with classical friends

- \(\class{BPP}\): Same as \(\class{BQP}\), but uses (random) classical circuits
- \(\class{PP}\): Same as \(\class{BPP}\), but with \(c>1/2\) and \(s\le 1/2\)
- \(\class{PSPACE}\): A promise problem \(A\) is in \(\class{PSPACE}\) if and only if there exists a deterministic Turing machine running in polynomial space that accepts every string \(x \in A_{yes}\) and rejects every string \(x \in A_{no}\)
- \(\class{PH}\): Polynomial hierarchy

Meet more complexity animals at Complexity Zoo!

\(\class{P} \subseteq \class{BPP} \subseteq \class{BQP} \subseteq \class{QMA} \subseteq \class{PP} \subseteq \class{PSPACE}\)

**Conjecture**. \(\class{BQP}\) is not contained in \(\class{NP}\) and vice versa.

### 2.7 BQP vs PP

**Theorem**. \(\class{BQP} \subseteq \class{PP}\).

GapP functions

A function \(g : \Sigma^* \rightarrow \mathbb{Z}\) is a

\begin{equation*} g(x) = \# \{ y \in \Sigma^{p(|x|)}: f(x,y) = 0\} - \# \{ y \in \Sigma^{p(|x|)}: f(x,y) = 1\} = \sum_{y \in \Sigma^{p(|x|)}} (-1)^{f(x,y)}. \end{equation*}*GapP function*if there exists a polynomial \(p\) and a polynomial-time computable funcion \(f\) such that- Lemma: A promise problem is in \(\class{PP}\) if and only if there is a GapP
function \(g\) such that
- if \(x \in A_{yes}\) then \(g(x)>0\), and
- if \(x \in A_{no}\) then \(g(x)\le 0\).

- Fact: quantum computational universality of H and Toffoli
- Quantum computing is all about estimating the first entry of unitary circuits
- Encode amplitudes as GapP functions

### 2.8 Exercise 3

Write down a definition of \(\class{BQP}\) without looking at any reference. Compare it with the definition given above and see if you have missed anything.

### 2.9 Exercise 4

Prove the error reduction theorem for \(\class{BQP}\).

## 3 QMA: Quantum Merlin Arthur

### 3.1 Definition

Let \(A = (A_{yes}, A_{no})\) be a promise problem and let \(c,s: \mathbb{N}
\rightarrow [0,1]\) be functions. Then \(A \in \class{QMA}(c,s)\) if and only if
there exists a *polynomial-time uniform family of quantum circuits* \(\{Q_n: n\in
\mathbb{N}\}\), where \(Q_n\) takes \(n + m(n)\) qubits as input for some polynomial
\(m\) and outputs 1 bit, such that

*(Completeness)*if \(x \in A_{yes} \cap \Sigma^n\) then there exists an \(m(n)\)-qubit state \(\ket{\psi}\) such that \(\Pr [ Q_n(x, \ket{\psi}) = 1 ] \geq c(n)\), and*(Soundness)*if \(x \in A_{no} \cap \Sigma^n\) then for all \(m(n)\)-qubit state \(\ket{\psi}\), \(\Pr [ Q_n(x, \ket{\psi}) = 1 ] \leq s(n)\).

The class \(\class{QMA}\) is defined as \(\class{QMA}(2/3,1/3)\).

Quantization of both the witness and the circuit

### 3.2 Quantum Cook-Levin theorem

#### 3.2.1 Satisfiability and local Hamiltonian problem

**Definition**. A \(k\)-local Hamiltonian \(H\) is a summation \(H = \sum_{j=1}^m H_j\)
of local terms \(H_j\) acting on at most \(k\) qubits (out of \(n\) qubits). The
\(k\)-local Hamiltonian problem is the promise problem with

*Input*: \((H,a,b)\) where \(H\) is a \(k\)-local Hamiltonian, \(a, b\) are real numbers such that \(b - a \ge 1/poly(n)\),*Yes instances*: The smallest eigenvalue of \(H\) is at most \(a\),*No instances*: The smallest eigenvalue of \(H\) is at least \(b\).

A 3-SAT clause as a Hamiltonian term

**Theorem**. The \(k\)-local Hamiltonian problem is \(\class{QMA}\)-complete for all \(k \ge 2\).

*Our discussion follows Quantum NP: A Survey*

#### 3.2.2 Circuit to Hamiltonian construction

Review of classical Cook-Levin theorem

Simplification: embed input \(x\) to the circuit

Clock register and computation register

History state \(\ket{\eta} = \frac{1}{\sqrt{T+1}} \sum_{t=0}^T \ket{t}_{clock} \otimes U_t \cdots U_2 U_1 (\ket{0^n} \ket{\psi})\)

Consider Hamiltonian terms

\begin{equation*} \begin{split} H_{in} & = \sum_{j=1}^n\, \ket{0}\bra{0}_{clock} \otimes \Pi_j^1,\\ H_{out} & = \ket{T}\bra{T}_{clock} \otimes \Pi_1^0,\\ H_{prop}^{(t)} & = \frac{1}{2} \bigl( \ket{t-1}\bra{t-1}_{clock} \otimes I + \ket{t}\bra{t}_{clock} \otimes I \\ & \qquad - \ket{t}\bra{t-1}_{clock} \otimes U_t - \ket{t-1}\bra{t}_{clock} \otimes U_t^\dagger \bigr),\\ H_{prop} & = \sum_{t=1}^T H_{prop}^{(t)}. \end{split} \end{equation*}The Hamiltonian corresponding to the circuit is \(H = H_{in} + H_{out} + H_{prop}\), and we set \(a = 1/T^{10}\) and \(b = 1/4(T+1)^3\).

#### 3.2.3 Proof

- Completeness. Easy to check!
Soundness. If \(x \in A_{no}\), the Hamiltonian \(H\) has energy at least \(b\)

Analyse the spectrum of \(H_{io} = H_{in} + H_{out}\) and \(H_{prop}\)

Consider the ground spaces \(N_{io}\) and \(N_{prop}\) of \(H_{io}\) and \(H_{prop}\) respectively

Define \(R = \sum_{t=0}^T U_t \cdots U_1 \otimes \ket{t}\bra{t}\)

- \(H_{io}\) is a projector, the second eigenvalue is \(1\)
- \(H_{prop}\) has a special form under the conjugation of \(R\) and the second eigenvalue is at least \(1/2(T+1)^2\)
- have a noticeable angle \(\theta\) with \(\sin^2 (\theta/2) \ge 1/2(T+1)\)

From \(O(\log(T))\)-local to \(5\)-local

### 3.3 Error reduction for QMA

- Standard error reduction: requires multiple copies of the quantum witness state
- Strong error reduction: a single copy of quantum witness state suffices

### 3.4 Discussions

\(\class{QMA}\) (local Hamiltonian problem) and optimization

Maximize: \(\mathrm{tr} (H \rho)\)

Subject to: \(\rho\) is semidefinite positive and trace \(1\)

Other complete problems for \(\class{QMA}\)

1-D local Hamiltonian problem

Circuit non-identity

Density matrix consistency / N-representability

- Variants of \(\class{QMA}\)

### 3.5 Exercise 5

Prove that the local Hamiltonian problem is in \(\class{QMA}\).

### 3.6 Exercise 6

For which circuit is the EPR state \(\frac{\ket{00}+\ket{11}}{\sqrt{2}}\) a history state? Write down the Hamiltonian for this circuit and check that the EPR state is the ground state of that Hamiltonian.

### 3.7 Research Problem

Understand the relation of \(\class{QMA}\) and its variants \(\class{QCMA}\), \(\class{QMA}_1\), \(\class{QMA}(2)\).