Physicists believe that quantum computers are capable of outperforming classical computers for certain tasks. But now researchers at the University of Amsterdam have shown that classical laser pulses can perform one of these tasks – a database search – just as quickly as the quantum approach. Meanwhile, researchers at the University of Science and Technology of China have shown that a riddle known as the prisoner’s dilemma has an unusual outcome when it is treated as a quantum problem.
Imagine you need to search a telephone directory for the name of a person whose phone number you have. Classically, the number of entries you will need to check is of the order of the total number of entries in the directory. But an algorithm developed by Lov Grover in 1997 states that a quantum computer could trace the name after a number of searches roughly equal to the square root of the total number of entries.
In a quantum system, the entries are each assigned a quantum state. The increase in efficiency arises because the directory is in a ‘superposition’ of all the possible states at the beginning of the experiment. This means that the quantum states of all the entries are connected, and as entries are eliminated from the search, the probability of finding the desired entry increases faster than it does in the classical problem, where the entries are not linked.
Robert Spreeuw and colleagues at the University of Amsterdam have now shown that this efficiency can be achieved by bouncing light pulses back and forth inside an optical cavity through a ‘directory’ plate (N Bhattacharya et al 2002 Phys. Rev. Lett. 88 137901). Each round trip is equivalent to one ‘check’ of the directory. The researchers found that the intensity profile of the light pulse is modified by the directory plate in a way that reveals the desired entry after a number of searches that is equal to the square root of the number of entries.
The team admits that – unlike quantum techniques – their method only works for directories with a limited number of entries because its efficiency depends on the width of the light beam used. The database searched by the Amsterdam team had 32 entries.
Elsewhere, Jiangfeng Du and co-workers at the University of Science and Technology of China have used ‘superposition’ to show that the well-known ‘prisoner’s dilemma’ puzzle has a different outcome if it is considered as a quantum problem rather than a classical one (Jiangfeng Du et al 2002 Phys. Rev. Lett. 88 137902).
In the prisoner’s dilemma, two or more suspects are held in separate cells. If the suspects share the blame for a particular crime, they will receive shorter sentences in total. If they blame each other, they could either be released or receive much longer sentences. But the suspects don’t know what their fellow prisoners will decide.
In the classical problem, acting selfishly usually leads to the shortest sentences. But Du and colleagues have shown that collaboration is the best strategy in the quantum version of the problem. They analysed the problem on a quantum computer based on the magnetic spin states of hydrogen nuclei, in which the choices available to the prisoners are initially represented as a superposition of quantum states in the quantum computer. This creates a relationship between the prisoners’ choices that does not exist in the classical problem and leads to a different outcome.
