WOLFRAM|DEMONSTRATIONS PROJECT

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.