Limitations of Quantum Advice and One-Way Communication

DOI10.4086/TOC.2005.V001A001MaRDI QIDQ3002754zbMATH OpenOpenAlexFDO

Authors Scott Aaronson

Publication date 24 May 2011

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

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

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

zbMATH Keywords

adviceBQPcommunicationdirect product theoremnonuniformoraclepolynomial methodPPquantum computationrelativized complexity

Mathematics Subject Classification ID

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

Recommendations

• Limits on the ability of quantum states to convey classical messages
• One-time pads cannot be used to improve the efficiency of quantum communication
• QUANTUM LIMITATIONS ON THE STORAGE AND TRANSMISSION OF INFORMATION
• Limitation on the Amount of Accessible Information in a Quantum Channel
• Quantum communication complexity advantage implies violation of a Bell inequality
• Unbounded-Error One-Way Classical and Quantum Communication Complexity
• RESTRICTIONS ON INFORMATION TRANSFER IN QUANTUM MEASUREMENTS
• LIMITATION ON THE ACCESSIBLE INFORMATION FOR QUANTUM CHANNELS WITH INEFFICIENT MEASUREMENTS
• New bounds on classical and quantum one-way communication complexity
• One-way quantum computation

Cited in

(29)

• Hidden cosets and applications to unclonable cryptography
• Secure software leasing from standard assumptions
• Unifying presampling via concentration bounds
• A full characterization of quantum advice
• Two results about quantum messages
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Limitations on quantum dimensionality reduction
• Computational Complexity of Projected Entangled Pair States
• A full characterization of quantum advice
• Limits on the ability of quantum states to convey classical messages
• Quantum lower bounds for approximate counting via Laurent polynomials
• Shadow tomography of quantum states
• Algorithmic Polynomials
• Bounds on the power of proofs and advice in general physical theories
• Quantum computing, postselection, and probabilistic polynomial-time
• Online learning of quantum states
• 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
• A new approach to generic lower bounds. Classical/quantum MDL, quantum factoring, and more
• Classical vs quantum advice and proofs under classically-accessible oracle
• A qubit, a coin, and an advice string walk into a relational problem
• Cumulative memory lower bounds for randomized and quantum computation
• Rewindable quantum computation and its equivalence to cloning and adaptive postselection
• Quantum time-space tradeoff for finding multiple collision pairs
• Quantum time-space tradeoffs for matrix problems
• Uncloneable quantum advice
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• Quantum information and the PCP theorem

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

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