On the Cryptographic Structure Required for Verifying Qubits
Abstract
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 P0,P1 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 δ in predicting b from x, there exists a sub-distribution M⪯ D of density (1−δ) 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 δ in guessing a private challenger bit b, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits b1⊕ b2 to at most δ2+negl(λ).
Related
- Trainable, self-verifying variational quantum eigensolver using adiabatic warm starts
- Self-verifying time-resolved multicomponent gas analysis from raw sensor signals
- The Future of AI-assisted Physics: Discovering, Verifying and Organizing Results via Formalization
- Interactive proofs for verifying (quantum) learning and testing
- AeroProp-X: An Open-Source, Self-Verifying Method-of-Characteristics Toolkit for Edge-Capable Rocket Nozzle Design and Aerothermodynamic Analysis
BibTeX
@misc{bartusek2026cryptographic,
title = {{On the Cryptographic Structure Required for Verifying Qubits}},
author = {James Bartusek and Itay Shalit},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.05527},
eprint = {2606.05527},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.05527},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Cryptographic Structure Required for Verifying Qubits
AU - James Bartusek
AU - Itay Shalit
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2606.05527
UR - https://arxiv.org/abs/2606.05527
AB - 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 δ in predicting b from x, there exists a sub-distribution M⪯ D of density (1−δ) 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 δ in guessing a private challenger bit b, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits b_1⊕ b_2 to at most δ^2+negl(λ).
ER -