Lecture 2.1 - Simple Quantum Algorithms I

Last updated Mar 27, 2022

Assume we have access to an oracle, e.g. a physical device that we cannot look inside, but to which we can pass some queries and which then returns some answers. ^0b31a3
🕒 02:24 Goal: determine some property of the oracle using the minimal number of queries.
🕒 03:36 On a classical computer, such an oracle is given by a function, $f: {0, 1}^n \rightarrow {0, 1}^m$ .
🕒 04:19 On a quantum computer, the oracle must be reversible.
🕒 05:50 $O_f$ : Bit Oracle, can be seen as a Unitary matrix which performs the map $O_f\ket{x}\ket{y} = \ket{x} \ket{y \oplus f(x)}$ .
🕒 06:49 For $f: {0, 1}^n \rightarrow {0, 1}$ , we can construct $U_f$ :
🕒 08:03 Why we can ignore $\ket{-}$ ?
$$\begin{aligned}
O_f \ket{x}\ket{y} &= \frac{1}{\sqrt 2}(\ket{x} \ket{0 \otimes f(x)} - \ket{x}\ket{1 \oplus f(x)}) \newline
&= \begin{cases} \frac{1}{\sqrt 2} \ket{x}(\ket{0} - \ket{1}) = \ket{x}\ket{y}, & \text{if} \\ f(x) = 0 \
\frac{1}{\sqrt 2}\ket{x} (\ket{1} - \ket{0}) = \ket{x}\ket{y}, & \text{if} \\ f(x) = 1
\end{cases} \newline
&= (-1)^{f(x)}\ket{x}\ket{y}.
\end{aligned}$$
🕒 10:29 So, this is independent of $\ket{y}$ , so we call this Phase Oracle $U_f$ , which performs the map $U_f \ket{x} = (-1)^{f(x)}\ket{x}$ .
- 🕒 11:26 $- \ket{x}\ket{y} = (- \ket{x}) \otimes \ket{y} = \ket{x} \otimes (- \ket{y})$ .

🕒 13:52 General representation of Hadamard Gate for a single qubit
- for $x \in {0, 1}$ : $$\begin{aligned}H \ket{x} &= \frac{1}{\sqrt 2}(\ket{0} + (-1)^x \ket{1}) \newline
  &= \frac{1}{\sqrt 2}((-1)^{0 \cdot x} \ket{0} + (-1)^{1 \cdot x} \ket{1}) \newline
  &= \frac{1}{\sqrt 2} \sum_{k \in {0, 1}} (-1)^{k \cdot x} \ket{k}. \end{aligned}$$
🕒 15:37 General representation of Hadamard Gate for an $n$- bit string
- for $x \in {0, 1}^n$ : $$H^{\otimes n} \ket{x} = \frac{1}{\sqrt 2^n} \sum_{k \in {0, 1}^n} (-1)^{k \cdot x} \ket{k}.$$
  - 🕒 18:10 $\ket{y}$ must be a superposition of all possible $2^n$ bit strings.

We are given a function $f: {0, 1}^n \rightarrow {0, 1}$ , realized by an Oracle, of which we know that it is either constant (all inputs map to the same output) or balanced (50% probability to be either 1 or 0).
🕒 21:54 Goal: Determine whether $f$ is constant or balanced.
🕒 22:12 Classical Solution
- We need to ask the Oracle at least twice, but if we get twice the same output, we need to ask again.
- In the worst case, we need to ask $\frac{N}{2} + 1 = 2^{N-1} + 1$ times, where $n$ is the number of input bits and $N = 2^n$ .
🕒 25:21 Quantum Solution
- We need only one query.
- 🕒 25:45 Circuit
- 🕒 27:39 Claim
  - If the outcome $y$ equals the bit string $000 \dots 0$ , then $f$ is constant, other it is balanced.
- 🕒 28:26 Proof
- 🕒 38:46 Intuitive way to see why this works.

🌱Aadam's Garden