0
$\begingroup$

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.

$\endgroup$

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.