Beating Classical Computing Without a Quantum Computer

See allHide authors and affiliations

Science  15 Feb 2013:
Vol. 339, Issue 6121, pp. 767-768
DOI: 10.1126/science.1234061

Quantum computers are expected to be able to solve mathematical problems that are not feasible on a classical computer. Although considerable progress has already been made, building a full-scale quantum computer would require controlled interactions between the quantum bits, or qubits, in order to implement the logic operations required for addition, subtraction, and multiplication. On pages 798 and 794 of this issue, Spring et al. (1) and Broome et al. (2), as well as Tillmann et al. (3), have shown that quantum systems—in this case, photons interacting along waveguides—could outperform a classical computer for certain kinds of matrix calculations without the need for logic operations.

This new method for performing calculations is based on the random walk process, as illustrated in the figure. In a classical random walk, one or more particles travel along a channel or path. At each moment in time, there is a probability PL that a particle will hop over to the channel to its left and a probability PR that it will hop over to the channel to its right. These probabilities may vary as a function of channel number and time. It is assumed that the particles do not interact with each other, so that the total probability of finding a particle in a given output channel is just a sum of the independent probabilities for the individual particles.

A quantum random walk (4) differs from a classical random walk because the particles also have wavelike properties in quantum mechanics. The wavelike properties of a particle are described by its wave function Ψ(x), which depends on its position x. Although a particle propagates as a wave, it will only be detected at a single location. The probability of detection at location x is equal to the square of the magnitude of Ψ(x). As illustrated in panel A of the figure, a particle will spread out as a wave while it propagates through the random walk process, but it will only be detected in a single output channel.

Calculating with quantum random walks.

(A) A classical random walk process in which M particles are initially located in N paths or channels. There is some probability that a particle will hop to an adjacent channel at any moment in time. (B) A quantum random walk process in which the wavelike nature of each particle spreads out among many channels. Nonetheless, each particle will be found in a single channel when its position is measured at the end of the process, as indicated by the two Xs at the bottom in this example. The probability of detecting the photons is proportional to the output of certain matrix calculations (the permanent) and allows these calculations to be performed much faster than with classical algorithms for large N.

The output probability distribution from a quantum random walk process does not simply correspond to a sum of the independent probabilities for the individual particles even if there is no physical interaction between the particles (panel B of the figure). The extra interactions arise because the state of the system must obey the rule that Ψ(x1, x2) = ±Ψ(x2, x1) when two indistinguishable particles are swapped or interchanged. The plus sign applies to particles that are known for historical reasons as bosons, whereas the minus sign applies to particles known as fermions. Applying this rule to the wave function produces an effective attraction between identical bosons and an effective repulsion between identical fermions. For example, the probability of finding two identical fermions at the same location x1 = x2 is zero because that corresponds to Ψ(x1, x1) = −Ψ(x1, x1). These effects are commonly referred to as exchange forces, even though there is no physical interaction between the particles. Roughly speaking, the exchange forces provide an effective interaction that can be used to perform certain calculations.

Spring et al., Broome et al., and Tillmann et al. used indistinguishable particles of light (photons) to implement a quantum random walk of this kind called boson sampling. The photons propagated through a series of conducting channels known as waveguides that were fabricated on the surface of a chip. Neighboring channels were coupled to each other by bringing them sufficiently close together that a photon had some probability of hopping to the adjacent waveguide. The probabilities of detecting the photons in the various output channels were then measured with single-photon detectors. It is possible to fabricate a much larger number of wave-guides on the surface of a chip than were used in these examples, so full-scale implementations should be possible in the future.

The probability of detecting a photon (a boson) in each of the output channels is proportional to the so-called permanent of a matrix (5). The permanent of an N × N matrix is defined as the sum of all products of N elements of the matrix chosen in such a way that each row and column appears only once. The permanent is similar to the more familiar determinant aside from the minus signs that appear in the determinant. There are efficient methods for calculating the determinant of a matrix that use classical computers, but the best-known classical algorithm for calculating the permanent requires an exponentially large number of computational steps and is not feasible for large N. The relevant matrices are related to the coupling coefficients between the N input and output channels, which can be controlled experimentally.

Experiments of this kind provide a simple demonstration of the ability of a quantum system to perform a potentially useful computation without the need for the quantum logic operations required for a general-purpose quantum computer. For larger values of N, this approach may eventually provide the first demonstration of an actual calculation that can be done faster using quantum techniques than could be achieved with a classical computer. In addition, Childs et al. (6) have shown that any calculation can be performed using quantum random walks if quantum logic operations (7, 8) between the photons are also included. The combination of these two techniques may eventually lead to the building of a full-scale quantum computer.



Navigate This Article