- Pset3 out, due November 2
- Henry, please record the lecture!

- Simons Algorithm
- Quantum Fourier Transform, Phase Estimation, Order Finding
- Grover Search, Quantum Counting, Amplitude Amplification

The formal study of this question is the focus of **quantum complexity theory**.

Study of various **computational resources** needed to solve computational problems.

- time
- space
- interactivity
- randomness
- non-determinism
- quantumness
- ...

The central questions:

- How do these computational resources relate to each other?
- What are the tradeoffs?

- Does non-determinism help speed up computations (P vs NP)
- If a problem can be solved using a small amount of memory, can it also be solved using a small amount of time?
- Can quantum computers efficiently solve problems that are hard for classical computers?

Used to classify and compare computational problems according to the computational resources needed to solve them.

The focus is on **decision problems**, which are computational problems where for each **input** there is a **binary output** ("yes" or "no").

**Example**: Graph connectivity problem

**Input**: graph $G$**Output**: is $G$ connected?

Decision problems that can be solved by **deterministic** algorithms running in time $O(n^c)$ where $n$ is the length of the input.

Captures the notion of **efficient classical computation** in theoretical computer science.

Examples: graph connectivity, determining if a number is prime, computing shortest paths in a graph

Decision problems whose solutions can be **verified** in polynomial time. If the answer to the input is "yes", then there exists a solution/certificate/proof that is efficiently checkable.

Examples: traveling salesman person problem, boolean satisfiability, factoring.

Most optimization/search problems are in NP. Many are **NP complete**.

Decision problems that can be solved by a **randomized**, polynomial time algorithm.

The correct answer must be obtained with high probability (say $99\%$).

Examples: any problem in P, polynomial identity testing

It is conjectured that P = BPP (i.e. randomization does not help for efficient computation).

Decision problems that can be solved by a deterministic algorithm that uses $O(n^c)$ bits of space where $n$ is the input length.

Captures the notion of problems that can be solved using a small amount of **memory**.

Examples: all of P, NP, BPP. Generalized tic-tac-toe, Super Mario Bros.

Decision problems that can be solved by a deterministic algorithm that runs in $O(2^{n^c})$ time.

Examples: all of PSPACE, generalized Chess.

Decision problems that can be solved by a **quantum** algorithm (i.e. a quantum circuit) of $O(n^c)$ size with high probability.

Captures the notion of **efficient quantum computation**.

Examples: all of P, BPP, factoring, simulating quantum physics.

- BQP $\subseteq$ BPP?

In other words, is there an efficient classical simulation of quantum computation?

- NP $\subseteq$ BQP?

Can quantum computers be used to solve hard optimization problems like SAT or Traveling Salesperson Problem?

- What are classical upper bounds on BQP?

**Definition**: The **acceptance probability** of a quantum circuit $C$ on input $\ket{\psi}$ is the probability that measuring the first qubit of $C\ket{\psi}$ yields $\ket{1}$ (i.e. accepts).

**Input**: A description of quantum circuit $C$ where either

- $\Pr[ C\ket{0 \cdots 0} \text{ accepts }] \geq .99$
- $\Pr[ C\ket{0 \cdots 0} \text{ accepts }] \leq .01$

**Output**: Determine which is the case.

APPROX-Q-CIRCUIT is a **promise problem** because the input is promised to satisfy some condition.

APPROX-Q-CIRCUIT is the canonical **BQP complete** problem, meaning that it is the "hardest" problem in BQP. If problem $A$ is in BQP, then it can be reduced to an instance of APPROX-Q-CIRCUIT.

**Claim**: APPROX-Q-CIRCUIT is solvable in BQP.

**Proof**: The description of the circuit $C$ is a list of single- and two-qubit gates $g_1,g_2,\ldots,g_T$ acting on various qubits.

The quantum algorithm to solve APPROX-Q-CIRCUIT is almost tautological: run the gates $g_1,g_2,\ldots$ in sequence, and measure the first qubit of resulting state.

This takes linear* time in the size of the circuit $C$.

* There is some additional overhead due to parsing the description of $C$.

The acceptance probability of a quantum circuit can be computed by a classical computer in exponential time.

**Proof**: Do what we've been doing in class: to compute the result of a circuit, compute the classical description of the state after applying a gate:

The matrix-vector multiplication takes $(2^n)^2)$ time (if $n$ = number of qubits of $C$). Doing this $T$ times requires $O(T \cdot 2^{2n})$ time.

If $\ket{\psi_T} = \sum_{x \in \{0,1\}^n} \alpha_x \ket{x}$, then

$$ \Pr \Big [ C \ket{0 \cdots 0} \text{ accepts} \Big] = \sum_{x \in \{0,1\}^n : x_1 = 1} |\alpha_x|^2 $$Since APPROX-Q-CIRCUIT is BQP-complete, this means BQP $\subseteq$ EXP.

Quantum computations can also be classically simulated using **polynomial space**. This is based on the **sum-over-histories** or **Feynman path integral** approach.

**Key idea**: in polynomial space, can iterate over exponentially many possible "histories" or "paths" of a quantum computation, and add up their amplitudes to determine final probability of measuring $\ket{1}$ in output qubit.

The amplitudes of the output state can be calculated via a tree:

Final amplitude of $\ket{b}$ = sum of amplitudes of all paths from $\ket{0} \to \ket{b}$.

More generally, suppose we have gates $g_1,g_2,g_3,\ldots,g_T$ in a $n$-qubit circuit.

The computation can be represented by a tree where:

- root node is labelled by $\ket{0 \cdots 0}$
- each node has $2^n$ children labeled by $\ket{x}$ for $x \in \{0,1\}^n$
- edge from node $\ket{x}$ in layer $t$ to node $\ket{y}$ in layer $t+1$ is labeled by
**transition amplitude**$ \bra{y} g_t \ket{x}$

**Claim**: Given $n$-qubit basis states $\ket{x}, \ket{y}$, and two-qubit gate $g$, the transition amplitude $\bra{y} g \ket{x}$ can be computed in (classical) polynomial time.

**Proof**: Assume without loss of generality that $g$ acts on first two qubits. Then we are really calculating

where $g$ is a $4\times 4$ unitary matrix and $I_{n-2}$ is identity on $n-2$ qubits.

`ComputeAmp`

¶**Input**: basis states $\ket{x}, \ket{y}$

`amp`

$\leftarrow$ 0

For $u_1$,$u_2$,...,$u_{T-1}\in \{0,1\}^n$:

$\qquad $ `amp`

$ = $ `amp`

$ + \bra{y} g_T \ket{u_{T-1}}$ $ \bra{u_{T-1}} g_{T-1} \ket{u_{T-2}} $ $\cdots \bra{u_1} g_1 \ket{x}$

Return `amp`

`ComputeAmp`

¶The subroutine `ComputeAmp`

computes the overall transition amplitude $\bra{y} C \ket{x}$.

It requires $O(T n)$ bits of space to store $u_1,\ldots,u_{T-1}$ and $\mathrm{poly}(n)$ bits to store `amp`

.

It takes $2^{O(Tn)}$ time to loop over all possible paths $(u_1,\ldots,u_{T-1})$.

**Input**: quantum circuit $C$ satisfying promise

`prob`

$\leftarrow$ 0

For all $y \in \{0,1\}^n$ where $y_1 = 1$:

$\qquad$ `prob`

$=$ `prob`

$ + |$ `ComputeAmp`

$(0^n,y)|^2$

If `prob`

$ \geq .99$ then output **YES**, otherwise output **NO**

The space usage of this algorithm is $\mathrm{poly}(n)$ (to store $y$ and `prob`

) plus whatever `ComputeAmp`

needs, which is polynomial space.

It computes probability of getting $\ket{1}$ in first qubit of final state.

Lower bound for Grover search.

In [ ]:

```
```