Photonic Boson Sampling in a Tunable Circuit

Computing Power of Quantum Mechanics There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson ). Broome et al. (p. 794 , published online 20 December) and Spring et al. (p. 798 , published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once. Childs et al. (p. 791 ) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation.