Skip to content
DraconiticResearch
Search Sources API
194,230 studies31 sourcesUpdated 53 min ago
Peer-reviewedCC BY 4.0Quantum

Interactive proofs for verifying (quantum) learning and testing

  • Matthias C. Caro1,2
  • Jens Eisert2,3
  • Marcel Hinsche2
  • Marios Ioannou2
  • Alexander Nietner2
  • Ryan Sweke4,5,6,7
7 affiliations
  1. 1Department of Computer Science, University of Warwick, UK
  2. 2Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin, Germany
  3. 3Helmholtz-Zentrum Berlin für Materialien und Energie, Berlin, Germany
  4. 4IBM Quantum, Almaden Research Center, San Jose, CA, USA
  5. 5African Institute for Mathematical Sciences (AIMS), South Africa
  6. 6Department of Mathematical Sciences, Stellenbosch University, Stellenbosch 7600, South Africa
  7. 7National Institute for Theoretical and Computational Sciences (NITheCS), South Africa
Open at sourcePDFDOICite

Abstract

We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place limitations on the efficiency and feasibility of testing or learning. In particular, we ask the following question: Could a resource-constrained learner/tester use interaction with a resource-unconstrained but untrusted party to solve a learning or testing problem more efficiently than they could without such an interaction? In this work, we answer this question both abstractly and for concrete problems, in two complementary ways: For a wide variety of scenarios, we prove that a resource-constrained learner cannot gain any advantage through classical interaction with an untrusted prover. As a special case, we show that for the vast majority of testing and learning problems in which quantum memory is a meaningful resource, a memory-constrained quantum algorithm cannot overcome its limitations via classical communication with a memory-unconstrained quantum prover. In contrast, when quantum communication is allowed, we construct a variety of interactive proof protocols, for specific learning and testing problems, which allow memory-constrained quantum verifiers to gain significant advantages through delegation to untrusted provers. These results highlight both the limitations and potential of delegating learning and testing problems to resource-rich but untrusted third parties.

Related

  1. On quantum interactive proofs with a laconic prover
    Zihan Hu, Yupan Liu
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
    Kishor Bharti
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Improving student understanding via interactive learning tutorial on quantum key distribution using entanglement
    Liam Doyle, Chandralekha Singh
    arXivPreprintCC BY-NC-ND 4.0Full textQuantum physics & quantum informationarXiv
  4. Trainable, self-verifying variational quantum eigensolver using adiabatic warm starts
    Bojan Žunkovič, Marco Ballarin, Lewis Wright +1
    Physical Review ResearchPeer-reviewedCC BY 4.0Atomic, molecular & optical physicsAPS
  5. Optimal Stabilizer Testing and Learning with Limited Quantum Memory
    Srinivasan Arunachalam, Louis Schatzki
    arXivPreprintCC BY 4.0Full textGeneral mathematicsQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@article{caro2026interactive,
  title = {{Interactive proofs for verifying (quantum) learning and testing}},
  author = {Matthias C. Caro and Jens Eisert and Marcel Hinsche and Marios Ioannou and Alexander Nietner and Ryan Sweke},
  journal = {Quantum},
  year = {2026},
  month = oct,
  doi = {10.22331/q-2026-10-20-2239},
  url = {https://quantum-journal.org/papers/q-2026-10-20-2239/},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - Interactive proofs for verifying (quantum) learning and testing
AU  - Matthias C. Caro
AU  - Jens Eisert
AU  - Marcel Hinsche
AU  - Marios Ioannou
AU  - Alexander Nietner
AU  - Ryan Sweke
PY  - 2026
DA  - 2026/10/20
JO  - Quantum
DO  - 10.22331/q-2026-10-20-2239
UR  - https://quantum-journal.org/papers/q-2026-10-20-2239/
AB  - We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place limitations on the efficiency and feasibility of testing or learning. In particular, we ask the following question: Could a resource-constrained learner/tester use interaction with a resource-unconstrained but untrusted party to solve a learning or testing problem more efficiently than they could without such an interaction? In this work, we answer this question both abstractly and for concrete problems, in two complementary ways: For a wide variety of scenarios, we prove that a resource-constrained learner cannot gain any advantage through classical interaction with an untrusted prover. As a special case, we show that for the vast majority of testing and learning problems in which quantum memory is a meaningful resource, a memory-constrained quantum algorithm cannot overcome its limitations via classical communication with a memory-unconstrained quantum prover. In contrast, when quantum communication is allowed, we construct a variety of interactive proof protocols, for specific learning and testing problems, which allow memory-constrained quantum verifiers to gain significant advantages through delegation to untrusted provers. These results highlight both the limitations and potential of delegating learning and testing problems to resource-rich but untrusted third parties.
SN  - 2521-327X
ER  -