Everyone is welcome to attend the online QuSoft seminar, this week with Nikhil Mande (QuSoft, CWI) on 'Symmetry and Quantum Query-to-Communication Simulation'.
Abstract: Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes the bounded-error 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 R^{cc}(f o G) < 2 R(f), where R^{cc} and R denote bounded-error 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. We improve upon their result in several ways.
1) 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 Set-Disjointness function (Theory of Computing'05). This 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 this, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function.
2) 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-symmetric, 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-symmetric functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unbounded-error model of communication).
Based on joint work with Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Manaswi Paraashar, and Ronald de Wolf (https://arxiv.org/abs/2012.05233)
Please contact Subhasree Patro or Jop Briet for the zoomlink.
