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)
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\)
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)\)
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^*\)
Turing machines
A brief discussion of TMs
Transition rule \(\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}\)
Configuration of a TM
Classical and quantum circuit models
Classical circuits are not necessarily reversible
Polynomial-time (mathematically simple, model-independent)
\(\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}\)
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.
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?
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.
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
The class \(\class{BQP}\) is defined as \(\class{BQP} = \class{BQP}(2/3,1/3)\).
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})\).
Theorem. \(\class{BQP}^{\class{BQP}} = \class{BQP}\).
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)}\)
What do we need to prove?
Two difficulties:
Hybrid method
Phase-kickback oracle: \(O \ket{i} = (-1)^{x_i} \ket{i}\).
Assume the algorithm has the form \(U_T O_T U_{T-1} \cdots U_{1} O_1 U_0\).
Hybrid \(t\) for \(t=0, 1, \ldots T\): \(O_s = \begin{cases} O & s > T-t, \\I & \text{o.w.}\end{cases}\)
Let \(\ket{\xi_t}\) be the final state of the Hybrid \(t\) circuit.
Consider Hybrid \(0\) and let \(\ket{\psi_t} = \sum_{i=1}^n \alpha^{(t)}_i \ket{i}\) be the state of this hybrid before the \(t\)-th query.
We have
\[\begin{equation} \sum_{i=1}^n \sum_{t=1}^T \abs{\alpha^{(t)}_i}^2 = T, \end{equation} \]and there exists \(i_0\) such that \(\sum_{t=1}^T \abs{\alpha^{(t)}_{i_0}}^2 \le T/n\). By Cauchy-Schwarz inequality,
\[\begin{equation} \sum_t \abs{\alpha^{(t)}_{i_0}} \le \sqrt{T \sum_t \abs{\alpha^{(t)}_{i_0}}^2} = T/\sqrt{n}. \end{equation} \]Then it is easy to show
\[\begin{equation} \begin{split} \norm{\ket{\xi_t} - \ket{\xi_{t-1}}} & \le 2 \abs{\alpha^{(T-t+1)}_{i_0}},\\ \norm{\ket{\xi_T} - \ket{\xi_0}} & \le 2 \sum_t \abs{\alpha^{(t)}_{i_0}} \le 2 T/\sqrt{n}. \end{split} \end{equation} \]\(\ket{\xi_T}\) is the final state of the algorithm, and it has a small probability of giving outcome \(i_0\) as it is very close to \(\ket{\xi_0}\).
\(\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.
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
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
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
The class \(\class{QMA}\) is defined as \(\class{QMA}(2/3,1/3)\).
Quantization of both the witness and the circuit.
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
A 3-SAT clause as a Hamiltonian term
Aharonov and Naveh, Quantum NP: A Survey
Marriott and Watrous, Quantum Arthur-Merlin Games
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.
Prove the error reduction theorem for \(\class{BQP}\).
Prove that BQP is in PSPACE