Quantum advantage for useful problems and its verification

4 problems

• Can classical algorithms match decoded quantum interferometry on polynomial intersection

  Open

  Most quantum methods for hard optimization problems give only modest speedups. A quantum method called decoded quantum interferometry finds better approximate solutions to a structured problem than any known classical method, and it is open whether a classical method can catch up.

• Is the 2025 OTOC(2) quantum echo experiment beyond classical simulation

  Contested

  In 2025 Google measured how information spreads and refocuses on a superconducting chip of 103 qubits and argued that classical computers would need vastly longer to reproduce the numbers. Whether improved classical methods can compute these values to the same accuracy is unsettled.

• Classically verifiable quantum advantage on pre-fault-tolerant hardware

  Open

  Current advantage experiments produce outputs that a classical computer cannot check without redoing the hard calculation. A task that today's noisy machines can perform, that is hard classically, and whose answer is quick to check has not been demonstrated.

• Classical verification of quantum computation without cryptographic assumptions

  Open

  A purely classical user can check a quantum computer's answer if one assumes certain codes are hard to break, or if two separated quantum computers are questioned. Whether one quantum computer can be checked by a classical user with no such assumption is open.