Hidden-State Proofs of Quantumness

Published

October 8, 2024

Author(s)

Carl A. Miller

Abstract

An experimental cryptographic proof of quantumness — that is, a proof, based only on well-studied cryptographic assumptions, that a physical device is performing quantum computations — will be a vital milestone in the progress of quantum information science. However, error tolerance is a persistent challenge for implementing such tests: we need a test that not only can be passed by an efficient quantum prover, but one that can be passed by a prover that exhibits a certain amount of computational error. (Brakerski et al. 2018) introduced a innovative two-round proof of quantumness based on the LWE (Learning With Errors) assumption. However, one of the steps in their protocol (the pre-image test) has low tolerance for error. In this work we present a proof of quantumness which maintains the same circuit structure as (Brakerski et al. 2018) but exhibits a large improvement in robustness for noise. Our protocol is based on cryptographically hiding an extended GHZ state within a sequence of classical bits. Asymptotically, our protocol allows the total probability of error within the circuit to be as high as 1 − Ω(λ−C), where λ is the security parameter and C is a constant that be chosen arbitrarily large. As part of this result, we prove an uncertainty principle over finite abelian groups which may be of independent interest.

Citation

(potentially a different journal, still TBD)

Pub Type

Journals

Download Paper

https://doi.org/10.48550/arXiv.2410.06368

Local Download

Keywords

quantum advantage, quantum supremacy, lattice-based cryptography

Citation

Miller, C. (2024), Hidden-State Proofs of Quantumness, (potentially a different journal, still TBD), [online], https://doi.org/10.48550/arXiv.2410.06368, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=958760 (Accessed October 10, 2025)