Is it possible for an efficient classical verifier (a BPP machine) to verify the output of an efficient quantum prover (a BQP machine)?
The answer is Yes. Researchers show that a classical polynomial time verifier (a BPP machine) can interact with an efficient quantum prover (a BQP machine) in order to verify BQP computations. They rely on the additional assumption that the verifier may use post-quantum cryptography that the BQP prover cannot break. They rely on quantum secure classical encryption schemes, such as those based on the learning with errors problem. These schemes can be used to encrypt classical bits (or quantum states) in a way in which an efficient quantum machine cannot extract any information.
This was the QIP 2019 Keynote subject. However, this is only presenting the Arxiv paper and two other late 2018 talks. It is answering questions about determining if a quantum computer has done something quantum and helping answering if Quantum supremacy has been achieved. Quantum supremacy is when quantum computers clearly beat regular computers.
The core of their construction is a measurement protocol, an interactive protocol between an efficient quantum prover and a classical verifier which is used to force the prover to behave as the verifier’s trusted measurement device. To formalize the idea of a measurement protocol, they now describe its completeness and soundness conditions, beginning with a small amount of necessary notation. In our measurement protocol, an honest prover constructs an n qubit quantum state ρ of his choice, and the verifier would like each qubit to be measured in either the standard basis or the Hadamard basis.
They use trapdoor function families. They are ideal families initially and then approximations of these function families are used.
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.