Search

# Lecture 2.1 - Simple Quantum Algorithms I

Last updated Mar 27, 2022

# # Notes

## # Deutsch-Jozsa algorithm

### π 00:53 Prerequisites for Deutsch-Jozsa algorithm

#### π 01:18Oracle

• 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:02Hadamard Gate on $n$ -qubits

• π 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.

### π 20:11Deutsch-Jozsa algorithm

• 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