Classical and Quantum Tensor Product Expanders
Abstract
Description
We introduce the concept of quantum tensor product expanders. These are expanders that act on several copies of a given system, where the Kraus operators are tensor products of the Kraus operator on a single system. We begin with the classical case, and show that a classical two-copy expander can be used to produce a quantum expander. We then discuss the quantum case and give applications to the Solovay-Kitaev problem. We give probabilistic constructions in both classical and quantum cases, giving tight bounds on the expectation value of the largest nontrivial eigenvalue in the quantum case.
18 pages. v2 fixed proof and slightly changed statement of Lemma 1. v3 clarified discussion of state randomization, non-Hermitian expanders, and various proof details. Journal version
18 pages. v2 fixed proof and slightly changed statement of Lemma 1. v3 clarified discussion of state randomization, non-Hermitian expanders, and various proof details. Journal version