Classical vs quantum advice and proofs under classically-accessible oracle

DOI10.4230/LIPICS.ITCS.2024.72MaRDI QIDQ6906355zbMATH OpenFDO

Authors Xingjian Li, Qipeng Liu, Angelos Pelecanos, Takashi Yamakawa

Publication date 4 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2024.72

zbMATH Keywords

computational complexityquantum computation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A cryptanalytic time-memory trade-off
• A full characterization of quantum advice
• Exponential separation of quantum and classical communication complexity
• Exponential separation of quantum and classical one-way communication complexity
• scientific article; zbMATH DE number 5485520 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• Limitations of Quantum Advice and One-Way Communication
• Polynomial time quantum computation with advice
• Quantum random oracle model with auxiliary input
• Quantum vs. classical proofs and subset verification
• Random Oracles and Auxiliary Input
• Random oracles and non-uniformity
• Random oracles in a quantum world
• The learnability of quantum states
• The Quantum Communication Complexity of Sampling
• Tight quantum time-space tradeoffs for function inversion
• Time space tradeoffs for attacks against one-way functions and PRGs
• Unifying presampling via concentration bounds
• Verifiable quantum advantage without structure

Cited in

(3)

• The role of piracy in quantum proofs
• Oracle separation of QMA and QCMA with bounded adaptivity
• Untelegraphable encryption and its applications

This page was built for publication: Classical vs quantum advice and proofs under classically-accessible oracle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906355)