On the Cryptographic Structure Required for Verifying Qubits

Quantum Physics [Submitted on 4 Jun 2026] On the Cryptographic Structure Required for Verifying Qubits James Bartusek, Itay Shalit Classically testing for the presence of anti-commuting operators on a quantum device is a critical tool underpinning recent progress in classical verification of quantum computation. While such tests can be based on cryptographic assumptions, known constructions rely on highly structured assumptions, e.g. trapdoor claw-free functions. In this work, we seek to explain this state of affairs by constructing strong cryptography from (certain forms of) classical tests of anti-commutation. In particular, we formulate the notion of a test of non-commutation (ToNC), an interactive protocol between a quantum prover and classical verifier in which the prover's final-round response is obtained by measuring one of two binary observables P_0,P_1 depending on the verifier's challenge bit c. We prove that, for a broad range of parameters, ToNC implies classical-communication key agreement (KA), and ToNC combined with one-way functions implies oblivious transfer (OT). Along the way, we develop tools for and provide the first known results on hardness amplification for post-quantum KA and OT, where communication is classical but adversaries may be quantum. In particular, we prove the following results of independent interest. - Post-quantum hard-core measure theorem: For any efficiently sampleable high-min-entropy distribution D over pairs (x,b) such that quantum circuits have advantage at most \delta in predicting b from x, there exists a sub-distribution M\preceq D of density (1-\delta) on which b is nearly optimally quantum-hard to predict. - Post-quantum interactive XOR lemma: Given any classically-interactive protocol, if quantum adversaries have advantage at most \delta in guessing a private challenger bit b, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits b_1\oplus b_2 to at most \delta^2+\rm{negl}(\lambda). Subjects: Quantum Physics (quant-ph); Cryptography and Security (cs.CR) Cite as: arXiv:2606.05527 [quant-ph]   (or arXiv:2606.05527v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2606.05527 Focus to learn more Submission history From: Itay Shalit [view email] [v1] Thu, 4 Jun 2026 00:16:07 UTC (102 KB) Access Paper: view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.CR References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)