Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 58 min ago
PreprintCC BY 4.0arXiv

On Removing Interaction from Quantum Proofs

  • Nicholas Spooner
  • Max Tromanhauser
Open at sourcePDFDOICite

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.

Related

  1. Quantifying Nonstabilizerness of Quantum Codes by Removing the Inert Background
    Yuan Liu, Ke-Mi Xu
    arXivPreprintarXiv licenceFull textMathematical physicsQuantum physics & quantum informationarXiv
  2. Elementary proofs of quantum lower bounds for element distinctness and k-sum
    Andris Ambainis, Martins Kokainis
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. Algebraic Proofs of Quantum Period--TBA Relations
    Min-xin Huang
    arXivPreprintCC BY 4.0Full textHigh-energy & particle physicsarXiv
  4. Natural proofs for quantum state preparation lower bounds
    Christine Li, Natalie Parham
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  5. Zero Knowledge Proofs in Quantum Networks
    Tuhin Paul, Srijani Das, Manasi Patra +1
    arXivPreprintCC BY-SA 4.0Full textMathematical physicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{spooner2026removing,
  title = {{On Removing Interaction from Quantum Proofs}},
  author = {Nicholas Spooner and Max Tromanhauser},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38387},
  eprint = {2609.38387},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38387},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On Removing Interaction from Quantum Proofs
AU  - Nicholas Spooner
AU  - Max Tromanhauser
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.38387
UR  - https://arxiv.org/abs/2609.38387
AB  - 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.
ER  -