Limitations of Quantum Advice and One-Way Communication
Limitations of Quantum Advice and One-Way Communication
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed.This paper shows in three settings that quantum messages have only limited advantages over classical ones.First, we show that BQP/qpoly ⊆ PP/poly, where BQP/qpoly is …