Quantum expanders and the quantum entropy difference problem

Abstract

We define quantum expanders in a natural way. We show that under certain conditions classical expander constructions generalize to the quantum setting, and in particular so does the Lubotzky, Philips and Sarnak construction of Ramanujan expanders from Cayley graphs of the group PGL. We show that this definition is exactly what is needed for characterizing the complexity of estimating quantum entropies.

30 pages, 1 figure

References in corpus (2)

• Thermodynamics and the Measure of Entanglement
• Approximate Randomization of Quantum States With Fewer Bits of Key

Cited by in corpus (10)

• Superadditivity of communication capacity using entangled inputs
• A quantum version of Wielandt's inequality
• Entanglement vs. gap for one-dimensional spin systems
• How Quantum Are Non-Negative Wavefunctions?
• Efficient Quantum Tensor Product Expanders and k-designs
• Local tests of global entanglement and a counterexample to the generalized area law
• Pseudo-randomness and Learning in Quantum Computation
• An Explicit Construction of Quantum Expanders
• Almost commuting matrices and stability for product groups
• Quantum Expanders and Geometry of Operator Spaces II