# Deutsch's Algorithm on a Quantum Computer

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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) or , which produce a single-bit result or , as follows: , , , . The first two functions are classified as "constant" (with ), while the latter two are described as "balanced" (with ). Suppose now that a classical computer, idealized as a "black box", can perform the computation .

[more]
Contributed by: S. M. Blinder (May 2017)

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

The Hadamard gate transforms the basis qubits into superpositions as follows: , )/. 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 and . The above would be a CNOT gate if .

In a generalization to 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 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