21 December 2012—Four independent groups of scientists say they’ve constructed a special class of quantum computer that could help physicists prove the worth of the potentially more-powerful quantum computers they’ve been working on.
By doing millions of calculations simultaneously, future quantum computers offer the hope of quickly solving problems that would take even the best supercomputers a thousand years to work through. But quantum computing experts have been dogged by a nagging fact: None of the rudimentary systems they’ve produced so far—or could produce in the near future—are powerful enough to prove that they would be faster at solving these complex problems than an ordinary computer.
“It begs the question as to whether quantum computers themselves are indeed necessary,” notes Matthew Broome, a physicist at the University of Queensland, in Brisbane, Australia. Broome is part of a multinational team that built a system that could hold the key to answering that question: The system is called a quantum boson sampling machine, which MIT theorists Scott Aaronson and Aleksandr Arkhipov dreamed up in 2010.
A quantum boson sampling machine consists mainly of a simple set of crisscrossing waveguides. There are as many entrances to the waveguides as there are exits. Aaronson and Arkhipov theorized that if you inject a large number of identical photons (the bosons) into this photonic circuit, it is incredibly difficult to compute where they will come out. And that computation gets much, much harder with each photon you add. “It’s quite astonishing that it’s as difficult as it is,” says Broome.
The boson sampling machine therefore offers a way to use a fairly simple quantum system to solve an intractable problem more efficiently than a classical computer can. The theorists saw it as a way to show that quantum systems really can compute some things better than ordinary computers. Today’s quantum computers are perhaps decades away from being capable of a calculation so big that it would stump a supercomputer. “Boson sampling gives a stronger proof and is technologically far more simple,” says Broome. However, unlike other quantum computing schemes, boson sampling is not “universal”—that is, it can’t be programmed to perform an arbitrary quantum computation.
Quantum optics labs jumped at the chance to test Aaronson and Arkhipov’s theory, in part because they already had the necessary components: a way of generating single photons, optical circuits that don’t lose too many photons, and sensitive detectors. “The nice thing about boson sampling is that what it requires is what we’ve been working quite hard on,” says Ian Walmsley, a quantum optics expert at the University of Oxford who led one of the groups reporting its results this week.
The four research groups built boson sampling machines that differed only in a few details, and each delivered the expected results when injected with three photons. (The Oxford group also did the experiment with four photons.) This amount is small enough to allow even a classical computer to produce an answer in a reasonable amount of time and gives the researchers an opportunity to check the experiments for subtle errors. “Before scaling to tens of photons, what you need to know is how well can you diagnose the imperfections,” says Justin Spring, part of the Oxford team.
(Two groups of researchers reported results this week in Science. Broome’s group consisted of researchers at the University of Queensland and MIT; Walmsley’s group was from Oxford and Shanghai Jiao Tong University, in China. The results from two additional boson sampling machines were posted to ArXiv, an online repository of scientific papers preprints, but have not yet been published in a journal. One paper was by scientists in Vienna and Jena, Germany. The other was by researchers in Milan, Rome, and Niterói, Brazil.)
According to Aaronson, who participated in the Brisbane research, it would take about 30 photons to show that a quantum system can definitively beat a classical computer. At that number, you can still do the conventional computer calculation to check the experiment. But at about 100 photons, he says, no near-future supercomputer could figure it out in a reasonable amount of time, he says.
Even though boson sampling might be much closer to demonstrating a quantum speedup than any “universal” quantum computer in the works, it will still be years before researchers can reach Aaronson and Arkhipov’s magic number. Getting there will take some technological advances, according to Anthony Laing, a quantum optics expert at the University of Bristol who was not involved in any of the four experiments. Scientists would need to improve their ability to reliably generate identical photons, keep the photons from changing during their trip through the circuit and reduce the number that get lost along the way, and detect the photons when they exit.
Progress in detectors “has been impressive,” says Laing. But the most crucial problem may be with the production of photons. Says Broome: “What ideally you want is to push a button and have a single photon come out, so that you could push 20 buttons and have 20 photons come out.” Today’s technology sometimes produces two photons instead of one, messing up the calculation.
If scientists can make a 30-photon or 100-photon boson sampling machine, will they be able to perform any of the wonders that universal quantum computers tempt us with? Cracking strong encryption? Searching huge data sets in an instant? Unlikely. The boson sampling machine solves just its own, rather difficult, problem, and no one has yet dreamed up another use for it. But if all it ever does is prove that other quantum computers are a worthwhile pursuit, it’ll have done its job.