Chakraborty, Sourav ;
Chattopadhyay, Arkadev ;
Høyer, Peter ;
Mande, Nikhil S. ;
Paraashar, Manaswi ;
de Wolf, Ronald
Symmetry and Quantum QueryToCommunication Simulation
Abstract
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {1,1}ⁿ → {1,1} and G ∈ {AND₂, XOR₂}, the boundederror quantum communication complexity of the composed function f∘G equals O(𝖰(f) log n), where 𝖰(f) denotes the boundederror quantum query complexity of f. This is achieved by Alice running the optimal quantum query algorithm for f, using a round of O(log n) qubits of communication to implement each query. This is in contrast with the classical setting, where it is easy to show that 𝖱^{cc}(f∘G) ≤ 2𝖱(f), where 𝖱^{cc} and 𝖱 denote boundederror communication and query complexity, respectively. Chakraborty et al. (CCC'20) exhibited a total function for which the log n overhead in the BCW simulation is required. This established the somewhat surprising fact that quantum reductions are in some cases inherently more expensive than classical reductions. We improve upon their result in several ways.
 We show that the log n overhead is not required when f is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the SetDisjointness function (Theory of Computing'05). Our upper bound assumes a shared entangled state, though for most symmetric functions the assumed number of entangled qubits is less than the communication and hence could be part of the communication.
 In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. This also provides a different, and arguably simpler, proof of Aaronson and Ambainis’s O(√n) communication upper bound for SetDisjointness.
 In view of our first result above, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unboundederror model of communication).
 We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the boundederror communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs.STACS.2022.20,
author = {Chakraborty, Sourav and Chattopadhyay, Arkadev and H{\o}yer, Peter and Mande, Nikhil S. and Paraashar, Manaswi and de Wolf, Ronald},
title = {{Symmetry and Quantum QueryToCommunication Simulation}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {20:120:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15830},
URN = {urn:nbn:de:0030drops158309},
doi = {10.4230/LIPIcs.STACS.2022.20},
annote = {Keywords: Classical and quantum communication complexity, querytocommunicationsimulation, quantum computing}
}
09.03.2022
Keywords: 

Classical and quantum communication complexity, querytocommunicationsimulation, quantum computing 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 