Complexity test offers new perspective on small quantum computers
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 limits of computation
Modern computers, which dwarf their forebears in speed and efficiency, still can't conquer some of the hardest computational problems. Making them even faster probably won't change that.
Computer scientists working in the field of computational complexity theory explore the ultimate limits of computers, cataloguing and classifying a universe of computational problems. For decades, they’ve been stuck on a particular nagging question, which boils down to this: What’s the relationship between solving a problem and checking your work?
Chris Cesare teams up with Emily Edwards and QuICS postdoctoral researcher Bill Fefferman to explain what this question entails and how researchers are tackling it with tools from physics.
This episode of Relatively Certain was produced and edited by Chris Cesare, with contributions from Emily Edwards, Sean Kelley and Kate Delossantos. It features music by Dave Depper, Podington Bear, Kevin MacLeod and Little Glass Men. Relatively Certain is a production of the Joint Quantum Institute, a research partnership between the University of Maryland and the National Institute of Standards and Technology, and you can find it on iTunes, Google Play or Soundcloud.