Complexity Test Offers New Perspective on Small Quantum Computers

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 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 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.”

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.

Story by Chris Cesare

Reference Publication
"Dynamical Phase Transitions in Sampling Complexity," Abhinav Deshpande, Bill Fefferman, Minh C. Tran, Michael Foss-Feig, Alexey V. Gorshkov, Phys. Rev. Lett., 121, 030501 (2018)
Research Contact: Abhinav Deshpande, This email address is being protected from spambots. You need JavaScript enabled to view it.: Alexey Gorshkov, This email address is being protected from spambots. You need JavaScript enabled to view it.

Orginal story: https://jqi.umd.edu/news/complexity-test-offers-new-perspective-on-small-quantum-computers

Chris Monroe Co-authors Piece on National Quantum Initiative - The Washington Times

Quantum technology harnesses the radical power of quantum systems — such as isolated atoms, photons and electrons — to transform how we process and communicate information. But that potential can be realized only if our nation’s resources are focused in a way that helps bring quantum research from the laboratory to the marketplace.

Read More

IceCube Neutrinos Point to Long-Sought Cosmic Ray Accelerator

An international team of scientists, with key contributions from researchers at the University of Maryland, has found the first evidence of a source of high-energy cosmic neutrinos—ghostly subatomic particles that travel to Earth unhindered for billions of light years from the most extreme environments in the universe.

Read More

Semiconductor Quantum Transistor Opens the Door for Photon-based Computing

waks for inline

Transistors are tiny switches that form the bedrock of modern computing—billions of them route electrical signals around inside a smartphone, for instance.

Quantum computers will need analogous hardware to manipulate quantum information. But the design constraints for this new technology are stringent, and today’s most advanced processors can’t be repurposed as quantum devices. That’s because quantum information carriers, dubbed qubits, have to follow different rules laid out by quantum physics.

Scientists can use many kinds of quantum particles as qubits, even the photons that make up light. Photons have added appeal because they can swiftly shuttle information over long distances and they are compatible with fabricated chips. However, making a quantum transistor triggered by light has been challenging because it requires that the photons interact with each other, something that doesn’t ordinarily happen on its own.

Now, researchers at the Joint Quantum Institute (JQI), led by JQI Fellow Edo Waks have cleared this hurdle and demonstrated the first single-photon transistor using a semiconductor chip. The device, described in the July 6 issue of Science, is compact: Roughly one million of these new transistors could fit inside a single grain of salt. It is also fast, able to process 10 billion photonic qubits every second.

“Using our transistor, we should be able to perform quantum gates between photons,” says Waks. “Software running on a quantum computer would use a series of such operations to attain exponential speedup for certain computational problems.

The photonic chip is made from a semiconductor with numerous holes in it, making it appear much like a honeycomb. Light entering the chip bounces around and gets trapped by the hole pattern; a small crystal called a quantum dot sits inside the area where the light intensity is strongest. Analogous to conventional computer memory, the dot stores information about photons as they enter the device. The dot can effectively tap into that memory to mediate photon interactions—meaning that the actions of one photon affect others that later arrive at the chip.

“In a single-photon transistor the quantum dot memory must persist long enough to interact with each photonic qubit,” says Shuo Sun, the lead author of the new work who is a Postdoctoral Research Fellow at Stanford University*. “This allows a single photon to switch a bigger stream of photons, which is essential for our device to be considered a transistor.”

To test that the chip operated like a transistor, the researchers examined how the device responded to weak light pulses that usually contained only one photon. In a normal environment, such dim light might barely register. However, in this device, a single photon gets trapped for a long time, registering its presence in the nearby dot.

The team observed that a single photon could, by interacting with the dot, control the transmission of a second light pulse through the device. The first light pulse acts like a key, opening the door for the second photon to enter the chip. If the first pulse didn’t contain any photons, the dot blocked subsequent photons from getting through. This behavior is similar to a conventional transistor where a small voltage controls the passage of current through it’s terminals. Here, the researchers successfully replaced the voltage with a single photon and demonstrated that their quantum transistor could switch a light pulse containing around 30 photons before the quantum dot’s memory ran out.

Waks, who is also a professor in the University of Maryland Department of Electrical and Computer Engineering, said that his team had to test different aspects of the device’s performance prior to getting the transistor to work. “Until now, we had the individual components necessary to make a single photon transistor, but here we combined all of the steps into a single chip,” Waks says.

Sun says that with realistic engineering improvements their approach could allow many quantum light transistors to be linked together. The team hopes that such speedy, highly connected devices will eventually lead to compact quantum computers that process large numbers of photonic qubits.

*Other contributors and affiliations

  • Edo Waks has affiliations with the University of Maryland Department of Electrical and Computer Engineering (ECE), Department of Physics, Joint Quantum Institute, and the Institute for Research in Electronics and Applied Physics (IREAP).
  • Shuo Sun was a UMD graduate student at the time of this research. He is now a postdoctoral research fellow at Stanford University.
  • JQI Fellow Glenn Solomon, a physicist at the National Institute of Standards and Technology, grew the sample used in this research.
  • Hyochul Kim was a postdoctoral research at UMD at the time of the research. He is now at Samsung Advanced Institute of Technology.
  • Zhouchen Luo is currently a UMD ECE graduate student.

Paper reference

"A single-photon switch and transistor enabled by a solid-state quantum memory,” Shuo Sun, Hyochul Kim, Zhouchen Luo, Glenn S. Solomon, and Edo Waks, Science, 361, 57 (2018)

Research contact:

Edo Waks: This email address is being protected from spambots. You need JavaScript enabled to view it.

Quantum Gas Reveals First Signs of Path-bending Monopole

Magnets, whether in the form of a bar, horseshoe or electromagnet, always have two poles. If you break a magnet in half, you’ll end up with two new magnets, each with its own magnetic north and south.

But some physics theories predict the existence of single-pole magnets—a situation akin to electric charges, which come in either positive or negative chunks. One particular incarnation—called the Yang monopole after its discoverer—was originally predicted in the context of high-energy physics, but it has never been observed.

Read More

 

ians