One of the biggest theoretical problems in quantum computing 鈥� just how much they differ from ordinary computers 鈥� has now been solved. The results suggest that these machines are far weirder than we thought.
鈥淚t鈥檚 a big deal because this has been one of the fundamental unsolved problems of quantum complexity theory for a quarter century,鈥� says Scott Aaronson at the University of Texas at Austin.
Quantum computers are devices that solve problems using the weird rules of quantum physics. Unlike ordinary classical computers, which store information in bits that are 0s or 1s, quantum computers use qubits that can be a mixture of both at once.
Advertisement
This difference means quantum computers should be able to solve some problems much faster than ordinary machines. Google, IBM and other organisations are racing to build the first computer capable of demonstrating 鈥渜uantum supremacy鈥� 鈥� the ability to solve problems that would be impractically slow on even a classical supercomputer.
Quantum breakthrough
Now, Ran Raz at Princeton University and Avishay Tal at Stanford University in California have proved that quantum computing isn鈥檛 just a faster way of solving problems, but something much stranger. They have shown that quantum computers could solve a particular set of problems that no classical computer ever could 鈥� even if we let the classical computer 鈥渃heat鈥� by giving it superpowers.
That might sound odd, but it is a common way of thinking amongst theorists like Raz and Tal. They study complexity classes 鈥� essentially sets of problems classified by how difficult they are to solve 鈥� to figure out how computation operates on a fundamental level.
Here, they looked at two classes. The first is called bounded-error quantum polynomial time (BQP), which is essentially the set of all problems solvable by a quantum computer. The second, polynomial hierarchy (PH), is the set of all problems a classical computer can solve if we give it a variety of superpowers, such as the ability to instantly guess correct solutions to a problem, or instantly determine whether a problem has no valid solution.
Clearly, a PH computer is very powerful, but it could likely never be built in the real world. Instead, it serves as a useful tool for studying computation. 鈥淎s abstract and unrealistic as this sounds, we complexity theorists think of the polynomial hierarchy as something recognisable as 鈥榗lassical computation鈥� at its core,鈥� says Henry Yuen of the University of Toronto, Canada.
You can also think of quantum computers as having a superpower 鈥� the ability to exploit quantum physics. Crucially, we believe it can exist in the real world, so the question is, which superpower is better, BQP or PH?
Superpower struggle
To answer this, Raz and Tal have shown that BPQ and PH are not identical 鈥� that there is an esoteric problem about the distribution of random numbers that a quantum computer can solve, but a PH computer cannot. 鈥淭he quantum computing superpower is just so weird and different,鈥� says Yuen, that PH cannot match it, at least for the specific problem they tested.
In other words, even if we make an ordinary computer more powerful than we could possibly expect to achieve in the real world, there are some problems that can only be solved with the power of quantum physics.
Practically speaking, there is unlikely to be any impact on the real-world quantum computers being built by the likes of Google. For one thing, the proof relies on another complexity theorist tool with little bearing in the real world called an 鈥渙racle鈥� 鈥� because, like a mystic sage, it provides instant answers to a question.
But studies of PH have informed Google鈥檚 attempt at quantum supremacy, so it might be possible to use Raz and Tal鈥檚 new result to come up with other ways of practically demonstrating the power of quantum computers.
鈥淚t sharpens our understanding of what makes the quantum computers different from classical computers,鈥� says Yuen. 鈥淭hese theoretical results usually have a way of eventually connecting to something concrete about the real world.鈥�
Reference: Electronic Colloquium on Computational Complexity,
