Deutsch's Algorithm on a Quantum Computer

​
function
f
1
(x)
f
2
(x)
f
3
(x)
f
4
(x)
random
quantum computation
0
In 1985, David Deutsch[1] proposed a highly contrived but simple algorithm to explore the potentially greater computational power of a quantum computer as compared to a classical computer. Consider four possible functions of a single-bit (or basis qubit)
x=0
or
1
, which produce a single-bit result
f(x)=0
or
1
, as follows:
f
1
(x)=0
,
f
2
(x)=1
,
f
3
(x)=x
,
f
4
(x)=1-x
. The first two functions are classified as "constant" (with
f(0)=f(1)
), while the latter two are described as "balanced" (with
f(0)≠f(1)
). Suppose now that a classical computer, idealized as a "black box", can perform the computation
x→
f
→f(x)
.
To determine whether
f(x)
is constant or balanced on a classical computer, it is necessary to run the program twice, with inputs
x=0
and
x=1
, respectively. For example, with the input
x=0
, suppose we find
f(x)=1
. Then
f
can be either
f
2
or
f
4
. We need a second run with
x=1
to determine which alternative is correct. By contrast, a 2-qubit quantum computer can find the result in a single operation—one shot instead of two.
As shown in the graphic, a black box performing one of the four functions is built into the quantum computer circuit. Our objective is to determine whether this function is constant or balanced. The two qubits
|0〉
and
|1〉
(which can be abbreviated as the quantum state
|01〉)
are input, and the program is executed. The first exit qubit is measured, which collapses it to a classical bit 0 or 1. Very directly, 0 indicates that
f
is constant while 1 indicates that it is balanced. The second exit qubit can be discarded.
You can select one of the four possible functions and run the quantum-computer program. The quantum state of the two-qubit system at each stage of the computation is exhibited, colored in red.

Details

The Hadamard gate
H
transforms the basis qubits into superpositions as follows:
H0=(|0〉+|1〉)
2
, ​
H|1〉=(|0〉-|1〉
)/
2
. The Deutsch gate carries out the following action, showing the incoming and outgoing qubits:
Here
⊕
represents the exclusive or (XOR) Boolean operation on the bits
y
and
f(x)
. The above would be a CNOT gate if
f(x)=x
.
In a generalization to
n
qubits, known as the Deutsch–Jozsa algorithm, a single query on a quantum computer can find a result that would require up to the of order
n
2
queries on a classical computer. Similar fragmentary results show promise of possible exponential gains in computational power using a quantum machine.

References

[1] D. Deutsch, "Quantum Theory, the Church–Turing Principle and the Universal Quantum Computer," Proceedings of the Royal Society of London A, 400, 1985 pp. 97–117.
[2] G. Fano and S. M. Blinder, Twenty-First Century Quantum Mechanics: Hilbert Space to Quantum Computers, Berlin: Springer, 2017, Sect. 6.5.
[3] "Deutsch's Algorithm." (Apr 28, 2017) www.cs.xu.edu/~kinne/quantum/deutche.html.
[4] M. A. Nielson and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, 2010. doi:10.1017/CBO9780511976667.

Permanent Citation

S. M. Blinder
​
​"Deutsch's Algorithm on a Quantum Computer"​
​http://demonstrations.wolfram.com/DeutschsAlgorithmOnAQuantumComputer/​
​Wolfram Demonstrations Project​
​Published: May 4, 2017