Quantum Communication Advantage in

TFNP · 2024

Read Quantum Communication Advantage in by TFNP (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-03296.txt.

Description

Abstract We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-way randomized model. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry ( JACM 2024 ).

Catalog record

CREATORTFNP
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-03296

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Communication Advantage in TFNP Abstract We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-way randomized model. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry ( JACM 2024 ). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication protocols. 1 Introduction A foremost goal in quantum complexity is to demonstrate an exponential quantum advantage. A prevalent theme is that we know how to demonstrate exponential quantum advantage for “structured” problems. For unstructured search, Grover’s algorithm famously only achieves a quadratic speedup, which we know to be tight [ BBBV97 ] . The canonical model for unstructured problems is total boolean functions , f\colon\{0,1\}^{n}\rightarrow\{0,1\} , and we know that for any total boolean function the quantum queries needed to evaluate it is at most a 4th power of the number of classical queries [ ABK+21 ] . The world of communication complexity is not immune to this difficulty, and a superpolynomial quantum communication speedup for total boolean functions is not known. The holy grail is again to have a speedup for a total boolean function, f\colon\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\} . Alas, we do not have any such candidates for a super-cubic speedup, and at the same time we cannot prove that quantum and classical communication complexities are polynomially related like in the query setting. The picture is completely different for partial functions and search problems, which have a promise about the structure of the problem input. A long line of work on partial problems [ BCW99 , Raz99 , BJK04 , GKK+08 , KR11 , Gav16 , Gav19 , Gav21 , GRT22 , LLPY24 ] has culminated in strong separations results: Gavinsky [ Gav16 ] and Girish, Raz, and Tal [ GRT22 ] exhibited partial functions with an exponential separation between the quantum SMP (simultaneous message passing) model and the classical two-way randomized communication model. We employ a different way to impose structure on the problem: we consider total NP search problems, which are relations lying in (the communication analogue of) the complexity class TFNP . The seminal work of Bar-Yossef, Jayram, and Kerenidis [ BJK04 ] showed an exponential quantum–classical separation in the restricted setting of one-way protocols for a total NP search problem (the hidden matching problem). Since then, no progress has been made for TFNP problems. In a recent breakthrough, Yamakawa and Zhandry [ YZ24a ] introduced a new total NP search problem that exhibits an exponential quantum speedup in the query complexity model. Their problem is also considered “unstructured,” because the quantum advantage holds over the uniform distribution, a question raised by Aaronson and Ambainis [ AA14 ] . In this work, we define a communication variant of their problem, called Bipartite NullCodeword , and obtain the strongest quantum–classical communication separation so far for any total NP search problem. Theorem 1 (Main result) . There exists a total two-party search problem S\subseteq\{0,1\}^{N}\times\{0,1\}^{N}\times Q for N=2^{\Theta(n)} that 1. admits a \operatorname{poly}(n) -bit protocol in the quantum SMP model, but 2. requires 2^{n^{\Omega(1)}} bits of communication in the randomized two-way communication model (even under the uniform input distribution), and 3. the relation is classically verifiable (in NP ) and thus the quantum advantage holds in TFNP . The separation in Theorem 1 is qualitatively as strong as one would want. Recall that in a quantum SMP protocol, Alice and Bob send a quantum state to a third-party referee, Charlie, who outputs the answer without further interaction. Even the one-way model can simulate this since Bob can emulate Charlie. Furthermore, our quantum SMP protocol is computationally efficient , i.e, all parties can be implemented using \mathrm{polylog}(N) size quantum circuits with oracle access to the input. This is the same notion of efficiency as in the result of [ GRT22 ] . Our protocol also does not use any shared entanglement or randomness, matching the result of Gavinsky [ Gav21 ] . Besides being fundamental considerations in theoretical computer science, verifiability and efficiency are also desirable properties for a quantum–classical communication complexity separation to be used as an experiment to demonstrate unconditional quantum advantage (a.k.a. quantum information supremacy [ ABK24 ] ). We see our result as a theoretical feasibility result for designing such an experiment based on communication complexity. We compare our result to several other notable quantum–classical communication separations in Table 1 . 1.1 Other related work The Yamakawa–Zhandry problem. The Yamakawa–Zhandry problem [ YZ24a ] was a breakthrough average-case query separation. Since then, it has proven to be useful in other settings, often by modifying the the problem slightly (like we do). Before our work, it was tweaked to make progress on the question of getting an oracle separation of QMA and QCMA [ LLPY24 , BK24a ] . More relevant to our work, Li et al. [ LLPY24 ] also use the Yamakawa–Zhandry problem to get a new separation between one-way quantum and one-way randomized communication complexity. However, their problem is easy in the classical two-way model since Bob’s input is short. Query-to-communication lifting. Most techniques in communication complexity literature which can distinguish quantum and classical communication complexity are tailored to promise problems. One technique that works for total problems (functions and relations) is query-to-communication lifting [ GPW20 , CFK+21 ] . 1 1 1 Lifting theorems show that \operatorname{CC}(f\circ g)=\Omega(\operatorname{Q}(f)) where g is a boolean function gadget, \operatorname{CC} is a communication complexity measure and \operatorname{Q} is a query complexity measure. The current strongest separation for a total boolean function between the quantum and classical two-way communication is cubic: This is achieved by lifting an analogous cubic separation in query complexity obtained by Sherstov, Storozhenko, and Wu [ SSW23 , Theorem 1.5] and independently by Bansal and Sinha [ BS21 , Corollary 1.5] . The exponential quantum query speedup from the Yamakawa–Zhandry problem [ YZ24a ] can also be lifted to communication (Lifted NullCodeword in Table 1 ). Given this, we can obtain an exponential separation between quantum and classical two-way communication for an unstructured relation . However, we do not know how to simulate queries to the input of the original relation for the lifted relation using less than two rounds of communication. This limits us to a two-way vs. two-way separation, as opposed to a quantum SMP vs. classical two-way separation. NP relations vs. partial functions. A partial boolean function can always be converted to a total relation by allowing any output on inputs where the function is undefined; however, the resulting total relation has no guarantees about NP verifiability (even if we started with a verifiable partial function). 2 2 2 We thank an anonymous reviewer for this observation. Our separation for a total relation and the separation of [ GRT22 ] for a partial function are formally incomparable because in our quantum upper bound, we require no entanglement, and our relation is additionally a total NP relation. In a different context, a separation for a total NP relation can be automatically translated to a separation for a partial function. Namely, Ben-David and Kundu [ BK24b ] show how to do this in the query complexity model

Read the complete text