Two results about quantum messages

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} ⁿ ×{0,1} ^m →{0,1} we have D ^A→B (f)≤O(Q ^A→B,*·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(logn) for f, whereas every one-way quantum protocol for f receiving a classical proof (protocol of type QCMA) requires communication.