ETH Zurich and MIT researchers make checking a quantum computer's work far more efficient

[Cameron92]

Quantum Zeitgeist covers a new theory paper from Finn Holler at ETH Zurich and Anand Natarajan at MIT that tackles a surprisingly important question. If you send a calculation to a quantum computer in the cloud, how do you know it did the work correctly? You cannot just rerun it on a classical computer to check, since the whole point is that classical machines cannot do it. This is known as verifying quantum computation

Earlier protocols for this needed verifier resources that grew far too fast as circuits got bigger, making them impractical for anything large. Holler and Natarajan's approach is quasilinear, meaning the classical verifier's work grows roughly in proportion to the size of the quantum circuit. That is a huge improvement. It makes checking large quantum computations practical, at least in theory. Earlier schemes worked in principle but were hopelessly slow in practice

The method works with a single quantum processor and does not require trusting it. It uses something called computational self testing to give the classical side control over the quantum register, and it relies on the Learning With Errors assumption, the same maths behind several post-quantum encryption schemes. The verification error also stays constant however many qubits are involved. The paper is titled Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games

Why does this matter? Most people will access quantum computers through the cloud, just like they use AI today. If you are a bank or a drug company paying for quantum time, you want proof the answer is right, not just a promise. Verification could also be important for any claim of quantum advantage, where sceptics want evidence the machine did what was claimed

This is very much theory rather than something running on real hardware yet, so it will be a while before it is used in practice. Still, it is the kind of foundation work that makes trustworthy quantum cloud services possible. Would you trust a quantum cloud result without some form of proof? And should verification be a requirement for any quantum advantage claim?

Researchers Build Quasilinear Quantum Computation Verifierquantumzeitgeist.com

[Foundry42]

The practical overhead will be the next question. Quasilinear in theory can still mean a large constant factor. Engineers will want to know how it performs on real circuits. Still, the direction is right

[Ivory Cass]

Using Learning With Errors is a neat touch. The same maths protects post-quantum encryption, so it is well studied

Building on trusted foundations makes the result more credible. Lattice problems are having a big decade

[Nadir Compass]

Theory always runs years ahead of hardware in this field. Shor's algorithm was published decades before anyone could run it meaningfully. Hardware still has a lot of catching up to do

[HighKey97]

Verification is one of those problems that sounds abstract until you think about paying for it. Nobody would pay for a calculation they cannot check. This makes the business case for quantum cloud much stronger. Trust is the product

[HeartbreakKidStinger64]

Natarajan is a serious name in quantum complexity theory. He was part of the team behind the MIP* = RE result a few years ago

That paper shook up maths and computer science. When he works on verification, it is worth paying attention