Complexity Test Offers New Perspective on Small Quantum Computers
August 8, 2018 | Joint Quantum InstituteEstimated reading time: 3 minutes
State-of-the-art quantum devices are not yet large enough to be called full-scale computers. The biggest comprise just a few dozen qubits—a meager count compared to the billions of bits in an ordinary computer’s memory. But steady progress means that these machines now routinely string together 10 or 20 qubits and may soon hold sway over 100 or more.
In the meantime, researchers are busy dreaming up uses for small quantum computers and mapping out the landscape of problems they’ll be suited to solving. A paper by researchers from the Joint Quantum Institute (JQI) and the Joint Center for Quantum Information and Computer Science (QuICS), published recently in Physical Review Letters, argues that a novel non-quantum perspective may help sketch the boundaries of this landscape (link is external) and potentially even reveal new physics in future experiments.
The new perspective involves a mathematical tool—a standard measure of computational difficulty known as sampling complexity—that gauges how easy or hard it is for an ordinary computer to simulate the outcome of a quantum experiment. Because the predictions of quantum physics are probabilistic, a single experiment could never verify that these predictions are accurate. You would need to perform many experiments, just like you would need to flip a coin many times to convince yourself that you’re holding an everyday, unbiased nickel.
If an ordinary computer takes a reasonable amount of time to mimic one run of a quantum experiment—by producing samples with approximately the same probabilities as the real thing—the sampling complexity is low; if it takes a long time, the sampling complexity is high.
Few expect that quantum computers wielding lots of qubits will have low sampling complexity—after all, quantum computers are expected to be more powerful than ordinary computers, so simulating them on your laptop should be hard. But while the power of quantum computers remains unproven, exploring the crossover from low complexity to high complexity could offer fresh insights about the capabilities of early quantum devices, says Alexey Gorshkov, a JQI and QuICS fellow who is a co-author of the new paper.
“Sampling complexity has remained an underappreciated tool,” Gorshkov says, largely because small quantum devices have only recently become reliable. “These devices are now essentially doing quantum sampling, and simulating this is at the heart of our entire field.”
Bosons are one of the two families of fundamental particles (the other being fermions). In general two bosons can interact with one another, but that’s not the case for the boson sampling problem. “Even though they are non-interacting in this problem, bosons are sort of just interesting enough to make boson sampling worth studying,” says Abhinav Deshpande, a graduate student at JQI and QuICS and the lead author of the paper.
In the boson sampling problem, a fixed number of identical particles are allowed to hop around on a grid, spreading out into quantum superpositions over many grid sites. Solving the problem means sampling from this smeared-out quantum probability cloud, something a quantum computer would have no trouble doing.
Deshpande, Gorshkov and their colleagues proved that there is a sharp transition between how easy and hard it is to simulate boson sampling on an ordinary computer. If you start with a few well-separated bosons and only let them hop around briefly, the sampling complexity remains low and the problem is easy to simulate. But if you wait longer, an ordinary computer has no chance of capturing the quantum behavior, and the problem becomes hard to simulate.
The result is intuitive, Deshpande says, since at short times the bosons are still relatively close to their starting positions and not much of their “quantumness” has emerged. For longer times, though, there’s an explosion of possibilities for where any given boson can end up. And because it’s impossible to tell two identical bosons apart from one another, the longer you let them hop around, the more likely they are to quietly swap places and further complicate the quantum probabilities. In this way, the dramatic shift in the sampling complexity is related to a change in the physics: Things don’t get too hard until bosons hop far enough to switch places.
Gorshkov says that looking for changes like this in sampling complexity may help uncover physical transitions in other quantum tasks or experiments. Conversely, a lack of ramping up in complexity may rule out a quantum advantage for devices that are too error-prone. Either way, Gorshkov says, future results arising from this perspective shift should be interesting. “A deeper look into the use of sampling complexity theory from computer science to study quantum many-body physics is bound to teach us something new and exciting about both fields,” he says.
Story by Chris Cesare
Suggested Items
DOCOMO, NTT, NEC and Fujitsu Develop Top-level Sub-terahertz 6G Device
04/12/2024 | JCN NewswireNTT DOCOMO, INC., NTT Corporation, NEC Corporation and Fujitsu Limited jointly announced today the development of a top-level (1) wireless device capable of ultra-high-speed 100 Gbps transmissions in the 100 GHz and 300 GHz sub-terahertz bands.
Scientists Propose a New Way to Search for Dark Matter
04/02/2024 | SLAC National Accelerator LaboratoryEver since its discovery, dark matter has remained invisible to scientists, despite the launch of multiple ultra-sensitive particle detector experiments around the world over several decades.
INSPECTIS Offers Slider Plate Stand for Optical Inspection
04/01/2024 | INSPECTISINSPECTIS introduces a new specialized slider stand capability for repetitive optical inspection tasks, for example, for the production of special devices such as stents.
Ambiq Apollo510 Delivers 30x Power Efficiency Improvement to Unleash Endpoint AI
03/27/2024 | AmbiqAmbiq, a technology leader in exceptionally energy-efficient semiconductors for IoT devices, is introducing the new Apollo510, the first member of the Apollo5 SoC family, which is uniquely positioned to kickstart the age of truly ubiquitous, practical, and meaningful AI.
Commercial Demand Continues to Be the Main Driver of Personal Computing Device Shipments into the GCC Region
03/26/2024 | IDCThe Gulf Cooperation Council (GCC) personal computing device (PCD) market, which is made up of desktops, notebooks, and workstations, declined 4.0% year on year in 2023, with high inventory levels and reduced consumer spending the primary causes.