Abstract
An important open question in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK) $Σ$-protocol for NP using the Fiat-Shamir transformation. Broadbent and Grilo introduced a quantum analog of a $Σ$-protocol (which they call a $Ξ$-protocol) in which the prover's first message is quantum, and show that HVZK $Ξ$-protocols exist for QMA. However, it is not clear how to compile such protocols into NIZKs in the (Q)ROM, because the Fiat-Shamir transformation seems to be incompatible with quantum messages. In this work we give formal evidence that this is indeed the case: we show that if generic "Fiat-Shamir-like" compilers for quantum protocols exist in the QROM (with small completeness and soundness error) then QMA = BQP.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Spooner, N., & Tromanhauser, M. (2026). On Removing Interaction from Quantum Proofs. https://omanscience.com/en/articles/on-removing-interaction-from-quantum-proofs
MLA 9
Spooner, Nicholas, and Max Tromanhauser. "On Removing Interaction from Quantum Proofs." https://omanscience.com/en/articles/on-removing-interaction-from-quantum-proofs.
Chicago (author–date)
Spooner, Nicholas, and Max Tromanhauser. 2026. "On Removing Interaction from Quantum Proofs." https://omanscience.com/en/articles/on-removing-interaction-from-quantum-proofs.
Harvard
Spooner, N. and Tromanhauser, M. (2026) 'On Removing Interaction from Quantum Proofs', Available at: https://omanscience.com/en/articles/on-removing-interaction-from-quantum-proofs.
Vancouver
Spooner N, Tromanhauser M. On Removing Interaction from Quantum Proofs. https://omanscience.com/en/articles/on-removing-interaction-from-quantum-proofs
IEEE
N. Spooner, and M. Tromanhauser, "On Removing Interaction from Quantum Proofs," https://omanscience.com/en/articles/on-removing-interaction-from-quantum-proofs.