Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable computational quantumness based on a strengthening of trap-door claw-free functions (TCFs).

In the above scheme:

  1. Vicky the classical verifier provides a description of a pair of functions $f_0$ and $f_1$ to Peggy the quantum prover, while saving the trapdoor to $f_0$ and $f_1$;

  2. Peggy prepares, measures, and reports the results of a register in a quantum state to provide a $y$ such that $y=f_0(x_0)=f_1(x_1)$, keeping a superposition of $\vert b\rangle\vert x_b\rangle$;

  3. Vicky asks Peggy to measure the superposition in either (a) the computational basis to provide a bit $b$ and an $x_b$ such that $f_b(x_b)=y$, or (b) in the Hadamard basis to provide a string $d$ orthogonal to $x_0\oplus x_1$; and

  4. Based on Vicky's possession of the trapdoor, Vicky can validate results (she uses the trapdoor to deduce both $x_0$ and $x_1$ from $y$ and Peggy's response above).

The authors instantiate their TCF's with lattice-based learning-with-errors, which, in addition to satisfying hardcore bit requirements, is also a leading candidate for post-quantum cryptography - that is, a cryptographic protocol that is likely secure against a quantum computer. They require post-quantum security for randomness generation, and Mahadev requires post-quantum security for her later breakthrough on classical verification of quantum computing.

But does such a scheme to just prove quantumness also need to be based on post-quantum TCFs?

For example if the trapdoor claw-free function was based on a classically-secure, but quantum-broken, TCF, and if Peggy could be consistent in reporting correct answers to Vicky, then Peggy has shown that either:

  • She has prepared and maintained a quantum superposition of both preimages as intended; or

  • She has broken the TCF with quantum computer to invert $f_b$ to find at least one preimage along with the string $d$.

Either way, she has evidenced computational quantumness.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.