Noise resilience of proofs of quantumness

Abstract

Achieving quantum computational advantage requires solving a conjectured classically intractable problem on a quantum device. A proof of quantumness is a type of challenge-response protocol inspired by cryptographic protocols in which a classical verifier can certify the quantum advantage of an untrusted prover in an efficient manner. The quantum prover should correctly solve the verifier’s challenges and be accepted, while any polynomial-time classical provers are rejected with exceedingly high probability. The problem with performing such a protocol with near-term quantum devices is that they are prone to errors and, therefore, cannot be relied on to always return correct results. A protocol based around the learning with rounding problem yields circuits with shorter depth, requires fewer qbits than previous protocols, and has by construction some robustness against noise. However, the precise nature of the noise robustness is unknown. This thesis analyses and quantifies the robustness of the quantum prover’s algorithm to noise. Simulating the protocols under different noise models shows that the protocol is resilient to noise up to an error rate of 0.10% for the problem sizes simulated up to 30 qbits. The protocol is most resilient to phase-flip noise, most susceptible to bit-flip noise, and appears to be slightly more resilient to depolarisation noise than bit-flip noise. Of the two constituent tests of the protocol, the bit flip noise affects the success rate of the preimage test more heavily than the equation test. Conversely, the phase flip noise affects the equation test more heavily than the preimage test. With a maximum tolerable error rate of 0.10% obtained from the simple noise models, the protocol is within one order of magnitude of being viable on near-term quantum devices. A more realistic noise model is tested that approximates the noise characteristics of an experimental quantum computer using measured and extended coherencetimes. None of the tested coherence times are low enough to cause the test static to fail. This implies that the protocol could be successfully utilised to prove the quantumness of the experimental computer. These results indicate that the protocol could be suitable for near-term devices, requiring slightly lower noise levels than those of current quantum computers.