Complexity test offers new perspective on small quantum computers

August 3, 2018 by Chris Cesare, Joint Quantum Institute
Simulating the behavior of quantum particles hopping around on a grid may be one of the first problems tackled by early quantum computers. Credit: E. Edwards/JQI

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 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 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 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 have only recently become reliable. "These devices are now essentially doing quantum sampling, and simulating this is at the heart of our entire field."

To demonstrate the utility of this approach, Gorshkov and several collaborators proved that sampling complexity tracks the easy-to-hard transition of a task that small- and medium-sized quantum computers are expected to perform faster than ordinary computers: boson sampling .

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.

Explore further: Boson sampling with photons found to produce useful output in spite of photon leaks for quantum supremacy

More information: Abhinav Deshpande et al. Dynamical Phase Transitions in Sampling Complexity, Physical Review Letters (2018). DOI: 10.1103/PhysRevLett.121.030501

Related Stories

New quantum computer design to predict molecule properties

May 31, 2018

The standard approach to building a quantum computer with majoranas as building blocks is to convert them into qubits. However, a promising application of quantum computing—quantum chemistry—would require these qubits ...

Researchers successfully simulate a 64-qubit circuit

June 26, 2018

Quantum computers are based on the principles of quantum mechanics. Compared with classical bits, qubits can be at the superposition between zero and one, so a quantum computer composed of qubits can calculate and store more ...

Scientists pinpoint the singularity for quantum computers

October 3, 2017

Researchers from the University of Bristol have discovered that super-powerful quantum computers, which scientists and engineers across the world are racing to build, need to be even more powerful than previously thought ...

Recommended for you

Scientists produce 3-D chemical maps of single bacteria

November 16, 2018

Scientists at the National Synchrotron Light Source II (NSLS-II)—a U.S. Department of Energy (DOE) Office of Science User Facility at DOE's Brookhaven National Laboratory—have used ultrabright x-rays to image single bacteria ...

Quantum science turns social

November 15, 2018

Researchers in a lab at Aarhus University have developed a versatile remote gaming interface that allowed external experts as well as hundreds of citizen scientists all over the world to optimize a quantum gas experiment ...

Bursting bubbles launch bacteria from water to air

November 15, 2018

Wherever there's water, there's bound to be bubbles floating at the surface. From standing puddles, lakes, and streams, to swimming pools, hot tubs, public fountains, and toilets, bubbles are ubiquitous, indoors and out.

Terahertz laser pulses amplify optical phonons in solids

November 15, 2018

A study led by scientists of the Max Planck Institute for the Structure and Dynamics of Matter (MPSD) at the Center for Free-Electron Laser Science in Hamburg/Germany presents evidence of the amplification of optical phonons ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.