Hidden-State Proofs of Quantumness

An experimental cryptographic proof of quantumness will be a vital milestone in the progress of quantum information science. 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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-10
Main Author: Miller, Carl A
Format: Article
Language:English
Subjects:
Group theory
Quantum computing
Quantum phenomena
Uncertainty principles
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An experimental cryptographic proof of quantumness will be a vital milestone in the progress of quantum information science. 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 an innovative two-round proof of quantumness based on the Learning With Errors (LWE) 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) while improving the robustness for noise. Our protocol is based on cryptographically hiding an extended Greenberger-Horne-Zeilinger (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 - O ( \lambda^{-C} )\), where \(\lambda\) is the security parameter and \(C\) is a constant that can be made arbitrarily large. As part of the proof of this result, we also prove an uncertainty principle over finite abelian groups which may be of independent interest.
ISSN:2331-8422