19  Quantum complexity

So far, we know that quantum computers can potentially be exponentially faster than classical computers. However, the exact extent of this advantage remains unknown.

For instance, can quantum computers solve NP-hard problems in polynomial time?

We start with the common complexity class NP (non-deterministic polynomial time):

Definition 19.1 (The complexity class NP) A language \(L\) is in \(\text{NP}\) if and only if there exists a deterministic classical algorithm \(A\) running in polynomial time such that:

If \(x\) is a YES-Instance, then a \(\omega\) exists such that \(A(x, \omega) = 1\),

if \(x\) is a NO-Instance, then no \(\omega\) exists such that \(A(x, \omega) = 1\) (in other words: for all \(\omega\) is \(A(x, \omega) \neq 1\)).

Note that this definition is a bit informal because we do not explicitly specify in which argument \(A\) is polynomial, and how the length of \(\omega\) is bounded etc. While important for a precise analysis, we omit such details in this chapter.

This means than an \(\text{NP}\)-algorithm can efficiently verify YES-instances and never incorrectly accepts a NO-instance.

Example: \(\text{SAT}\) (Satisfiability)

Given a function \(f: \{0,1\}^n \rightarrow \{0,1\}\) (e.g. represented as a circuit), the \(\text{SAT}\) problem is defined as:

YES-Instance: A \(z\) exists such that \(f(z) = 1\),

NO-Instance: No \(z\) exists such that \(f(z) = 1\).

The \(\text{SAT}\) problem is in \(\text{NP}\).

Furthermore, \(\text{SAT}\) is \(\text{NP}\)-complete. This means that if we can solve \(\text{SAT}\) in polynomial time, we can solve any problem in \(\text{NP}\) in polynomial time.

The key question is whether quantum computers can solve \(\text{SAT}\) (or any other \(\text{NP}\)-complete problem) in polynomial time. This is closely related to the famous “\(\text{P} = \text{NP}\)” problem.

Although the question remains unsolved even for classical computers, there are weak indications for quantum computers suggesting a negative answer.

19.1 Oracle lower bounds

It is known that quantum computers cannot solve \(\text{SAT}\) in polynomial time relative to a black-box function (oracle). That is, if the only thing the algorithm can do with \(f\) is to evaluate it. (No “decompilation” or similar.)

For classical computers, it is easy to see that \(\Theta(2^n)\) queries are necessary and sufficient to distinguish YES- and NO-instances in the black-box case. For quantum computers, this bound is reduced to \(\Theta(2^\frac{n}{2})\).

This is achievable with Grover’s algorithm: For a function \(f\), Grover’s algorithm finds a \(z\) such that \(f(z) = 1\), if such a \(z\) exists. This can be used to distinguish YES- or NO-instances with arbitrary small error.

We now aks: Could there be even faster quantum algorithms?

Assume we have a quantum algorithm \(A^f\) that uses arbitrary quantum operations (unitaries, auxiliary qubits, measurements, \(\dots\)) and can query the oracle \(V_f: \ket{x} \rightarrow (-1)^{f(x)} \ket{x}\).¹

Theorem 19.1 (Quantum SAT lower bound) If a quantum algorithm can distinguish YES- and NO-instances of \(\text{SAT}\) with constant error, it must perform at least \(\Omega(2^\frac{n}{2})\) queries to \(V_f\).

More precisely:

If \[ \Pr[A^{f_x}() \rightarrow 1 : x \xleftarrow{\textdollar} \{0,1\}^n] - \Pr[A^{f_0}() \rightarrow 1] \geq \text{const} > 0 \] and the algorithm makes \(q\) oracle queries, then \[ q \in \Omega(2^\frac{n}{2}). \] Here \(f_x\) is the function \(f_x(x) = 1\) and \(f_x(z) = 0\) for all \(z \neq x\). And \(f_0(z) = 0\) for all \(z\).

19.1.1 Proof sketch

To give a proof sketch for Theorem 19.1, we look at the circuits for \(A^{f_x}\) and \(A^{f_0}\):

An execution of \(A^{f_x}\)

An execution of \(A^{f_0}\)

We analyze the final states \(\psi^x_q\) and \(\phi_q\) of the algorithms/circuits. We define the average squared distance between the final states: \[ D \coloneqq \sum_{x \in \{0,1\}^n} 2^{-n} \| \psi^x_q - \phi_q \|^2. \]

We aim to show: \(D \leq \frac{4q^2}{2^{-n}}\). For this we need a lemma:

Lemma 19.1 (Quantum inequality) Given two quantum states \(\psi\) and \(\phi\), then for any quantum measurement it is \[ \Bigl| \Pr[\text{outcome is } 1 \text{ given } \psi] - \Pr[\text{outcome is } 1 \text{ given } \phi] \Bigr| \leq \| \psi - \phi \|. \]

With this lemma we get:

\[ \begin{aligned} \Delta &\coloneqq \Pr[A^{f_x}() \rightarrow 1 : x \xleftarrow{\textdollar} \{0,1\}^n] - \Pr[A^{f_0}() \rightarrow 1] \\ &= \sum_{x \in \{0,1\}^n} 2^{-n} \biggl( \Pr[A^{f_x}() \rightarrow 1] - \Pr[A^{f_0}() \rightarrow 1] \biggr) \\ &\leq \sum_{x \in \{0,1\}^n} 2^{-n} \sqrt{\| \psi^x_q - \phi_q \|^2 } \quad \text{// Quantum inequality above} \\ &\leq \sqrt{ \sum_{x \in \{0,1\}^n} 2^{-n} \| \psi^x_q - \phi_q \|^2 } \quad \text{// Jensen's inequality} \\ &= \sqrt{D}. \end{aligned} \]

So it is \(\Delta \leq \sqrt{D}\) and since we assumed \(\Delta \geq \text{const}\) it is: \[ D \geq \Delta^2 \geq \text{const}. \]

Hence, if we show \(D \leq \frac{4q^2}{2^{-n}}\) then it follows \(\frac{q^2}{2^{-n}} \geq \text{const}\) and therefore \(q \in \Omega(2^\frac{n}{2})\).

We prove this via induction on the number of queries \(k\), defining: \[ D_k \coloneqq \sum_{x \in \{0,1\}^n} 2^{-n} \| \psi^x_k - \phi_k \|^2. \] Note that \(D = D_q\). To prove \(D \leq \frac{4q^2}{2^{-n}}\), we will show \(D_k \leq \frac{4k^2}{2^{-n}}\) by induction.

For \(k=0\) it is \(\psi^x_k = \phi_k\), as you can see in the circuits. And therefore it is: \[ D_0 = 0 \leq \frac{4 \cdot 0^2}{2^{-n}} = 0. \]

Now we look at the induction step \(k \rightarrow k+1\):

We have \(D_k \leq \frac{4k^2}{2^{-n}}\) and want to show \(D_{k+1} \leq \frac{4 (k+1)^2}{2^{-n}}\):

\[ \begin{aligned} 2^n D_{k+1} &= \sum_{x \in \{0,1\}^n} \Bigl\| \psi^x_{k+1} - \phi_{k+1} \Bigr\|^2 \\ &= \sum_{x \in \{0,1\}^n} \Bigl\| U_{k+1} (V_f \otimes I_2) \psi^x_k - U_{k+1} \phi_k \Bigr\|^2 \quad \text{// by looking at the circuits} \\ &= \sum_{x \in \{0,1\}^n} \Bigl\| U_{k+1} \Bigl( (V_f \otimes I_2) \psi^x_k - \phi_k \Bigr) \Bigr\|^2 \\ &= \sum_{x \in \{0,1\}^n} \Bigl\| (V_f \otimes I_2) \psi^x_k - \phi_k \Bigr\|^2 \quad \text{// because unitaries preserve norms} \\ &= \sum_{x \in \{0,1\}^n} \Bigl\| (V_f \otimes I_2) (\psi^x_k - \phi_k) + \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr) \phi_k \Bigr\|^2 \\ &\leq \sum_{x \in \{0,1\}^n} \Bigl\| (V_f \otimes I_2) (\psi^x_k - \phi_k) \Bigr\|^2 + 2 \Bigl\| (V_f \otimes I_2) (\psi^x_k - \phi_k) \Bigr\| \cdot \Bigl\| \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr) \phi_k \Bigr\| \\ & \quad\quad + \Bigl\| \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr) \phi_k \Bigr\|^2 \\ &= \sum_{x \in \{0,1\}^n} \Bigl\| \psi^x_k - \phi_k \Bigr\|^2 + 2 \Bigl\| \psi^x_k - \phi_k \Bigr\| \cdot \Bigl\| \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr) \phi_k \Bigr\| \\ & \quad\quad + \Bigl\| \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr) \phi_k \Bigr\|^2 \quad \text{// because unitaries preserve norms} \\ &= 2^n D_k + 2 \sum_{x \in \{0,1\}^n} \Bigl\| \psi^x_k - \phi_k \Bigr\| \cdot \Bigl\| \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr)\phi_k \Bigr\| + \sum_{x \in \{0,1\}^n} \Bigl\| \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr) \phi_k \Bigr\|^2 \\ &\overset{(*)}{=} 2^n D_k + 4 \sum_{x \in \{0,1\}^n} \Bigl\| \psi^x_k - \phi_k \Bigr\| \sqrt{\Pr[M \rightarrow x]} + 4 \underbrace{\sum_{x \in \{0,1\}^n} \Pr[M \rightarrow x]}_{=1 \Bigl(\sum \text{ over all measurement outcomes}\Bigr)} \\ &\leq 2^n D_k + 4 \sqrt{\sum_{x \in \{0,1\}^n} \Bigl\| \psi^x_k - \phi_k \Bigr\| \cdot \sum_{x \in \{0,1\}^n} \Pr[M \rightarrow x]} + 4 \quad \text{// Cauchy-Schwarz-inequality} \\ &= 2^n D_k + 4 \sqrt{2^n D_k \cdot 1} + 4 \\ &\leq 4k^2 + 4 \sqrt{4k^2} + 4 \quad \text{// induction hypothesis} \\ &= 4k^2 + 8k + 4 \\ &= 4(k+1)^2. \end{aligned} \]

So it is \(D_{k+1} \leq \frac{4 (k+1)^2}{2^{-n}}\). Note that \((*)\) holds since when we consider \(\Bigl\| \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr) \phi_k \Bigr\|^2\) it is: \[ \begin{aligned} \Bigl(V_f - I_{2^n} \Bigr) \ket{z} &= V_f \ket{z} - \ket{z} \\ &= \begin{cases} -\ket{z} - \ket{z} = -2\ket{z} & (z = x) \\ \ket{z} - \ket{z} = 0 & (z \neq x) \\ \end{cases} \end{aligned} \] from which follows that \((V_f - I_{2^n}) = 2 P_x\) where \(P_x\) is the projection outcome onto \(\ket{x}\). Hence: \[ \begin{aligned} &\quad \: \Bigl\| \Bigl((V_f \otimes I_2) - I_{2^{n+1}} \Bigr) \phi_k \Bigr\|^2 \\ &= \Bigl\| \Bigl((V_f - I_{2^n}) \otimes I_2 \Bigr) \phi_k \Bigr\|^2 \\ &= 4 \Bigl\| \underbrace{\Bigl(P_x \otimes I_{2^n} \Bigr) \phi_k}_{\substack{\text{non-normalized} \\ \text{post-measurement-state} \\ \text{when measuring } \ket{x}}} \Bigr\|^2 \\ &= 4 \Pr[M \rightarrow x] \end{aligned} \] where \(M\) is the measurement of the \(X\)-register.

In conclusion, no quantum algorithm can solve \(\text{SAT}\) in less than \(\Omega(2^\frac{n}{2})\) queries with an oracle. So \(\text{SAT}\) is quantum-hard relative to some oracle.

19.2 Quantum Merlin Arthur

The question arises, if there is a “quantum \(\text{NP}\)”?

For this we define the class \(\text{QMA}\) (Quantum Merlin Arthur) analogous to Definition 19.1:

Definition 19.2 (The complexity class QMA) A language \(L\) is in \(\text{QMA}\) if and only if there exists a quantum algorithm \(A\) running in polynomial time such that:

If \(x\) is a YES-Instance, then a quantum state \(\ket{\psi}\) exists such that \(\Pr[A(x, \ket{\psi}) = 1] \geq \frac{2}{3}\),

if \(x\) is a NO-Instance, then for all quantum states \(\ket{\psi}\) is \(\Pr[A(x, \ket{\psi}) = 1] \leq \frac{1}{3}\).

Thus, \(\text{QMA}\) plays a similar role in quantum complexity theory as \(\text{NP}\) in classical complexity theory. (And as \(\text{MA}\) in the complexity of randomized algorithms.)

There are known \(\text{QMA}\)-complete problems. One example is the “Local Hamiltonian problem”. For the definition and explanation of a Hamiltonian see Section 13.3.

Definition 19.3 (2-local Hamiltonian) A Hamiltonian \(H\) is \(2\)-local if it can be written as: \[ H = \sum_{i=1}^k H_i \] where each \(H_i\) is a Hamiltonian that operates only on two qubits.

Example: 2-Local Hamiltonian problem

Given a \(2\)-local Hamiltonian \(H\) (specified by the individual \(H_i\)), determine whether:

YES-Instance: The smallest eigenvector of \(H\) is \(\leq \frac{1}{3}\),

NO-Instance: The smallest eigenvector of \(H\) is \(\geq \frac{2}{3}\).

This problem is indeed \(\text{QMA}\)-complete (without proof):

Theorem 19.2 (2LA is QMA-complete) The \(2\)-Local Hamiltonian problem is \(\text{QMA}\)-complete.

---

1. One may wonder why \(V_f\) and not \(U_F\) (Section 12.1.1). In Section 12.1.1 we saw that from \(U_f\), we can construct \(V_f\). Vice versa, given \(V_f\) and the classical knowledge of a single \(f(x)\), we can construct \(U_f\). So it does not matter much, which we choose.