pdf icon
Volume 6 (2010) Article 3 pp. 47-79
Quantum Expanders: Motivation and Construction
Received: August 3, 2008
Published: May 2, 2010
Download article from ToC site:
[PDF (396K)]    [PS (1442K)]    [PS.GZ (340K)]
[Source ZIP]
Keywords: quantum expanders, quantum entropy difference, QSZK
ACM Classification: F.2.0, F.2.3
AMS Classification: 81P68, 68Q17

Abstract: [Plain Text Version]

$ \newcommand{\PGL}{\mbox{PGL}(2,q)} \newcommand{\QSZK}{\mbox{QSZK}} \newcommand{\SZK}{\mbox{SZK}} $

We define quantum expanders in a natural way and give two constructions of quantum expanders, both based on classical expander constructions. The first construction is algebraic, and is based on the construction of Cayley Ramanujan graphs over the group $\PGL$ given by Lubotzky, Phillips, and Sarnak (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold, Vadhan, and Wigderson (2000). Both constructions are of constant degree, and the second one is explicit.

Using another construction of quantum expanders by Ambainis and Smith (2004), we characterize the complexity of comparing and estimating quantum entropies. Specifically, we consider the following task: given two mixed states, each given by a quantum circuit generating it, decide which mixed state has more entropy. We show that this problem is $\QSZK$—complete (where $\QSZK$ is the class of languages having a zero-knowledge quantum interactive protocol). This problem is very well motivated from a physical point of view. Our proof follows the classical proof structure that the entropy difference problem is $\SZK$—complete, but crucially depends on the use of quantum expanders.