From 6ce0bb9a8f9fd7d169cbb414a9537d68c5290aae Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Fri, 14 Oct 2022 23:25:28 +0200
Subject: Initial commit after migration from Hugo
---
.../deutsch-jozsa-algorithm/deutsch-circuit.png | Bin 0 -> 3557 bytes
.../deutsch-jozsa-circuit.png | Bin 0 -> 7788 bytes
.../know/concept/deutsch-jozsa-algorithm/index.md | 229 +++++++++++++++++++++
3 files changed, 229 insertions(+)
create mode 100644 source/know/concept/deutsch-jozsa-algorithm/deutsch-circuit.png
create mode 100644 source/know/concept/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png
create mode 100644 source/know/concept/deutsch-jozsa-algorithm/index.md
(limited to 'source/know/concept/deutsch-jozsa-algorithm')
diff --git a/source/know/concept/deutsch-jozsa-algorithm/deutsch-circuit.png b/source/know/concept/deutsch-jozsa-algorithm/deutsch-circuit.png
new file mode 100644
index 0000000..0c6c7b2
Binary files /dev/null and b/source/know/concept/deutsch-jozsa-algorithm/deutsch-circuit.png differ
diff --git a/source/know/concept/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png b/source/know/concept/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png
new file mode 100644
index 0000000..335a624
Binary files /dev/null and b/source/know/concept/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png differ
diff --git a/source/know/concept/deutsch-jozsa-algorithm/index.md b/source/know/concept/deutsch-jozsa-algorithm/index.md
new file mode 100644
index 0000000..080b290
--- /dev/null
+++ b/source/know/concept/deutsch-jozsa-algorithm/index.md
@@ -0,0 +1,229 @@
+---
+title: "Deutsch-Jozsa algorithm"
+date: 2021-04-08
+categories:
+- Quantum information
+- Algorithms
+layout: "concept"
+---
+
+The **Deutsch algorithm** and its extension, the **Deutsch-Jozsa algorithm**,
+were first to prove that quantum computers can
+solve certain problems more efficiently
+than any classical system.
+
+Given an unknown "black box" binary function $f(x)$ of one or more bits $x$,
+the goal is determine whether $f$ is
+**constant** (i.e. $f(x)$ is the same for all $x$)
+or **balanced** (i.e. exactly 50% of all $x$-values yield $f(x) = 0$,
+and the other 50% yield $f(x) = 1$).
+We can query $f$ as many times as we want with inputs of our choice,
+but we want to solve the problem using as few queries as possible.
+
+The problem is extremely artificial and of no practical use,
+but quantum computers can solve it with a single query,
+while classical computers need up to $2^{N - 1} + 1$ queries
+for an $N$-bit $x$.
+
+
+## Deutsch algorithm
+
+The Deutsch algorithm handles the simplest case,
+where $x$ is only a single bit.
+Only four $f$ exist:
+
++ **Constant**: $(f(0) = f(1) = 0)$ or $(f(0) = f(1) = 1)$.
++ **Balanced**: $(f(0) = 0, f(1) = 1)$, or $(f(0) = 1, f(1) = 0)$.
+
+In other words, we only need to determine if $f(0) = f(1)$ or $f(0) \neq f(1)$.
+To do this, we use the following quantum circuit,
+where $U_f$ is the oracle we query:
+
+
+
+
+
+Due to unitarity constraints,
+the action of $U_f$ is defined to be as follows,
+with $\oplus$ meaning XOR:
+
+$$\begin{aligned}
+ \Ket{x} \Ket{y}
+ \quad \to \boxed{U_f} \to \quad
+ \Ket{x} \Ket{y \oplus f(x)}
+\end{aligned}$$
+
+Starting on the left from two qubits $\Ket{0}$ and $\Ket{1}$,
+we apply the [Hadamard gate](/know/concept/quantum-gate/) $H$ to both:
+
+$$\begin{aligned}
+ \Ket{0} \Ket{1}
+ \quad \to \boxed{H^{\otimes 2}} \to \quad
+ \Ket{+} \Ket{-}
+ = \frac{1}{2} \Big( \Ket{0} + \Ket{1} \Big) \Big( \Ket{0} - \Ket{1} \Big)
+\end{aligned}$$
+
+Feeding this result into the oracle $U_f$ then leads us to:
+
+$$\begin{aligned}
+ \to \boxed{U_f} \to \quad
+ \frac{1}{2} \Ket{0} \Big( \Ket{0 \oplus f(0)} - \Ket{1 \oplus f(0)} \Big)
+ + \frac{1}{2} \Ket{1} \Big( \Ket{0 \oplus f(1)} - \Ket{1 \oplus f(1)} \Big)
+\end{aligned}$$
+
+The parenthesized superpositions can be reduced.
+Assuming that $f(b) = 0$, we notice:
+
+$$\begin{aligned}
+ \Ket{0 \oplus f(b)} - \Ket{1 \oplus f(b)}
+ = \Ket{0 \oplus 0} - \Ket{1 \oplus 0}
+ = \Ket{0} - \Ket{1}
+\end{aligned}$$
+
+On the other hand, if we assume that $f(b) = 1$,
+we get the opposite result:
+
+$$\begin{aligned}
+ \Ket{0 \oplus f(b)} - \Ket{1 \oplus f(b)}
+ = \Ket{0 \oplus 1} - \Ket{1 \oplus 1}
+ = - \big(\Ket{0} - \Ket{1}\big)
+\end{aligned}$$
+
+We can thus combine both cases, $f(b) = 0$ or $f(b) = 1$,
+into the following single expression:
+
+$$\begin{aligned}
+ \Ket{0 \oplus f(b)} - \Ket{1 \oplus f(b)}
+ = (-1)^{f(b)} \big(\Ket{0} - \Ket{1}\big)
+\end{aligned}$$
+
+Using this, we rewrite the intermediate state of the quantum circuit like so:
+
+$$\begin{aligned}
+ \Ket{0} \Ket{1}
+ \quad \to \boxed{H^{\otimes 2}} \to \boxed{U_f} \to \quad
+ \frac{1}{2} \Big( (-1)^{f(0)} \Ket{0} + (-1)^{f(1)} \Ket{1} \Big) \Big( \Ket{0} - \Ket{1} \Big)
+\end{aligned}$$
+
+The second qubit in state $\Ket{-}$ is garbage; it is no longer of interest.
+The first qubit is given by:
+
+$$\begin{aligned}
+ \frac{1}{\sqrt{2}} \Big( (-1)^{f(0)} \Ket{0} + (-1)^{f(1)} \Ket{1} \Big)
+ = \frac{(-1)^{f(0)}}{\sqrt{2}} \Big( \Ket{0} + (-1)^{f(0) \oplus f(1)} \Ket{1} \Big)
+\end{aligned}$$
+
+If $f$ is constant, then $f(0) \oplus f(1) = 0$,
+meaning this state is $(-1)^{f(0)} \Ket{+}$.
+On the other hand, if $f$ is balanced, then $f(0) \oplus f(1) = 1$,
+meaning this state is $(-1)^{f(0)} \Ket{-}$.
+Taking the Hadamard transform of this qubit therefore yields:
+
+$$\begin{aligned}
+ \to \boxed{H} \to \quad
+ (-1)^{f(0)} \Ket{f(0) \oplus f(1)}
+\end{aligned}$$
+
+Depending on whether $f$ is constant or balanced,
+the mearurement outcome of this state will be $\Ket{0}$ or $\Ket{1}$
+with 100\% probability. We have solved the problem!
+
+Note that we only consulted the oracle (i.e. applied $U_f$) once.
+A classical computer would need to query it twice,
+once with input $x = 0$, and again with $x = 1$.
+
+
+## Full Deutsch-Jozsa algorithm
+
+The Deutsch-Jozsa algorithm generalizes the above to $N$-bit inputs $x$.
+We are promised that $f(x)$ is either constant or balanced;
+other possibilities are assumed to be impossible.
+This algorithm is then implemented by the following quantum circuit:
+
+
+
+
+
+There are $N$ qubits in initial state $\Ket{0}$, and one in $\Ket{1}$.
+For clarity, the oracle $U_f$ works like so:
+
+$$\begin{aligned}
+ \Ket{x_1} \Ket{x_2} \cdots \Ket{x_N} \Ket{y}
+ \quad \to \boxed{U_f} \to \quad
+ \Ket{x_1} \cdots \Ket{x_N} \Ket{y \oplus f(x_1, ..., x_N)}
+\end{aligned}$$
+
+Applying the $N + 1$ Hadamard gates to the initial state
+yields the following superposition:
+
+$$\begin{aligned}
+ \Ket{0}^{\otimes N} \Ket{1}
+ \quad \to \boxed{H^{\otimes N + 1}} \to \quad
+ \Ket{+}^{\otimes N} \Ket{-}
+ = \frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} \Ket{x} \Ket{-}
+\end{aligned}$$
+
+Where $\Ket{x} = \Ket{x_1} \cdots \Ket{x_N}$ denotes a classical binary state.
+For example, if $x = 5 = 2^0 + 2^2$ in the summation,
+then $\Ket{x} = \Ket{1} \Ket{0} \Ket{1} \Ket{0}^{\otimes N-3}$
+(from least to most significant).
+
+We give this state to the oracle,
+and, by the same logic as for the Deutsch algorithm,
+get back:
+
+$$\begin{aligned}
+ \to \boxed{U_f} \to \quad
+ \frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} (-1)^{f(x)} \Ket{x} \Ket{-}
+\end{aligned}$$
+
+The last qubit $\Ket{-}$ is garbage.
+Next, applying the Hadamard transform to the other $N$ gives:
+
+$$\begin{aligned}
+ \to \boxed{H^{\otimes N}} \to \quad
+ \frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} (-1)^{f(x)}
+ \bigg( \frac{1}{\sqrt{2^N}} \sum_{y = 0}^{2^N - 1} (-1)^{x \cdot y} \Ket{y} \bigg)
+\end{aligned}$$
+
+Where $x \cdot y$ is the bitwise dot product of the binary representations of $x$ and $y$,
+so, for example, if $N = 2$, then $x \cdot y = x_1 y_1 + x_2 y_2$.
+Note that the above expression has not been reduced at all;
+it follows from the definition of the Hadamard transform.
+We can rewrite it like so:
+
+$$\begin{aligned}
+ \frac{1}{2^N} \sum_{x = 0}^{2^N - 1} \sum_{y = 0}^{2^N - 1} (-1)^{f(x) + x \cdot y} \Ket{y}
+ = \sum_{y = 0}^{2^N - 1} \bigg( \frac{1}{2^N} \sum_{x = 0}^{2^N - 1} (-1)^{f(x) + x \cdot y} \bigg) \Ket{y}
+ = \sum_{y = 0}^{2^N - 1} c_y \Ket{y}
+\end{aligned}$$
+
+The parenthesized expression can be interpreted as the coefficients
+of a superposition of several $y$-values.
+Therefore, the probability that a measurement yields $y = 0$,
+i.e. $\Ket{y} = \Ket{0}^{\otimes N}$, is:
+
+$$\begin{aligned}
+ |c_0|^2
+ = \bigg| \frac{1}{2^N} \sum_{x = 0}^{2^N - 1} (-1)^{f(x)} \bigg|^2
+\end{aligned}$$
+
+The summation always contains an even number of terms, for all values of $N$.
+Consequently, if $f$ is constant, then $|c_0|^2 = |\!\pm\! 2^N / 2^N|^2 = 1$.
+Otherwise, if $f$ is balanced, all the terms cancel out, so we are left with $|c_0|^2 = 0$.
+In other words, we reach the same result as the Deutsch algorithm:
+we only need to measure the $N$ qubits once;
+$f$ is constant if and only if all are zero.
+
+The Deutsch-Jozsa algorithm needs only one oracle query to give an error-free result,
+whereas a classical computer needs $2^{N-1} + 1$ queries in the worst case;
+a revolutionary discovery.
+
+
+## References
+1. J.S. Neergaard-Nielsen,
+ *Quantum information: lectures notes*,
+ 2021, unpublished.
+2. S. Aaronson,
+ *Introduction to quantum information science: lecture notes*,
+ 2018, unpublished.
--
cgit v1.2.3