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-time
Non-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 GapP function if there exists a polynomial \(p\) and a polynomial-time computable funcion \(f\) such that
\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*}- 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)\).