We've covered a lot of the progress that has gone into creating effective quantum computers. Although there has been a good deal of progress in terms of building individual components, we haven't been able to put things together into a complete device. That has left us building small, proof-of-concept systems that are handily outperformed by existing classical systems. Without a large enough system, we can't clearly demonstrate the sort of accelerated performance we predict we'll get from quantum hardware.
Two groups of researchers have now figured out a way to test whether quantum systems really can outperform a classical computer. Their systems, which take advantage of a phenomenon called boson sampling, can't be used to compute any algorithms, so they're not as useful as quantum computers might be. But they can be used to confirm that we're on the right track when it comes to quantum computers.
A quantum computer isn't like our existing computers, where electrons flow through a series of switches. Instead, a carefully prepared quantum system is allowed to evolve, and it is then measured. The system only provides us with an answer because we can map different answers to all the possible states that the system can end up in. Because quantum systems evolve very quickly, it should be possible for these systems to arrive at an answer much faster than a typical computer.
Emphasis on the "should be." Since we haven't been able to build a large system, all the problems we've solved have been so simple that a regular computer could solve them while the quantum mechanics are still setting everything up. What the new papers provide is a test case, a system that we can scale now. It won't provide any general computation abilities, but it will be able to give us a clear yes-or-no answer on whether quantum systems can outperform a classical computer.
Both devices are remarkably similar. Single photons (photons are one example of a boson) enter a system where they run into partial mirrors called beamsplitters, which have a 50/50 probability of reflecting the photons or letting them pass through. At random, the beamsplitters send the photons down one of a series of possible paths—in the demonstration devices, the photons should encounter three beamsplitters before they exit the device and are detected. Because of the quantum nature of the photon, even if it's the only one in the device, it can still create an interference pattern with itself, making calculating the probabilities of it coming out the different exit points rather complex.
Now, make the system bigger, with more potential paths. Then start increasing the number of photons that are sent in at the same time, so that they not only interfere with themselves, but with each other. The difficulty of calculating the probabilities of where photons come out of the device goes up very rapidly—so rapidly that it quickly becomes faster to just measure where the photons come out enough times to figure out the probabilities.
(In fact, the calculations are a problem that falls in the category of #P-complete, a special subgroup of the class of problems that can't be solved simply.)
In these papers, the authors keep things rather small. One used three identical photons sent in at once through any of six possible entry sites, with the paths etched into a silica-on-silicon waveguide; three entry points and six exits for the other. In this configuration, calculating the exit probabilities was rather simple, and it was faster than performing the quantum measurement.
But the key thing is that the calculations and the actual measurements agreed. Technical issues like the loss of photons in the equipment or the tendency of photon sources to sometimes send more than one into the device at a time weren't problematic enough that the calculations disagreed significantly from the real-world measurements.
Matthew Broome, from Australia's University of Queensland and lead author of one of the two papers, told Ars that, although their device didn't outperform a classical computer, it is likely that one that's able to handle roughly 20-30 photons should be be able to beat a computer handily. These results show that there is nothing to stop us from building something of that size tomorrow. "The device is the only technologically feasible proposed quantum device that could demonstrate a superior computing advantage over a classical computer," Broome said.
Broome didn't see any obvious calculations that could be done with his device (and, from his perspective, that wasn't the point of the research anyway). But Ian Walmsley, an author of the other paper, suggested it might be possible to use it to simulate other, less conveniently behaved quantum systems. Beyond that, he said, "We'll have to see what our theorist colleagues come up with."
"There is extremely strong evidence to support that Boson Sampling cannot be simulated efficiently on a classical computer, so demonstrating the Boson Sampling algorithm in the lab with a real quantum computer is strong evidence to show that one can indeed harness a computational advantage with quantum physics," Broome said. And that would provide a clear indication that all the effort put into quantum computing could ultimately pay off.