Mahadev solved this problem in 2018 using LWE. A related problem that remains open is, can we get [[Verifiable Quantum Supremacy]] for [[NISQ]] devices? ### Litteratur - Mahadevs artikkel - [EPRINT:ChiHun23 - Non-Interactive Classical Verification of Quantum Depth: A Fine-Grained Characterization](https://eprint.iacr.org/2023/1911) - "The goal is to demonstrate that a classical verifier can reject a device with a quantum circuit depth of no more than 𝑑, even if the prover employs additional polynomial-time classical computation to deceive."