A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs

Abstract

The Bonami-Beckner hypercontractive inequality is a powerful tool in Fourier analysis of real-valued functions on the Boolean cube. In this paper we present a version of this inequality for matrix-valued functions on the Boolean cube. Its proof is based on a powerful inequality by Ball, Carlen, and Lieb. We also present a number of applications. First, we analyze maps that encode $n$ classical bits into $m$ qubits, in such a way that each set of $k$ bits can be recovered with some probability by an appropriate measurement on the quantum encoding; we show that if $m<0.7n$, then the success probability is exponentially small in $k$. This result may be viewed as a direct product version of Nayak's quantum random access code bound. It in turn implies strong direct product theorems for the one-way quantum communication complexity of Disjointness and other problems. Second, we prove that error-correcting codes that are locally decodable with 2 queries require length exponential in the length of the encoded string. This gives what is arguably the first ``non-quantum'' proof of a result originally derived by Kerenidis and de Wolf using quantum information theory, and answers a question by Trevisan.

This is the full version of a paper that will appear in the proceedings of the IEEE FOCS 08 conference

References in corpus (3)

• Sampling of min-entropy relative to quantum knowledge
• Multiparty Communication Complexity of Disjointness
• Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$

Cited by in corpus (29)

• Entropy accumulation
• Entanglement sampling and applications
• Some applications of hypercontractive inequalities in quantum information theory
• Sampling of min-entropy relative to quantum knowledge
• Quantum boolean functions
• Hypercontractivity of quasi-free quantum semigroups
• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
• Quantum Random Access Codes for Boolean Functions
• Exponential Decay of Matrix $\Phi$-Entropies on Markov Semigroups with Applications to Dynamical Evolutions of Quantum Ensembles
• Average-case Speedup for Product Formulas
• Quantum Proofs for Classical Theorems
• A direct product theorem for bounded-round public-coin randomized communication complexity
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Bitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access Codes
• Matrix Poincaré, Φ-Sobolev inequalities, and quantum ensembles
• Direct Sum Theorem for Bounded Round Quantum Communication Complexity
• Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
• Randomness Extraction via Delta-Biased Masking in the Presence of a Quantum Attacker
• On the communication complexity of sparse set disjointness and exists-equal problems
• Quantum Approximation of Normalized Schatten Norms and Applications to Learning
• Simple quantum password checking
• Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem
• Nonlocal games with noisy maximally entangled states are decidable
• $n$-fold unbiased bases: an extension of the MUB condition
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• A Strong Direct Product Theorem for Disjointness
• A near-optimal direct-sum theorem for communication complexity
• Lower Bounds for Approximate LDC