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

Random Matrices Theory and Application

Non-Hermitian expander obtained with Haar distributed unitaries

Sarah Timhadjelt

Published Apr 24, 2025• 2 citations
Publisher

Abstract

We consider a random quantum channel obtained by taking a selection of [Formula: see text] independent and Haar distributed [Formula: see text]-dimensional unitaries. We follow the argument of Hastings to bound the spectral gap in terms of eigenvalues and adapt it to give an exact estimate of the spectral gap in terms of singular values [7, 8]. This shows that we have constructed a random quantum expander in terms of both singular values and eigenvalues. The lower bound is an analog of the Alon–Boppana bound for [Formula: see text]-regular graphs. The upper bound is obtained using Schwinger–Dyson equations.

DOI
10.1142/s201032632550011x

Related papers

Non-Hermitian expander obtained with Haar distributed unitaries

Sarah Timhadjelt

We consider a random quantum channel obtained by taking a selection of $d$ independent and Haar distributed $N$ dimensional unitaries. We follow the argument of Hastings to bound the spectral gap in terms of eigenvalues and adapt it to give an exact estimate of the spectral gap in terms of singular values \cite{hastings2007random,harrow2007quantum}. This shows that we have constructed a random quantum expander in terms of both singular values and eigenvalues. The lower bound is an analog of the Alon-Boppana bound for $d$-regular graphs. The upper bound is obtained using Schwinger-Dyson equations.

arXiv:2406.10029•Jun 14, 2024•0 citations

On the spectral gap of random quantum channels

Carlos E. González-Guillén, Marius Junge, Ion Nechita

In this work, we prove a lower bound on the difference between the first and second singular values of quantum channels induced by random isometries, that is tight in the scaling of the number of Kraus operators. This allows us to give an upper bound on the difference between the first and second largest (in modulus) eigenvalues of random channels with same large input and output dimensions for finite number of Kraus operators $k\geq 169$. Moreover, we show that these random quantum channels are quantum expanders, answering a question posed by Hastings. As an application, we show that ground states of infinite 1D spin chains, which are well-approximated by matrix product states, fulfill a principle of maximum entropy.

arXiv:1811.08847•Nov 21, 2018•6 citations

Random unitaries give quantum expanders

M. B. Hastings

We show that randomly choosing the matrices in a completely positive map from the unitary group gives a quantum expander. We consider Hermitian and non-Hermitian cases, and we provide asymptotically tight bounds in the Hermitian case on the typical value of the second largest eigenvalue. The key idea is the use of Schwinger-Dyson equations from lattice gauge theory to efficiently compute averages over the unitary group.

arXiv:0706.0556•Physical Review A•Sep 13, 2007•93 citations

Optimal Quantum (Tensor Product) Expanders From Unitary Designs

Cécilia Lancien

Abstract In this work we investigate how quantum expanders (i.e., quantum channels with few Kraus operators but a large spectral gap) can be constructed from unitary designs. Concretely, we prove that a random quantum channel whose Kraus operators are independent unitaries sampled from a $2$-design measure is with high probability an optimal expander (in the sense that its spectral gap is as large as possible). More generally, we show that, if these Kraus operators are independent unitaries of the form $U^{\otimes k}$, with $U$ sampled from a $2k$-design measure, then the corresponding random quantum channel is typically an optimal $k$-copy tensor product expander, a concept introduced by Harrow and Hastings (Quant. Inf. Comput. 2009).

arXiv:2409.17971•International Mathematics Research Notices•Dec 30, 2025•1 citation

Quantum random walks on d-regular graphs with Haar-random coin operators

Alice C. Quillen

With unitary coin operator that is a random matrix drawn from a uniform distribution with respect to the Haar measure, we construct a variant of a discrete quantum random walk using a d-regular undirected connected simple graph. With each step of the walk, the coin operator random matrix is drawn independently from the distribution. The expectation value over the distribution of random unitaries for the associated quantum channel gives a depolarization channel for the coin subspace and resembles the associated classical random walk where the direction a walker steps depends upon the outcome of a fair coin or balanced d-sided dice. Remarkably, despite the fact that the averaged channel depolarizes the coin subspace, measurements in the vertex subspace can be designed that would reveal information about the initial quantum state, even after many iterations of the channel. We illustrate with examples of quantum walks on Cayley graphs of Abelian groups, such as the cycle and hypercube graphs. For Cayley graphs of Abelian groups, the averaged channel is dephasing in the Fourier basis. These quantum walks are examples of bipartite strongly interacting systems, where one subsystem is strongly perturbed, yet information about the initial state in the other subsystem is potentially measurable forever. Due to its decoherence, a quantum random walk with a Haar-random coin would not be useful in search algorithms but could aid in understanding quantum systems with strongly perturbed subsystems.

quant-pharXiv:2607.04584•Physical Review A•Jul 7, 2026•0 citations

An upper bound on quantum capacity of unital quantum channels

Anurag Anshu

We analyze the quantum capacity of a unital quantum channel, using ideas from the proof of near-optimality of Petz recovery map [Barnum and Knill 2000] and give an upper bound on the quantum capacity in terms of regularized output 2-norm of the channel. We also show that any code attempting to exceed this upper bound must incur large error in decoding, which can be viewed as a weaker version of the strong converse results for quantum capacity. As an application, we find nearly matching upper and lower bounds (up to an additive constant) on the quantum capacity of quantum expander channels. Using these techniques, we further conclude that the `mixture of random unitaries' channels arising in the construction of quantum expanders in [Hastings 2007] show a trend in multiplicativity of output 2-norm similar to that exhibited in [Montanaro 2013] for output œ-norm of random quantum channels.

arXiv:1611.09248•IEEE Information Theory Workshop (ITW)•Nov 1, 2017•1 citation
We consider a random quantum channel obtained by taking a selection of [Formula: see text] independent and Haar distributed [Formula: see text]-dimensional unitaries. We follow the argument of Hastings to bound the spectral gap in terms of eigenvalues and adapt it to give an exact estimate of the spectral gap in terms of singular values [7, 8]. This shows that we have constructed a random quantum expander in terms of both singular values and eigenvalues. The lower bound is an analog of the Alon–Boppana bound for [Formula: see text]-regular graphs. The upper bound is obtained using Schwinger–Dyson equations.
We consider a random quantum channel obtained by taking a selection of ddd independent and Haar distributed NNN dimensional unitaries. We follow the argument of Hastings to bound the spectral gap in terms of eigenvalues and adapt it to give an exact estimate of the spectral gap in terms of singular values \cite{hastings2007random,harrow2007quantum}. This shows that we have constructed a random quantum expander in terms of both singular values and eigenvalues. The lower bound is an analog of the Alon-Boppana bound for ddd-regular graphs. The upper bound is obtained using Schwinger-Dyson equations.
In this work, we prove a lower bound on the difference between the first and second singular values of quantum channels induced by random isometries, that is tight in the scaling of the number of Kraus operators. This allows us to give an upper bound on the difference between the first and second largest (in modulus) eigenvalues of random channels with same large input and output dimensions for finite number of Kraus operators k≥169k\geq 169k≥169. Moreover, we show that these random quantum channels are quantum expanders, answering a question posed by Hastings. As an application, we show that ground states of infinite 1D spin chains, which are well-approximated by matrix product states, fulfill a principle of maximum entropy.
Abstract In this work we investigate how quantum expanders (i.e., quantum channels with few Kraus operators but a large spectral gap) can be constructed from unitary designs. Concretely, we prove that a random quantum channel whose Kraus operators are independent unitaries sampled from a 222-design measure is with high probability an optimal expander (in the sense that its spectral gap is as large as possible). More generally, we show that, if these Kraus operators are independent unitaries of the form U⊗kU^{\otimes k}U⊗k, with UUU sampled from a 2k2k2k-design measure, then the corresponding random quantum channel is typically an optimal kkk-copy tensor product expander, a concept introduced by Harrow and Hastings (Quant. Inf. Comput. 2009).
With unitary coin operator that is a random matrix drawn from a uniform distribution with respect to the Haar measure, we construct a variant of a discrete quantum random walk using a d-regular undirected connected simple graph. With each step of the walk, the coin operator random matrix is drawn independently from the distribution. The expectation value over the distribution of random unitaries for the associated quantum channel gives a depolarization channel for the coin subspace and resembles the associated classical random walk where the direction a walker steps depends upon the outcome of a fair coin or balanced d-sided dice. Remarkably, despite the fact that the averaged channel depolarizes the coin subspace, measurements in the vertex subspace can be designed that would reveal information about the initial quantum state, even after many iterations of the channel. We illustrate with examples of quantum walks on Cayley graphs of Abelian groups, such as the cycle and hypercube graphs. For Cayley graphs of Abelian groups, the averaged channel is dephasing in the Fourier basis. These quantum walks are examples of bipartite strongly interacting systems, where one subsystem is strongly perturbed, yet information about the initial state in the other subsystem is potentially measurable forever. Due to its decoherence, a quantum random walk with a Haar-random coin would not be useful in search algorithms but could aid in understanding quantum systems with strongly perturbed subsystems.
We analyze the quantum capacity of a unital quantum channel, using ideas from the proof of near-optimality of Petz recovery map [Barnum and Knill 2000] and give an upper bound on the quantum capacity in terms of regularized output 2-norm of the channel. We also show that any code attempting to exceed this upper bound must incur large error in decoding, which can be viewed as a weaker version of the strong converse results for quantum capacity. As an application, we find nearly matching upper and lower bounds (up to an additive constant) on the quantum capacity of quantum expander channels. Using these techniques, we further conclude that the `mixture of random unitaries' channels arising in the construction of quantum expanders in [Hastings 2007] show a trend in multiplicativity of output 2-norm similar to that exhibited in [Montanaro 2013] for output œ-norm of random quantum channels.