- Pset2 due Sunday, October 9, 11:59pm.
- Henry, please record the lecture!

- Holevo's Theorem, Superdense coding, Universal gate sets and the Deutsch algorithm

**Deutsch problem**: Given oracle access to a boolean function $f: \{0,1\} \to \{0,1\}$, decide whether $f(0) = f(1)$ or $f(0) \neq f(1)$.

**Deutsch algorithm**:

This quantum algorithm solves the Deutsch problem with **one** call to $U_f$, which maps $\ket{x,b}$ to $\ket{x, b \oplus f(x)}$.

The algorithm evaluates the function $f$ in **superposition**. This seems to give a 2x speedup!

Is this cheating? Maybe the "quantum access" is just really making multiple classical queries under the hood?

**Observation**: the qubit storing the answer at the end corresponds to the **input wire** of the oracle $U_f$. We don't care about the output wire!

This is a common feature in many quantum algorithms with exponential speedup.

**Problem**: Given oracle access to $f:\{0,1\}^n \to \{0,1\}^n$ such that there exists a nonzero **secret string** $s \in \{0,1\}^n$ where for all $x, y \in \{0,1\}^n$

find the secret string $s$.

**Problem**: Given oracle access to $f:\{0,1\}^n \to \{0,1\}^n$ such that there exists a nonzero **secret string** $s \in \{0,1\}^n$ where for all $x, y \in \{0,1\}^n$

find the secret string $s$. Here $x \oplus y$ means bitwise XOR.

**Question**: How many queries to $f$ are necessary to find the secret?

- Randomly sample $x_1,\ldots,x_K \in \{0,1\}^n$ for $K = 10 \sqrt{2^n}$.
- Check if there exists a pair $x_i \neq x_j$ where $f(x_i) = f(x_j)$. If so, then output $s = x_i \oplus x_j$.

By the **birthday paradox**, this algorithm will find the secret with high probability. Requires $O(2^{n/2})$ queries to $f$. (Show on board)

$2^{n/2}$ queries are necessary for any classical algorithm!

A quantum algorithm queries $f$ by calling the $2n$-qubit unitary $U_f$ that maps

$$| \underbrace{x}_{n \text{ qubits}}, \underbrace{z}_{n \text{ qubits}} \rangle \mapsto \ket{x, z \oplus f(x)}$$Here, $\oplus$ denotes bitwise addition.

Simons algorithm is a **classical-quantum** hybrid algorithm.

It uses the quantum computer as a *subroutine* to sample from a distribution many times, and uses **classical post-processing** to extract the secret.

**Simons subroutine**: Quantum circuit queries $U_f$ *once* and obtains a *uniformly random* string $y \in \{0,1\}^n$ where inner product of $y$ and the secret $s$,

is equal to $0$.

**Classical post-processing**:

Obtain $m = 100n$ samples $y^{(1)}, y^{(2)}, \ldots,y^{(m)}$ such that

\begin{align*} y^{(1)} \cdot s &= 0 \\ y^{(2)} \cdot s &= 0 \\ &\vdots \\ y^{(m)} \cdot s &= 0 \end{align*}What is $H^{\otimes n} \ket{0}^{\otimes n}$?

This can be rewritten as $(H \ket{0})^{\otimes n} = \ket{+}^{\otimes n}$.

What is $H^{\otimes n} \ket{x_1,\ldots,x_n}$?

- Makes $O(n)$ queries to $U_f$ and solves the problem with high probability
- Once again, the valuable information is stored not in the answer register of $U_f$, but in the input register.

- Making crucial use of constructive/destructive interference!
- It's finding
**global hidden structure**in the function. - Is this speedup more convincing?

Invented by Dan Simons in 1992, and was the first example of a problem that could be solved exponentially faster with a quantum algorithm compared to a classical randomized algorithm.

This algorithm directly inspired Peter Shor to invent the famous factoring algorithm.

Recently, Simons algorithm also has applications to breaking symmetric key cryptography.

Quantum Fourier Transform

In [ ]:

```
```