摘要：We define quantum expanders in a natural way and give twoconstructions of quantum expanders, both based on classical expanderconstructions.The first construction is algebraic, and is based on the constructionof Cayley Ramanujan graphs over the group $\PGL$ given by Lubotzky,Phillips, and Sarnak (1988). The second construction is combinatorial, and is based on aquantum variant of the Zig-Zag product introduced by Reingold,Vadhan, and Wigderson (2000). Both constructions are ofconstant degree, and the second one is explicit.Using another construction of quantum expanders by Ambainis andSmith (2004),we characterize the complexity of comparing andestimating quantum entropies. Specifically, we consider thefollowing task: given two mixed states, each given by a quantumcircuit generating it, decide which mixed state has more entropy.We show that this problem is $\QSZK$—complete (where $\QSZK$ isthe class of languages having a zero-knowledge quantum interactiveprotocol). This problem is very well motivated from a physicalpoint of view. Our proof follows the classical proof structurethat the entropy difference problem is $\SZK$—complete, butcrucially depends on the use of quantum expanders.
