- Introduction to (quantum) complexity theory
- BQP: polynomial time quantum computation
- BQP $\subseteq$ PSPACE

Decision problems where the "yes" inputs have solutions that can be efficiently checked.

**Example**: Traveling Salesman Problem

**Input**: Graph $G$, integer $k$

**Output**: Does $G$ have a tour of length at most $k$ that visits every city once and returns to origin?

A decision problem has an NP "algorithm" if the algorithm can *nondeterministically* guess a solution (if it exists), and check the solution in polynomial time. If there is no solution, no guess will be accepted.

"Quantum computers solve problems by trying all possible solutions simultaneously and outputting a correct one!"

If that were true, then NP complete problems would be instantly solvable on quantum computers.

We don't have the tools available to outright prove that BQP cannot solve NP-complete problems. But we can try to give evidence for this.

We will show a **black box separation** (also known as **oracle separation** between NP and BQP.

Decision problems are defined with inputs that are represented as binary strings (i.e. graphs, integers, etc. are represented in binary), and the outputs are about whether the inputs satisfy some property.

**oracle model**, decision problems get **black box functions** as input, and the goal is to decide something about the function given query access to the function.

In particular, cannot "look inside the black box" in order to solve the problem.

**Input**: A black box function $f: \{0,1\}^n \to \{0,1\}$.

**Output**: Does there exist $x$ such that $f(x) = 1$?

There is an **NP oracle algorithm** that "solves" the Unstructured Search Problem with $1$ query.

There is an **quantum oracle algorithm** (namely, Grover's algorithm) that solves the Unstructured Search Problem with $O(\sqrt{2^n})$ quantum queries.

**Question**: is there a quantum algorithm that can solve Unstructured Search Problem with $\mathrm{poly}(n)$ queries?

Bennett, Bernstein, Brassard, and Vazirani: "Strengths and weakness of quantum computing" (1997)

We will show that $A$ can't increase the amplitude on the marked input fast enough to notice it.

The algorithm $A$ alternates between fixed unitaries $A_0,A_1,\ldots,A_T$ that don't depend on $f$, and phase oracles $O_f$.

It starts in the all zeroes state, and either outputs a marked input $\ket{x^*}$ with high probability or outputs "NO MARKED INPUT".

Imagine running the algorithm $A$ on the all zeroes function (there is no marked input).

This is equivalent to running the algorithm with the phase oracle $I$.

Let $\ket{\psi_T^I}$ denote the final state of the algorithm. Measuring it yields "NO MARKED INPUT" with high probability.

**Goal**: Show there exists $f(x)$ with unique solution $x^*$, where running $A$ with $O_f$ yields output state $\ket{\psi^f_T}$ satisfying

**Contradiction**: measuring $\ket{\psi^f_T}$ yields "NO MARKED INPUT" with high probability.

Define $\ket{\psi^I_t}$ = state of algorithm querying $I$ right after $t$'th query, for $1 \leq t \leq T$.

**Intuition**: There has to be an $x^*$ where the total amplitude over all timesteps is small.

Define the **query magnitude** of $x \in \{0,1\}$

**Claim**: $\sum_x M_x = T$

**Proof**:

$ \sum_x M_x = \sum_{t=1}^T \sum_{x,w} |\alpha_{t,x,w}|^2$ (by definition of $M_x$)

$ \qquad = \sum_{t=1}^T 1$ (because $\ket{\psi_t^I}$ is a unit vector)

$\qquad = T$.

Therefore there exists $x^*$ where $M_{x^*} = T/2^n$.

Define $f(x)$ to have $x^*$ as a unique solution.

This $x^*$ is an "overlooked" input - it does not get a lot of attention from the algorithm!

To show that $\ket{\psi_T^f}$ is close to $\ket{\psi_f^I}$, we analyze **hybrids**, which are fictitious runs of the algorithm where the oracle changes in the middle.

**Hybrid 0**: all $T$ queries to $I$.

**Hybrid 1**: first $T-1$ queries to $I$, last query to $O_f$.

**Hybrid $k$**: first $T - k$ queries to $I$, last $k$ queries to $O_f$.

Analyze on the board.

We wish to find a computational task $T$ that:

- NISQ (Noisy Intermediate-Scale Quantum) machine can run $T$ in, e.g. < 1 second.
- Verifiable on a classical computer in a reasonable amount of time (e.g. several weeks on a supercomputing cluster)
- Some complexity evidence that $T$ cannot be efficiently solved by classical computers.

Such a task $T$ would demonstrate the supremacy of quantum computers over classical computers.

This computational task $T$ can only happen in a "sweet spot" with $\sim 50$-$100$ qubits.

Enough that it's not easy for classical computers, but not too much so that we can run it on our existing quantum computers, and also verify it using $\sim 2^{50}$ operations on a classical computer.

Number of qubits $n = 50$

Number of gates $m = 200$

Number of samples $T = $ several million

- Pick a random quantum circuit $C$ acting on $n$ qubits, with $m$ gates.
- Using quantum computer run circuit $C$ on $\ket{0 \cdots 0}$, generate samples $x_1,\ldots,x_T$ from the distribution $\mathcal{D}_C$.
- Output $x_1,\ldots,x_T$.

A quantum computer, by definition, can easily perform the random circuit sampling task. How hard is it for a classical computer to do the same?

**Theorem** (Bouland, Fefferman, Nirkhe, Vazirani): There is no classical algorithm that, given circuit $C$, can generate samples from $\mathcal{D}_C$ with high probability, unless the polynomial hierarchy collapses to the third level.

"X unless the polynomial hierarchy collapses" is complexity theory evidence that X is true. It is a generalization of the assumption that $P \neq NP$.

*exactly* from $\mathcal{D}_C$. However, not even the quantum computer can do that, because it has some small amount of noise. One can ask how hard is it to *approximately sample* from $\mathcal{D}_C$. It is conjectured that this is still hard for classical algorithms (assuming polynomial hierarchy does not collapse).

How do you check whether a bunch of samples $x_1,\ldots,x_T$ were generated by $\mathcal{D}_C$? There is no known efficient way of doing so.

**Idea**: Heavy output generation (HOG) test

- Use a classical supercomputer to compute the median $\alpha$ of all $p_C(x)$.
- If at least $2/3$ of $x_1,\ldots,x_T$ are
**heavy**(meaning $p_C(x_i) \geq \alpha$), then accept. Otherwise reject.

**Intuition**: heavy $x$'s form the bulk of the probability mass of distribution $\mathcal{D}_C$. Sampling from $\mathcal{D}_C$ should yield a lot of heavy strings.

However, it should also be hard for a classical computer to predict, given a circuit $C$ and $x$, whether $p_C(x)$ is above the median.

If a quantum machine is able to consistently output heavy strings from $\mathcal{D}_C$, then the machine must've "done something right".

Conducted in Fall 2019. Ran many circuits on their 49-qubit "Sycamore" chip.

Extremely noisy: signal-to-noise ratio is about 1%. (However, Google claims it is enough to verify the sampling).

**Recently**: many challenges to this claim (faster classical simulations, noisy sampling may not be as hard as we thought).

Simulating quantum physics.

In [ ]:

```
```