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.
Read More: Here
