Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40116

Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

Yunqi Huang, Zekun Ye

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 4, 2026 (v2)
v1 · Sep 30, 2026v2 · Oct 4, 2026
arXivHTMLPDF

Abstract

We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function $f$ on length-$n$ strings over a fixed alphabet of size $q$, invariant under simultaneous coordinate permutations, we prove $R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))$, where $t=\min\{n,Q^{\ast}(f)^2\}$, $R^{\mathrm{pub}}$ denotes public-coin randomized communication complexity, and $Q^{\ast}$ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed $\varepsilon\in(0,1)$, there are binary permutation-invariant partial functions with quantum communication complexity $O_\varepsilon(\log\log n)$ and randomized communication complexity $Ω_\varepsilon((\log n)^{1-\varepsilon})$. We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. Growing alphabets and graph symmetries admit exponential separations. For every fixed $\varepsilon\in(0,1)$, we exhibit permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum communication complexity $O_\varepsilon(\log n)$ and randomized communication complexity $Ω_\varepsilon(n^{1-\varepsilon})$. For graph-invariant partial functions on $v$-vertex graphs, we obtain $O_\varepsilon(\log v)$ quantum versus $Ω_\varepsilon(v^{2-\varepsilon})$ randomized communication complexity. All separation protocols require no prior entanglement.

AI Summary

The paper asks how simultaneous coordinate-permutation symmetry constrains quantum advantages in two-party communication complexity. For every permutation-invariant partial function on $[q]^n\times[q]^n$ with fixed alphabet size $q$, it proves $R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))$, where $t=\min\{n,Q^*(f)^2\}$ and $Q^*$ allows prior entanglement. This extends the previous binary result to fixed larger alphabets and reduces its logarithmic overhead. Disjointness attains the bound when $t=\Theta(n)$. The analysis defines a separation parameter $h$ between oppositely labelled joint-count tables with fixed marginal histograms. It gives classical cost $O_q(u\log(2+n/u))$, with $u=\min\{n,h^{-2}\}$, and quantum bounds $\Omega_q(h^{-1})$ and $O_q(\min\{n,h^{-1}\log n\})$. Classical estimation uses sampling and batch recovery of disagreements; quantum estimation uses coherent sampling and amplitude estimation. The lower bound combines alternating-cycle and maximum-spanning-tree reductions with uniform polynomial approximation derived from multislice contraction and acceptance-matrix factorization. Symmetry-preserving encodings of known communication separations give $Q=O_\varepsilon(\log n)$ versus $R^{\mathrm{pub}}=\Omega_\varepsilon(n^{1-\varepsilon})$ for $n$-symbol inputs with fixed histograms. Graph constructions give analogous separations on copies of one rigid tree, and $\Omega_\varepsilon(v^{2-\varepsilon})$ classical cost for connected graphs with varying isomorphism types. Binary weight encodings yield $Q=O_\varepsilon(\log\log n)$ versus $R^{\mathrm{pub}}=\Omega_\varepsilon((\log n)^{1-\varepsilon})$. The separations concern partial functions. The exponent obstructions do not establish optimality across all parameter regimes or exclude purely quadratic simulation with fixed margins. Alphabet-dependent constants are not fully quantified, and local computation is unrestricted.

Little sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum and Classical Communication Complexity of Permutation-Invariant Functions

Ziyi Guan, Yunqi Huang, Penghui Yao +1 more

This paper gives a nearly tight characterization of the quantum communication complexity of permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of permutation-invariant Boolean functions are quadratically equivalent (up to a polylogarithmic factor of the input size). Our results extend a recent line of research regarding query complexity to communication complexity, showing symmetry prevents exponential quantum speedups. Furthermore, we show that the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a polylogarithmic factor of the input size).

arXiv:2401.00454•IEEE Transactions on Information Theory•Jan 27, 2025•3 citations

Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

Mark Bun, Joao F. Doriguello, John Kallaugher +1 more

We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem. Here, Alice is given an $n$-bit string and Bob is given $Ω(n)$ disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of $f$ on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where $f$ is the parity function. We establish classical and quantum communication bounds for $f$-Boolean Hidden Partition in terms of the sign degree $d$ of $f$, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when $d \le 1$ and quantum protocols when $d \le 2$, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every $f$ of sign degree $d \ge 2$, the randomized classical communication complexity of this problem is $Θ(n^{1-1/d})$ while its quantum communication complexity lies between $Ω(n^{1-2/d})$ and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions $f$ admitting polynomial quantum advantage as those for which $d \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.

quant-pharXiv:2610.06789•Oct 6, 2026•0 citations

Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry

Yunqi Huang, Lvzhou Li, Zekun Ye +1 more

A function $f:\cD\subseteq A^N\to\{0,1\}$ is \emph{permutation-invariant} if every permutation of its input positions preserves both its domain and its value. We study how this symmetry limits quantum speedups. For $1/6\leq\varepsilon<1/2$, we prove that every such function over an arbitrary finite alphabet $A$ satisfies $R_\varepsilon(f)=O(Q_\varepsilon(f)^2)$, where $R_\varepsilon$ and $Q_\varepsilon$ denote randomized and quantum query complexities with error at most $\varepsilon$. This improves the previous cubic bound (ITCS 2019). We further establish bounds for graph and hypergraph properties, for which vertex relabeling preserves both the promise and the answer. For the same range of $\varepsilon$, we obtain $R_\varepsilon(f)=O(Q_\varepsilon(f)^4)$ for graph properties in the adjacency-matrix model and $R_\varepsilon(f)=O_k(Q_\varepsilon(f)^{2k})$ for $k$-uniform hypergraph properties with fixed $k\geq2$, where the implicit constant depends only on $k$. These improve the previous bounds $R_{1/3}(f)=O(Q_{1/3}(f)^6)$ and $R_{1/3}(f)=O_k(Q_{1/3}(f)^{3k})$, respectively (SICOMP 2024) These bounds are tight for permutation-invariant functions and nearly tight for graph and hypergraph properties. Unstructured search gives a matching quadratic separation with $R_{1/3}(f)=Θ\!\left(Q_{1/3}(f)^2\right)$. For every fixed $k\geq 2$, we construct explicit families of invariant promise problems on $k$-uniform hypergraphs satisfying $R_{1/3}(f)\geq Q_{1/3}(f)^{2k-o(1)}$.

arXiv:2611.08919•Nov 6, 2026•0 citations

Trade-Offs Between Entanglement and Communication

Srinivasan Arunachalam, Uma Girish

We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every $k\ge 1$: $Q\|^*$ versus $R2^*$: We show that quantum simultaneous protocols with $\tildeΘ(k^5 \log^3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22]. $R\|^*$ versus $Q\|^*$: We show that classical simultaneous protocols with $\tildeΘ(k \log n)$ qubits of entanglement can exponentially outperform quantum simultaneous protocols with $O(k)$ qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06]. $R\|^*$ versus $R1^*$: We show that classical simultaneous protocols with $\tildeΘ(k\log n)$ qubits of entanglement can exponentially outperform randomized one-way protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication.

arXiv:2306.01233•Leibniz international proceedings in informatics•Jan 1, 2023•4 citations

Communication Complexity of Private Simultaneous Quantum Messages Protocols

Akinori Kawachi, Harumichi Nishimura

The private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, $k$ parties $P_1,\ldots,P_k$ initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs $x_1,\ldots, x_k$. Every $P_i$ generates a quantum message from the private input $x_i$ and the shared random string (entangled states), and then sends it to the referee $R$. Receiving the messages, $R$ computes $F(x_1,\ldots,x_k)$. Then, $R$ learns nothing except for $F(x_1,\ldots,x_k)$ as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound $(3-o(1))n$ of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of $2n$-bit input, which is larger than the trivial upper bound $2n$ of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.

arXiv:2105.07120•Leibniz international proceedings in informatics•Jan 1, 2021•15 citations

The Role of Symmetry in Quantum Query-to-Communication Simulation

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer +3 more

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) is at most 2R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. We show that the O(log n) overhead is required for some functions in the quantum setting, and thus the BCW simulation is tight. We note here that prior to our work, the possibility of Q^{cc}(f o G) = O(Q(f)), for all f and all G in {AND_2, XOR_2}, had not been ruled out. More specifically, we show the following. - We show that the log n overhead is *not* required when f is symmetric, generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). - 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. - 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. - 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 bounded-error communication model.

arXiv:2012.05233•Dec 9, 2020•5 citations
We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function fff on length-nnn strings over a fixed alphabet of size qqq, invariant under simultaneous coordinate permutations, we prove Rpub(f)=Oq(tlog⁡(2+n/t))R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))Rpub(f)=Oq​(tlog(2+n/t)), where t=min⁡{n,Q∗(f)2}t=\min\{n,Q^{\ast}(f)^2\}t=min{n,Q∗(f)2}, RpubR^{\mathrm{pub}}Rpub denotes public-coin randomized communication complexity, and Q∗Q^{\ast}Q∗ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), there are binary permutation-invariant partial functions with quantum communication complexity Oε(log⁡log⁡n)O_\varepsilon(\log\log n)Oε​(loglogn) and randomized communication complexity Ωε((log⁡n)1−ε)Ω_\varepsilon((\log n)^{1-\varepsilon})Ωε​((logn)1−ε). We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor.
Growing alphabets and graph symmetries admit exponential separations. For every fixed ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), we exhibit permutation-invariant partial functions on length-nnn strings over an nnn-symbol alphabet with quantum communication complexity Oε(log⁡n)O_\varepsilon(\log n)Oε​(logn) and randomized communication complexity Ωε(n1−ε)Ω_\varepsilon(n^{1-\varepsilon})Ωε​(n1−ε). For graph-invariant partial functions on vvv-vertex graphs, we obtain Oε(log⁡v)O_\varepsilon(\log v)Oε​(logv) quantum versus Ωε(v2−ε)Ω_\varepsilon(v^{2-\varepsilon})Ωε​(v2−ε) randomized communication complexity. All separation protocols require no prior entanglement.
The paper asks how simultaneous coordinate-permutation symmetry constrains quantum advantages in two-party communication complexity. For every permutation-invariant partial function on [q]n×[q]n[q]^n\times[q]^n[q]n×[q]n with fixed alphabet size qqq, it proves Rpub(f)=Oq(tlog⁡(2+n/t))R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))Rpub(f)=Oq​(tlog(2+n/t)), where t=min⁡{n,Q∗(f)2}t=\min\{n,Q^*(f)^2\}t=min{n,Q∗(f)2} and Q∗Q^*Q∗ allows prior entanglement. This extends the previous binary result to fixed larger alphabets and reduces its logarithmic overhead. Disjointness attains the bound when t=Θ(n)t=\Theta(n)t=Θ(n).
The analysis defines a separation parameter hhh between oppositely labelled joint-count tables with fixed marginal histograms. It gives classical cost Oq(ulog⁡(2+n/u))O_q(u\log(2+n/u))Oq​(ulog(2+n/u)), with u=min⁡{n,h−2}u=\min\{n,h^{-2}\}u=min{n,h−2}, and quantum bounds Ωq(h−1)\Omega_q(h^{-1})Ωq​(h−1) and Oq(min⁡{n,h−1log⁡n})O_q(\min\{n,h^{-1}\log n\})Oq​(min{n,h−1logn}). Classical estimation uses sampling and batch recovery of disagreements; quantum estimation uses coherent sampling and amplitude estimation. The lower bound combines alternating-cycle and maximum-spanning-tree reductions with uniform polynomial approximation derived from multislice contraction and acceptance-matrix factorization.
Symmetry-preserving encodings of known communication separations give Q=Oε(log⁡n)Q=O_\varepsilon(\log n)Q=Oε​(logn) versus Rpub=Ωε(n1−ε)R^{\mathrm{pub}}=\Omega_\varepsilon(n^{1-\varepsilon})Rpub=Ωε​(n1−ε) for nnn-symbol inputs with fixed histograms. Graph constructions give analogous separations on copies of one rigid tree, and Ωε(v2−ε)\Omega_\varepsilon(v^{2-\varepsilon})Ωε​(v2−ε) classical cost for connected graphs with varying isomorphism types. Binary weight encodings yield Q=Oε(log⁡log⁡n)Q=O_\varepsilon(\log\log n)Q=Oε​(loglogn) versus Rpub=Ωε((log⁡n)1−ε)R^{\mathrm{pub}}=\Omega_\varepsilon((\log n)^{1-\varepsilon})Rpub=Ωε​((logn)1−ε).
The separations concern partial functions. The exponent obstructions do not establish optimality across all parameter regimes or exclude purely quadratic simulation with fixed margins. Alphabet-dependent constants are not fully quantified, and local computation is unrestricted.
This paper gives a nearly tight characterization of the quantum communication complexity of permutation-invariant Boolean functions. With such a characterization, we show that the quantum and randomized communication complexity of permutation-invariant Boolean functions are quadratically equivalent (up to a polylogarithmic factor of the input size). Our results extend a recent line of research regarding query complexity to communication complexity, showing symmetry prevents exponential quantum speedups. Furthermore, we show that the Log-rank Conjecture holds for any non-trivial total permutation-invariant Boolean function. Moreover, we establish a relationship between the quantum/classical communication complexity and the approximate rank of permutation-invariant Boolean functions. This implies the correctness of the Log-approximate-rank Conjecture for permutation-invariant Boolean functions in both randomized and quantum settings (up to a polylogarithmic factor of the input size).
We study the one-way communication complexity of the fff-Boolean Hidden Partition problem. Here, Alice is given an nnn-bit string and Bob is given Ω(n)Ω(n)Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of fff on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where fff is the parity function. We establish classical and quantum communication bounds for fff-Boolean Hidden Partition in terms of the sign degree ddd of fff, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when d≤1d \le 1d≤1 and quantum protocols when d≤2d \le 2d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every fff of sign degree d≥2d \ge 2d≥2, the randomized classical communication complexity of this problem is Θ(n1−1/d)Θ(n^{1-1/d})Θ(n1−1/d) while its quantum communication complexity lies between Ω(n1−2/d)Ω(n^{1-2/d})Ω(n1−2/d) and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions fff admitting polynomial quantum advantage as those for which d≥2d \ge 2d≥2, with a new infinite family of exponential separations given by the case d=2d = 2d=2.
A function $f:\cD\subseteq A^N\to\{0,1\}$ is \emph{permutation-invariant} if every permutation of its input positions preserves both its domain and its value. We study how this symmetry limits quantum speedups. For 1/6≤ε<1/21/6\leq\varepsilon<1/21/6≤ε<1/2, we prove that every such function over an arbitrary finite alphabet AAA satisfies Rε(f)=O(Qε(f)2)R_\varepsilon(f)=O(Q_\varepsilon(f)^2)Rε​(f)=O(Qε​(f)2), where RεR_\varepsilonRε​ and QεQ_\varepsilonQε​ denote randomized and quantum query complexities with error at most ε\varepsilonε. This improves the previous cubic bound (ITCS 2019). We further establish bounds for graph and hypergraph properties, for which vertex relabeling preserves both the promise and the answer. For the same range of ε\varepsilonε, we obtain Rε(f)=O(Qε(f)4)R_\varepsilon(f)=O(Q_\varepsilon(f)^4)Rε​(f)=O(Qε​(f)4) for graph properties in the adjacency-matrix model and Rε(f)=Ok(Qε(f)2k)R_\varepsilon(f)=O_k(Q_\varepsilon(f)^{2k})Rε​(f)=Ok​(Qε​(f)2k) for kkk-uniform hypergraph properties with fixed k≥2k\geq2k≥2, where the implicit constant depends only on kkk. These improve the previous bounds R1/3(f)=O(Q1/3(f)6)R_{1/3}(f)=O(Q_{1/3}(f)^6)R1/3​(f)=O(Q1/3​(f)6) and R1/3(f)=Ok(Q1/3(f)3k)R_{1/3}(f)=O_k(Q_{1/3}(f)^{3k})R1/3​(f)=Ok​(Q1/3​(f)3k), respectively (SICOMP 2024) These bounds are tight for permutation-invariant functions and nearly tight for graph and hypergraph properties. Unstructured search gives a matching quadratic separation with R1/3(f)=Θ ⁣(Q1/3(f)2)R_{1/3}(f)=Θ\!\left(Q_{1/3}(f)^2\right)R1/3​(f)=Θ(Q1/3​(f)2). For every fixed k≥2k\geq 2k≥2, we construct explicit families of invariant promise problems on kkk-uniform hypergraphs satisfying R1/3(f)≥Q1/3(f)2k−o(1)R_{1/3}(f)\geq Q_{1/3}(f)^{2k-o(1)}R1/3​(f)≥Q1/3​(f)2k−o(1).
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on nnn bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every k≥1k\ge 1k≥1: Q∥∗Q\|^*Q∥∗ versus R2∗R2^*R2∗: We show that quantum simultaneous protocols with Θ~(k5log⁡3n)\tildeΘ(k^5 \log^3 n)Θ~(k5log3n) qubits of entanglement can exponentially outperform two-way randomized protocols with O(k)O(k)O(k) qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22]. R∥∗R\|^*R∥∗ versus Q∥∗Q\|^*Q∥∗: We show that classical simultaneous protocols with Θ~(klog⁡n)\tildeΘ(k \log n)Θ~(klogn) qubits of entanglement can exponentially outperform quantum simultaneous protocols with O(k)O(k)O(k) qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06]. R∥∗R\|^*R∥∗ versus R1∗R1^*R1∗: We show that classical simultaneous protocols with Θ~(klog⁡n)\tildeΘ(k\log n)Θ~(klogn) qubits of entanglement can exponentially outperform randomized one-way protocols with O(k)O(k)O(k) qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication.
The private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, kkk parties P1,…,PkP_1,\ldots,P_kP1​,…,Pk​ initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs x1,…,xkx_1,\ldots, x_kx1​,…,xk​. Every PiP_iPi​ generates a quantum message from the private input xix_ixi​ and the shared random string (entangled states), and then sends it to the referee RRR. Receiving the messages, RRR computes F(x1,…,xk)F(x_1,\ldots,x_k)F(x1​,…,xk​). Then, RRR learns nothing except for F(x1,…,xk)F(x_1,\ldots,x_k)F(x1​,…,xk​) as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound (3−o(1))n(3-o(1))n(3−o(1))n of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of 2n2n2n-bit input, which is larger than the trivial upper bound 2n2n2n of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.
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) is at most 2R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. We show that the O(log n) overhead is required for some functions in the quantum setting, and thus the BCW simulation is tight. We note here that prior to our work, the possibility of Q^{cc}(f o G) = O(Q(f)), for all f and all G in {AND_2, XOR_2}, had not been ruled out. More specifically, we show the following. - We show that the log n overhead is *not* required when f is symmetric, generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). - 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. - 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. - 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 bounded-error communication model.