Efficient quantum protocols for XOR functions

DOI10.1137/1.9781611973402.136MaRDI QIDQ5384098zbMATH OpenOpenAlexFDO

Authors Shengyu Zhang

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.6738

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: We show that for any Boolean function f on {0,1}^n, the bounded-error quantum communication complexity of XOR functions $fcircoplus$ satisfies that $Q_{e}psilon(fcircoplus)=O(2^d(log|hatf{|}_{1,epsilon}+logfracnepsilon)log(1/epsilon))$, where d is the F2-degree of f, and $|hatf{|}_{1,epsilon}=mi{n}_{g:|f-g{|}_{i}nftyleqepsilon}|hatf{|}_1$. This implies that the previous lower bound $Q_{e}psilon(fcircoplus)=Omega(log|hatf{|}_{1,epsilon})$ by Lee and Shraibman cite{LS09} is tight for f with low F2-degree. The result also confirms the quantum version of the Log-rank Conjecture for low-degree XOR functions. In addition, we show that the exact quantum communication complexity satisfies $Q_E(f)=O(2^{d}log|hatf{|}_0)$, where $|hatf{|}_0$ is the number of nonzero Fourier coefficients of f. This matches the previous lower bound $Q_E(f(x,y))=Omega(logrank(M_f))$ by Buhrman and de Wolf cite{BdW01} for low-degree XOR functions.

Recommendations

• Communication complexities of symmetric XOR functions
• Lower Bounds for Quantum Communication Complexity
• Structure of protocols for XOR functions
• scientific article; zbMATH DE number 5568623
• Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models

Cited in

(14)

• Upper bounds on communication in terms of approximate rank
• Wire-crossings optimization based on majority-of-five and XOR-of-three primitives in QCA
• Dimension-free bounds and structural results in communication complexity
• Norms, XOR lemmas, and lower bounds for polynomials and protocols
• Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models
• Communication complexities of symmetric XOR functions
• Structure of protocols for XOR functions
• Separation of unbounded-error models in multi-party communication complexity
• A short list of equalities induces large sign-rank
• A lifting theorem with applications to symmetric functions
• Implementing a non-local xor function with quantum communication
• Upper bounds on communication in terms of approximate rank
• One-way communication complexity of partial XOR functions
• Perfect parallel repetition theorem for quantum XOR proof systems

This page was built for publication: Efficient quantum protocols for XOR functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384098)