Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0709.0911

An Explicit Construction of Quantum Expanders

Avraham Ben-Aroya, Oded Schwartz, Amnon Ta‐Shma

Published Sep 6, 2007• 7 citations
arXivHTMLPDF

Abstract

Quantum expanders are a natural generalization of classical expanders. These objects were introduced and studied by Ben-Aroya and Ta-Shma and by Hastings. In this note we show how to construct explicit, constant-degree quantum expanders. The construction is essentially the classical Zig-Zag expander construction, applied to quantum expanders.

DOI
10.48550/arxiv.0709.0911

Related papers

Quantum Expanders: Motivation and Constructions

Avraham Ben-Aroya, Oded Schwartz, Amnon Ta‐Shma

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 et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold et al. (2000). Both constructions are of constant degree, and the second one is explicit. Using quantum expanders, we 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 QSZK 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 resembles the classical proof that the entropy difference problem is SZK-complete, but crucially depends on the use of quantum expanders.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•11 citations

Quantum expanders from any classical Cayley graph expander

Aram W. Harrow

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.

Quantum Information and Computation•Sep 1, 2008•45 citations

Quantum expanders from any classical Cayley graph expander

Aram W. Harrow

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.

arXiv:0709.1142•Sep 7, 2007•0 citations

Quantum margulis expanders

D. Gross, Jens Eisert

We present a simple way to quantize the well-known Margulis expander map. The result is a quantum expander which acts on discrete Wigner functions in the same way the classical Margulis expander acts on probability distributions. The quantum version shares all essential properties of the classical counterpart, e.g., it has the same degree and spectrum. Unlike previous constructions of quantum expanders, our method does not rely on non-Abelian harmonic analysis. Analogues for continuous variable systems are mentioned. Indeed, the construction seems one of the few instances where applications based on discrete and continuous phase space methods can be developed in complete analogy.

arXiv:0710.0651•Quantum Information and Computation•Sep 1, 2008•25 citations

Quantum expanders and the quantum entropy difference problem

Avraham Ben-Aroya, Amnon Ta‐Shma

We define quantum expanders in a natural way. We show that under certain conditions classical expander constructions generalize to the quantum setting, and in particular so does the Lubotzky, Philips and Sarnak construction of Ramanujan expanders from Cayley graphs of the group PGL. We show that this definition is exactly what is needed for characterizing the complexity of estimating quantum entropies.

arXiv:quant-ph/0702129•Feb 13, 2007•30 citations

Quantum expanders from any classical Cayley graph expander

Aram W. Harrow

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. Background. Classical expanders can be defined in either combinatorial or spectral terms, while quantum expanders usually have only a spectral definition. Quantum expanders were introduced in [2] for their application to quantum spin chains and in [5] for applications to quantum statistical zero knowledge. Here we (following [2] and [4]) define a (N, D, λ) quantum expander to be a quantum operation E that • Has N-dimensional input and output. • Has D Kraus operators. • Has second-largest singular value ≤ λ. Equivalently, if E(ρ) = ρ and tr ρσ = 0 then ‖E(σ)‖2 ≤ λ‖σ‖2,

Quantum Information and Computation•Sep 1, 2008•23 citations
Quantum expanders are a natural generalization of classical expanders. These objects were introduced and studied by Ben-Aroya and Ta-Shma and by Hastings. In this note we show how to construct explicit, constant-degree quantum expanders. The construction is essentially the classical Zig-Zag expander construction, applied to quantum expanders.
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 et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold et al. (2000). Both constructions are of constant degree, and the second one is explicit. Using quantum expanders, we 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 QSZK 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 resembles the classical proof that the entropy difference problem is SZK-complete, but crucially depends on the use of quantum expanders.
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.
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.
We present a simple way to quantize the well-known Margulis expander map. The result is a quantum expander which acts on discrete Wigner functions in the same way the classical Margulis expander acts on probability distributions. The quantum version shares all essential properties of the classical counterpart, e.g., it has the same degree and spectrum. Unlike previous constructions of quantum expanders, our method does not rely on non-Abelian harmonic analysis. Analogues for continuous variable systems are mentioned. Indeed, the construction seems one of the few instances where applications based on discrete and continuous phase space methods can be developed in complete analogy.
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. Background. Classical expanders can be defined in either combinatorial or spectral terms, while quantum expanders usually have only a spectral definition. Quantum expanders were introduced in [2] for their application to quantum spin chains and in [5] for applications to quantum statistical zero knowledge. Here we (following [2] and [4]) define a (N, D, λ) quantum expander to be a quantum operation E that • Has N-dimensional input and output. • Has D Kraus operators. • Has second-largest singular value ≤ λ. Equivalently, if E(ρ) = ρ and tr ρσ = 0 then ‖E(σ)‖2 ≤ λ‖σ‖2,