Deutsch's algorithm
Brief introduction to Deutsch's algorithm
Quantum computers pose as the future of computing. Although, at the time of writing, the computing harwdare based on quantum mechanics principles can accommodate only a small number of qubits, algorithms have been developed that demonstrate the superiority of quantum computers for certain class problems.
One such algorithm, and perhaps the simplest one is Deutsch's algorithm. The algorithm solves the following problem [1]
Given a boolean function $f:\{0,1\} \rightarrow \{0,1\}$ determine if $f$ is constant.
The algorithm, can solve the problem with fewer calls to the function $f$ than is possible on a classical machine [1]. A function is called constant if $f(0) = f(1)$. On the other hand, if $f$ is one-to-one, is called balanced [1].
Using a classical computer we need to do two evaluations of the function; one for each of the two inputs [1, 2]. On the other hand, Deutsch's algorithm requires only a single call to a black box to solve the problem. The key to the algorithm is the ability to place the second qubit of the input to the black box in a superposition [2]. Let's see how to do this.
Deutsch's algorithm works by putting both qubits representing the two inputs into a superposition [1]. The way to do this is using the Hadamard gate. The following image shows this schematically.
Figure 1. Deutsch's algorithm circuit. Image from [1].
Let's study how the state system $|\psi\rangle$ evolves. Initially the system is at
$$|\psi \rangle = |01\rangle$$
Appication of the Hadamard gate moves the two qubits respectively to
$$|0 \rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$$
$$ |1 \rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$
Thus, $|\psi\rangle$ will be at
$$|\psi \rangle = \left[\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right]\left[\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right]$$
Let's rename the top qubit as $|x\rangle$. We want to evaluate $f(x)$. Note that when the bottom qubit is put into a superposition and then multiply by $U_f$, the system will be at state [1]
$$|\psi \rangle = (-1)^{f(x)}|x \rangle \left[\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right]$$
Given however that $|x\rangle$ is also in superposition, we will have that the system will be at state [1]
$$|\psi \rangle = \left[ \frac{(-1)^{f(0)}|0 \rangle + (-1)^{f(1)}|1 \rangle}{\sqrt{2}}\right]\left[\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right]$$
The actual state, as shown in the equation above, depends on the values of $f$. We can summarize this as follows [1].
The final step is to apply the Hadamard gate on the top qubit. Recall that the Hadamard matrix is its own inverse. Thus applying it to the top qubit we get [1]
Now, we simply measure the top qubit. If it is in state $|0\rangle$, then we know that f is a constant function [1]. This was all accomplished with only one function evaluation.
One of the nice points demonstared by the algorithm is that a change of basis can allow solving a problem that otherwise requires more questions to the oracle. In Deutsch algorithm, we start in the canonical basis $|01\rangle$. The first application of the Hadamard matrices is used to change the basis to go into a balanced superposition of basic states. While in this noncanonical basis, we evaluate $f$ with the bottom qubit. The last Hadamard matrix is used as a change of basis matrix to revert back to the canonical basis [1].
import numpy as np
import random
H = np.array([[1.0/np.sqrt(2.0), 1.0/np.sqrt(2.0)], [1.0/np.sqrt(2.0), - 1.0/np.sqrt(2.0)]])
def oracle(x, y, constant):
if constant:
f0 = 0 #random.choice([0,1])
f1 = 0 #random.choice([0,1])
else:
f0 = 0 #random.choice([0,1])
f1 = 1 #random.choice([0,1])
return np.array([(-1)**f0*x[0], (-1)**f1*x[1]])
zero = np.array([1., 0.])
one = np.array([0.0, 1.0])
zero_H = np.dot(H, zero)
one_H = np.dot(H, one)
print(zero_H)
print(one_H)
out_oracle = oracle(x=zero_H, y=one_H, constant=True)
x = np.dot(H, out_oracle)
print(x)
out_oracle = oracle(x=zero_H, y=one_H, constant=False)
x = np.dot(H, out_oracle)
print(x)
- Noson S. Yanofsky and Mirco A. Mannucci,
Quantum Computing for Computer Scientists, Cambridge University Press - Eleanor Rieffel, Wolfgang Polak,
Quantum Computing: A Gentle Introduction, The MIT Press. - Deutsch's algorithm