If today’s computers had dreams and ambitions, there would be some problems that they wouldn’t even dream about solving. Some problems would take far too much time or memory, running on for nearly forever. But in an exciting new result, a team of computer scientists have shown how in theory quantum computers should be able to rapidly verify that a practically infinite problem was solved.
Quantum computers were not supposed to be able to do this. One prominent computer scientist and professor at the University of Texas at Austin, Scott Aaronson, called the discovery one of the biggest theoretical “surprises so far in this century”.
Videos by VICE
The new result, still awaiting peer review, comes from the abstract realm of theoretical computer science, where computers are examined through mathematical models and proofs. In this field, scientists can describe epic computers of unlimited power with scribbled definitions on paper.
“You’re not studying these [computers] in order to build anything,” said Thomas Vidick, one coauthor of the study and professor at the California Institute of Technology. Rather, the researchers theorize about quantum computers to understand the complexity of problems that they could solve. “Problems that are so hard that you are setting aside how much time it takes to solve them, and instead focusing on different ways to verify their solution.”
The authors show that quantum computers can rapidly verify the solution to what is known as the halting problem. (In mathematical terms, this can be stated as MIP* = RE.) The halting problem is the problem of determining whether a running program ever comes to a stop. The program must be finite in length, say, 100 lines of code long.
Alan Turing discovered that the halting problem was uncomputable in 1936, when he devised his breakthrough mathematical model of a computer, now known as a Turing machine. In this case, uncomputability means that there is no clever algorithm for solving the halting problem. If a computer simply watched a program run for an arbitrarily long time, then it could eventually determine if a program finally stops. But this strategy doesn’t count as computable, because useful computations must finish in a predictable time, whether that’s one day, or one year, or one billion years.
The new result shows that even something like a run-of-the-mill laptop computer could quickly verify that a halting problem actually halts, however, by checking with two powerful quantum computers. This works even if that program doesn’t halt for, say, ten times longer than the age of the universe.
In the authors’ theory, the quantum computers have practically infinite power—think of computers the size of planets—so it is no surprise that they can solve the halting problem. But if their solution takes all the time and space in the universe, how do they prove it to you and your laptop? Another coauthor of the study, Henry Yuen, professor at the University of Toronto, spoke to Motherboard about the results.
“There’s an intuition from the last nearly 100 years from Turing that the halting problem is not solvable. If we know it’s not solvable, why would we expect that it’s possible for someone to convince you that they solved it? That’s one of the major sources of bewilderment,” Yuen said.
What allows this remarkable feat is quantum entanglement: each quantum computer contains subatomic particles that are entangled with particles in the other computer. When particles are said to be entangled, they seem to share information. In a classic example of two entangled singlet state particles, if the first one is found to spin on an upward axis, then the second one must have a spin that points down, like two dice that always roll to opposite sides.
Entanglement offers a profound communication resource for the two quantum computers. In separate work from 2019, two of the new study’s coauthors, Anand Natarajan and John Wright, showed that entanglement allowed rapid verification of the solution of one class of enormously long problems, called NEEXP problems.
Here’s how it works: The weaker computer (the laptop, in this case) exchanges questions and answers with the powerful quantum computers to verify their solution. These questions and answers involve measurements on entangled particles contained in both quantum computers.
But because of entanglement, measurements on particles in one computer say something about the entangled particles in the other computer, enabling greater knowledge transfer. Natarajan and Wright used entanglement to compress the Q&A verification process for NEEXP problems into a very short time.
But NEEXP problems are still nowhere near as large or as long as the halting problem, whose solution is much harder to verify. The new result gets at the halting problem by figuring out how to compress the questioning procedure multiple times.
“This paper solves the main technical thing,” said Zhengfeng Ji, coauthor and professor at the University of Technology Sydney. “We wanted to make sure there’s a so-called normal form [a mathematical object] we can define, and that first of all it’s powerful enough, and after the compression procedure it’s still a normal form, so that we can apply the compression over and over again.”
In the course of working on the problem, the researchers realized that the computing power of entanglement tied back to deep questions in physics and pure mathematics. A long standing problem in algebraic theory, known as Connes’ embedding conjecture, has been resolved by the new findings—assuming that they stand up to scrutiny after peer review. The findings also resolve a curious problem in the mathematical foundations of quantum physics, known as Tsirelson’s problem.
Tsirelson’s problem concerns two subtly different models of quantum physics. These models try to describe how entangled particles can seem to share information even when located far apart, where they do not interact. At large distances, measurements on two different entangled particles should not affect one another.
One of the entanglement models, called the tensor-product model, captures this behavior by chopping systems of entangled particles into separate, localized subsystems that do not interact. In the other quantum model, called the commuting operator model, reality is treated as a single, indivisible quantum system. But measurements on one part of the system are assumed to have no effect on measurements in other, far-away parts.
Both models have been used by theoretical physicists without understanding how they might be different in practice. The new result establishes that in certain cases, the models of entanglement predict different quantitative results. Physicists might therefore be able to make an experiment that validates one of the entanglement models and rules the other one out.
Experimental tests of entanglement have been the source of great interest since the 1970’s. Physicists have shown in real tests that the amount of correlations between entangled particles is more than would be expected if quantum entanglement did not exist. These differences are captured in formulas known as Bell inequalities.
Bell inequalities directly quantify the famous weirdness of quantum physics, where entangled particles all the way on opposite sides of the universe could seem to communicate instantaneously. The mathematician Greg Kuperberg at the University of California – Davis has done research on mathematical aspects of Bell inequalities.
The new result “is some vast computational extension,” he said. “You [potentially] have a much stronger violation of some kind of Bell inequality,” meaning that quantum physics might be even more weird than was thought. Entanglement might be even stronger. And the computers that one day use quantum physics, verifying impossible problems over immeasurable distances, might seem to us more like gods.
