Quantum expanders from any classical Cayley graph expander
Quantum expanders from any classical Cayley graph expander
复制标题
来自任何经典凯莱图扩展器的量子扩展器
DOI：
--
复制
发表时间：
2007
影响因子：
1
通讯作者：
A. Harrow
中科院分区：
文献类型：
--
作者：
A. Harrow
我们给出了一个简单的方法，将群G的Cayley图上的行走转换为G的任意条上的量子运算。经典行走的大多数性质延续到量子运算：度成为Kraus算子的数量，谱间隙下界是量子运算的间隙（被视为密度矩阵上的线性映射），只要G上的经典行走和量子傅里叶变换有效，量子运算就是有效的。这意味着在群（如对称群）上利用经典的常次常间隙凯莱展开图族，我们可以构造有效的量子展开图族。
We give a simple recipe for translating walks on Cayley graphs of a group G into a quantum operation on any irrep of G. Most properties of the classical walk carry over to the quantum operation: degree becomes the number of Kraus operators, the spectral gap lower-bounds the gap of the quantum operation (viewed as a linear map on density matrices), and the quantum operation is efficient whenever the classical walk and the quantum Fourier transform on G are efficient. This means that using classical constantdegree constant-gap families of Cayley expander graphs on groups such as the symmetric group, we can construct efficient families of quantum expanders.