Paper Info
Title
Two Results about Quantum Messages.
Abstract
We prove two results about the relationship between quantum and classical messages. Our first contribution is to show how to replace a quantum message in a one-way communication protocol by a deterministic message, establishing that for all partial Boolean functions f : {0, 1}(n) x {0, 1}(m) -> {0, 1} we have D-A -> B (f) <= O(Q(A -> B),*(f) . m). This bound was previously known for total functions, while for partial functions this improves on results by Aaronson [1,2], in which either a log-factor on the right hand is present, or the left hand side is R-A -> B (f), and in which also no entanglement is allowed. In our second contribution we investigate the power of quantum proofs over classical proofs. We give the first example of a scenario in which quantum proofs lead to exponential savings in computing a Boolean function, for quantum verifiers. The previously only known separation between the power of quantum and classical proofs is in a setting where the input is also quantum [3]. We exhibit a partial Boolean function f, such that there is a one-way quantum communication protocol receiving a quantum proof (i.e., a protocol of type QMA) that has cost O(log n) for f, whereas every one-way quantum protocol for f receiving a classical proof (protocol of type QCMA) requires communication Omega(root n/log n).
Year
DOI
Venue
2014
10.1007/978-3-662-44465-8_38
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8635
0302-9743
Citations 
PageRank 
References 
1
0.34
17
Authors
2
Name
Order
Citations
PageRank
Hartmut Klauck148430.85
Supartha Podder211.02