Theory of Computing
-------------------
Title     : Quantum Expanders: Motivation and Construction
Authors   : Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma
Volume    : 6
Number    : 3
Pages     : 47-79
URL       : https://theoryofcomputing.org/articles/v006a003

Abstract
--------

We define quantum expanders in a natural way. We 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(2,q) 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) 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 QSZ 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.