Matrix discrepancy from Quantum communication

DOI10.1145/3519935.3519954MaRDI QIDQ6083518zbMATH OpenOpenAlexWikidataFDO

Authors Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

sketchingsemidefinite programmingquantum communication complexitymatrix discrepancyquantum random access codes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We develop a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of the Matrix Spencer conjecture. In particular, we show that for every collection of symmetric $nimesn$ matrices $A_1,ldots,A_n$ with $|A_i|leq1$ and $|A_i{|}_{F}leq{n}^{1/4}$ there exist signs $xin{pm1}^n$ such that the maximum eigenvalue of $su{m}_{ileqn}{x}_i{A}_i$ is at most $O(sqrtn)$. We give a polynomial-time algorithm based on partial coloring and semidefinite programming to find such $x$. Our techniques open a new avenue to use tools from communication complexity and information theory to study discrepancy. The proof of our main result combines a simple compression scheme for transcripts of repeated (quantum) communication protocols with quantum state purification, the Holevo bound from quantum information, and tools from sketching and dimensionality reduction. Our approach also offers a promising avenue to resolve the Matrix Spencer conjecture completely -- we show it is implied by a natural conjecture in quantum communication complexity.

Recommendations

• Quantum communication based on an algorithm of determining a matrix
• Quantum discord in quantum communication protocols
• Quantum discord as a resource in quantum communication
• Problems in the mathematical theory of quantum communication channels
• Quantum mutual information matrices
• Diagonal quantum discord
• Quantum communication through a spin chain with interaction determined by a Jacobi matrix
• Quantum communication complexity
• A matrix inequality for entanglement distillation problem
• Computing coherence vectors and correlation matrices with application to quantum discord quantification

Cited in

(5)

• Weaver's discrepancy for Gaussian random vectors
• Average-case matrix discrepancy: satisfiability bounds
• On the concentration of Gaussian Cayley matrices
• Better sparsifiers for directed Eulerian graphs
• Zero-one laws for random feasibility problems

This page was built for publication: Matrix discrepancy from Quantum communication

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