Limitations of Quantum Advice and One-Way Communication

DOI10.4086/toc.2005.v001a001zbMath1213.68278OpenAlexW3103450999MaRDI QIDQ3002754

Scott Aaronson

Publication date: 24 May 2011

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2005.v001a001

zbMATH Keywords

PPcommunicationquantum computationadviceoraclepolynomial methodnonuniformBQPdirect product theoremrelativized complexity

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Trigonometric polynomials, inequalities, extremal problems (42A05) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (17)

Hidden cosets and applications to unclonable cryptography ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Quantum information and the PCP theorem ⋮ Post-quantum simulatable extraction with minimal assumptions: black-box and constant-round ⋮ Collusion resistant copy-protection for watermarkable functionalities ⋮ Non-uniformity and quantum advice in the quantum random oracle model ⋮ Secure software leasing from standard assumptions ⋮ Unifying presampling via concentration bounds ⋮ Shadow Tomography of Quantum States ⋮ Algorithmic Polynomials ⋮ One-way reversible and quantum finite automata with advice ⋮ On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity ⋮ Limitations on Quantum Dimensionality Reduction ⋮ Quantum computing, postselection, and probabilistic polynomial-time ⋮ Unnamed Item ⋮ Computational Complexity of Projected Entangled Pair States ⋮ Online learning of quantum states

This page was built for publication: Limitations of Quantum Advice and One-Way Communication