The Deutsch algorithm
- I. Introduction
- II. Elements of quantum mechanics
- III. The electromagnetic field
- IV. The qubit
- V. Quantum gates
- VI. States and operators
- VII. Shor’s algorithm
- VIII. Quantum teleportation
- IX. The Deutsch algorithm
- X. The no-cloning theorem
- XI. About anyons
- XII. About SU(2)
- XIII. Teleportation topology
- XIV. The Simon algorithm
- XV. Superdense coding
- XVI. Chern-Simons theory
- XVII. The toric code
- REF. Some pointers
The Deutsch quantum algorithm is a remarkably simple yet powerful example of how different quantum algorithms are compared to classic ones. The algorithm solves a very simple question;
given a black-box function \(f:\{0,1\}\mapsto\{0,1\}\) determine the value of \(f(0)\oplus f(1)\)
It’s obvious that a classic algorithm needs to test the function twice, once for 0 and once for 1. A quantum algorithm needs to test the function only once. Below is a straighforward proof of this fact and it relies only on basic bra-ket arithmetics.
The unknown function defines a unitary transformation \(U_f\) on a 2-qubit as follows:
\(U_f\,|x\,y\rangle := |x\,(y\oplus f(x))\rangle = |x\rangle\otimes|y\oplus f(x)\rangle\)
This is unitary because \(U_f.U_f=\mathbb{1}\):
\(U_f.U_f\,|x\,y\rangle \\ \;= U_f.(\;|x\rangle\otimes|y\oplus f(x)\rangle\;) \\ \; = |x\rangle\otimes|(y\oplus f(x))\oplus f(x)\rangle\\ \; = |x\rangle\otimes|y\oplus ( f(x)\oplus f(x))\rangle\\ \; = |x\rangle\otimes|y\rangle =\mathbb{1}. |x\,y\rangle\)
We’ll define the following kets to ease the notation
\(|-\rangle := \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle),\; |+\rangle := \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\)
and if we apply the unitary \(U_f\) on these minus kets:
\(U_f.|x\rangle\otimes|-\rangle = \frac{1}{\sqrt{2}}|x\rangle\otimes(|0\oplus f(x)\rangle - |1\oplus f(x)\rangle)\). There are two possibilities, either \(f(x)=1\) or \(f(x)=0\). In the first case \(U_f.|x\rangle\otimes|-\rangle=-|x\rangle\otimes|-\rangle\) and in the second case \(U_f.|x\rangle\otimes|-\rangle=|x\rangle\otimes|-\rangle\) which can be combined as
\(U_f.|x\rangle\otimes|-\rangle=(-)^{f(x)}|x\rangle\otimes|-\rangle\). You can similarly show that
\(U_f.|x\rangle\otimes|+\rangle= |x\rangle\otimes|+\rangle\).
Now, the fact that you need only one measurement on a quantum level can be proven as follows:
Start or prepare a quantum 2-qubit in the following state
\(|\psi_1\rangle := |0\,1\rangle\)
then apply the Hadamard transformation on both qubits:
\(|\psi_2\rangle := H\otimes H\;|\psi_1\rangle\\\;=|+\rangle | -\rangle\\\;=\frac{1}{\sqrt{2}}|0\rangle|-\rangle+ \frac{1}{\sqrt{2}}|1\rangle|-\rangle\)
next apply the black-box function and using the derived relationship above:
\(|\psi_3\rangle = U_f.|\psi_2\rangle\\\;=\frac{1}{\sqrt{2}}(-)^{f(0)}|0\rangle|-\rangle+ \frac{1}{\sqrt{2}}(-)^{f(1)}|1\rangle|-\rangle\\\;= (-)^{f(0)}\frac{1}{\sqrt{2}}(|0\rangle+(-)^{f(0)\oplus f(1)}|1\rangle)\,|-\rangle\).
There are two possibilities; the function is constant or it’s not. If it’s constant then \(f(0)\oplus f(1) = 0\) and hence
\(|\psi_3\rangle= (-)^{f(0)}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\,|-\rangle.\) If it’s not constant then \(|\psi_3\rangle= (-)^{f(0)}\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\,|-\rangle.\)
Applying to each of these options a final Hadamard transform and noting that
\(H\,|-\rangle = |1\rangle, \;\;H\,|+\rangle = |0\rangle\)
we get that
\(H\,|\psi_3\rangle =\bigg\{ \begin{array}{ll} (-)^{f(0)}\frac{1}{\sqrt{2}}|0\rangle\,|-\rangle & if\;f(0)\oplus f(1) = 0\\ (-)^{f(0)}\frac{1}{\sqrt{2}}|1\rangle\,|-\rangle & if \;f(0)\oplus f(1)=1\end{array}\).
Now you simply need to measure the first qubit and you are done.
Where does the magic come from? The transition from classic computing to quantum computing really is the transition from an OR logic to an AND logic. Classically a bit can be up OR down while quantum mechanically a (qu)bit can be up AND down at the same time. The superposition of states and entanglement in particular allows one to have multiple computations at the same time. The Deutsch algorithm is just a clever way to transition quantum states (without measuring and hence breaking things) to end up with something you want or need. While classic programming gives you the freedom to do anything you like with registers, a quantum program is a sequence of unitary transformations.
The Deutsch theorem has an extension known as the Deutsch-Josza algorithm and deals with a more general binary functions of the form
\(f:\{0,1\}^n\mapsto\{0,1\}\)
The proof is very similar to the one above. You start with the state
\(|\psi_0\rangle := |0\rangle^{\otimes n}|-\rangle\)
and apply n times the Hadamard transform on the n-first qubits:
\(|\psi_1\rangle := (H^{\otimes n}\otimes 1)\,|0\rangle^{\otimes n}|-\rangle\\\;=|+\rangle^{\otimes n}|-\rangle\)
and since the the first n-qubits correspond to all possible combinations of 0’s and 1’s you get
\(|\psi_1\rangle = \frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}}|x\rangle|-\rangle.\)
You can also interprete the sum as the sum of all integers from zero to \(2^n -1\) in binary format. Upon applying the black-box unitary transformation we get
\(|\psi_2\rangle := U_f .|\psi_1\rangle = \frac{1}{\sqrt{2^n}}.U_f.\big( \sum\,|x\rangle\,|-\rangle\big)\)
and using once again the derived relationship above but extended to multiple qubits
\(|\psi_2\rangle = \frac{1}{\sqrt{2^n}}\big( \sum\,(-)^{f(x)}|x\rangle\,|-\rangle\big)\).
The Hadamard transform on a single qubit can be written as
$H,|x= (|0+ (-)^x,|1) = _{{0,1}}(-)^{x.z}|z$
and by extension you can easily see that on a multi qubit you have
\(H^{\otimes n}\,|x\rangle \frac{1}{\sqrt{2^n}}\sum_{\{0,1\}}(-)^{x.z}|z\rangle\)
where now the product \(x.z\) is the standard inner product of binary vectors. So, upon applying the Hadamard on the n-qubits we get
\(|\psi_3\rangle := H^{\otimes n}\,|\psi_2\rangle\\\;= \frac{1}{\sqrt{2^n}}\big( \sum_x\,(-)^{f(x)}\,H^{\otimes n}\,|x\rangle\,|-\rangle\big)\)
and combining things
\(|\psi_3\rangle := H^{\otimes n}\,|\psi_2\rangle\\\;= \frac{1}{\sqrt{2^n}}\big( \sum_x\,(-)^{f(x)}\,\big( \frac{1}{\sqrt{2^n}}\sum_{z}(-)^{x.z}|z\rangle \big)\,|-\rangle\big)\\\;=\frac{1}{2^n}\sum_{x,z}(-)^{x.z+f(x)}|z\rangle|-\rangle.\)
Consider the \(\otimes^n\,|0\rangle\) state in this sum with coefficient
\(C= \frac{1}{2^n}\sum_{x}(-)^{f(x)}\)
There are two options you can consider:
- the function is constant in which case \(C=\pm 1\) depending on whether the constant map is zero or one. So, measuring this state comes with probability one since the coefficient is plus-minus one.
- the function is not constant but balanced (equally many 0’s and 1’s) in which case the coefficient is zero and one can be certain that measuring this register will never happen.
Put together we can conclude that it takes only one measurement to determine whether the function is constant or balanced. In comparison, a classic algorithm needs at least \(2^{n-1}+1\) queries to determine the same result. So, this extension of the Deutsch algorithm is even more baffling and shows clearly the potention of quantum computing in machine learning and AI.