Another version of the PCP theorem, not yet proved, specifically deals with the quantum case. Computer scientists suspect that the quantum PCP conjecture is true, and proving it would change our understanding of the complexity of quantum problems. It’s considered arguably the most important open problem in quantum computational complexity theory. But so far, it’s remained unreachable.
Nine years ago, two researchers identified an intermediate goal to help us get there. They came up with a simpler hypothesis, known as the “no low-energy trivial state” (NLTS) conjecture, which would have to be true if the quantum PCP conjecture is true. Proving it wouldn’t necessarily make it any easier to prove the quantum PCP conjecture, but it would resolve some of its most intriguing questions.
Then in June of 2022, in a paper posted to the scientific preprint site arxiv.org, three computer scientists proved the NLTS conjecture. The result has striking implications for computer science and quantum physics.
Comments are closed.