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:
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$;
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$;
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
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.
