When checking that solutions to certain problems are correct, it turns out, you can’t get around the inherent complexity of the quantum world.
Introduction
More than 30 years ago, researchers discovered that hypothetical computers based on the laws of quantum physics would be able to rapidly solve difficult math problems. Ever since then, they’ve sought to pinpoint cases where quantum computers are more powerful than their ordinary “classical” cousins.
For nearly as long, a small band of computer scientists has pursued a related question that gets less attention: Are proofs that exploit quantum physics also more powerful than classical proofs?
In this context, a “proof” is not a series of logical statements that leads to a theorem, as it is in math. Instead, it’s a certificate confirming that a problem has been solved correctly. For example, if you solve a tricky sudoku puzzle, your solution itself is a proof. A computer can easily scan the grid and verify that it’s correct.
