Quantum expanders from any classical Cayley graph expander
| dc.creator | Harrow, Aram W. | |
| dc.date | 2007-09-07 | |
| dc.date | 2007-10-09 | |
| dc.date.accessioned | 2026-07-07T09:44:20Z | |
| dc.date.available | 2026-07-07T09:44:20Z | |
| dc.description | 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 becomes 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 constant-degree constant-gap families of Cayley expander graphs on e.g. the symmetric group, we can construct efficient families of quantum expanders. | |
| dc.description | 5 pages, constant gap. v2. Removed mistaken claim about QSZK. Added references including arXiv:0710.0651 | |
| dc.identifier | https://arxiv.org/abs/0709.1142 | |
| dc.identifier | http://arxiv.org/abs/0709.1142 | |
| dc.identifier | Q. Inf. Comp., vol. 8, no. 8/9, pp. 715-721, 2008. | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/162837 | |
| dc.subject | Quantum Physics | |
| dc.title | Quantum expanders from any classical Cayley graph expander | |
| dc.type | text |