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:2409.17971 · International Mathematics Research Notices

Optimal Quantum (Tensor Product) Expanders From Unitary Designs

Cécilia Lancien

Published Dec 30, 2025• 5 citations
arXivHTMLPDF

Abstract

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).

DOI
10.1093/imrn/rnaf383

Related papers

Concentration of Quantum Channels With Random Kraus Operators via Matrix Bernstein Inequality

Motohisa Fukuda

Abstract. In this study, we generate quantum channels with random Kraus operators to typically obtain almost twirling quantum channels and quantum expanders. To prove the concentration phenomena, we use matrix Bernstein’s inequality. In this way, our random models do not utilize Haar-distributed unitary matrices or Gaussian matrices. Rather, as in the preceding research, we use unitary t-designs to generate mixed tensor-product unitary channels acting on Cdt. Although our bounds in Schatten p-norm are valid only for 1 ≤p≤ 2, we show that they are typically quantum ϵ-twirling channels with the tail bound proportional to 1/poly(dt), while such bounds were previously constants. The number of required Kraus operators was also improved by powers of logdandt, to be proportional todtlogd/ϵ2. Such random quantum channels are also typically quantum expanders, but the number of Kraus operators must grow proportionally totlogdin our case. Finally, a new non-unital model of super-operators generated by bounded and isotropic random Kraus operators was introduced, which can be typically rectified to yield almost randomizing quantum channels and quantum expanders.

arXiv:2409.06862•IEEE Transactions on Information Theory•May 5, 2025•3 citations

Classical and quantum tensor product expanders

M. B. Hastings, Aram W. Harrow

We introduce the concept of quantum tensor product expanders. These generalize the concept of quantum expanders, which are quantum maps that are efficient randomizers and use only a small number of Kraus operators. Quantum tensor product expanders 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.

arXiv:0804.0011•Quantum Information and Computation•Mar 1, 2009•61 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•19 citations

Efficient quantum tensor product expanders and unitary t-designs via the zigzag product

Sen, Pranab

A classical t-tensor product expander is a natural way of formalising correlated walks of t particles on a regular expander graph. A quantum t-tensor product expander is a completely positive trace preserving map that is a straightforward analogue of a classical t-tensor product expander. Interest in these maps arises from the fact that iterating a quantum t-tensor product expander gives us a unitary t-design, which has many applications to quantum computation and information. We show that the zigzag product of a high dimensional quantum expander (i.e. t = 1) of moderate degree with a moderate dimensional quantum t-tensor product expander of low degree gives us a high dimensional quantum t-tensor product expander of low degree. Previously such a result was known only for quantum expanders i.e. t = 1. Using the zigzag product we give efficient constructions of quantum t-tensor product expanders in dimension D where t = polylog(D). We then show how replacing the zigzag product by the generalised zigzag product leads to almost-Ramanujan quantum tensor product expanders i.e. having near-optimal almost quadratic tradeoff between the degree and the second largest singular value. Both the products give better tradeoffs between the degree and second largest singular value than what was previously known for efficient constructions.

arXiv:1808.10521•Aug 30, 2018•13 citations

Epsilon-Nets, Unitary Designs, and Random Quantum Circuits

Michał Oszmaniec, Adam Sawicki, Michał Horodecki

Epsilon-nets and approximate unitary$t$-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for$d$dimensional Hilbert space, unitaries constituting$\delta $-approximate$t$-expanders form$\epsilon $-nets for$t\simeq \frac {d^{5/2}}{ \epsilon }$and$\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}$. We also show that for arbitrary$t$,$\epsilon $-nets can be used to construct$\delta $-approximate unitary$t$-designs for$\delta \simeq \epsilon t$, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary$t$design necessary to obtain an$\epsilon $-net must grow at least as fast as$\frac {1}{ \epsilon }$(for fixed dimension) and not slower than$d^{2}$(for fixed$\epsilon $). This shows near optimality of our result connecting$t$-designs and$\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.

arXiv:2007.10885•IEEE Transactions on Information Theory•Nov 13, 2021•41 citations

Random unitary circuits with constant spectral gap

Tim Baer, Jeongwan Haah

We prove constant lower bounds for the spectral gap of the following random walks on unitary groups $\mathsf{SU}(2^n)$ on $n$ qubits. (i) Random Pauli Rotation: choose an $n$-qubit Pauli operator $P$ and an angle $θ\in [0,2π)$, both uniformly at random, and apply $e^{\mathrm i θP}$. (ii) Brickwork Random Unitary Circuit: choose $n-1$ unitaries $U_{i}$ uniformly at random from $\mathsf{SU}(4)$ (including central phases of the parent group) independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$. Importantly, the gap bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary $t$-designs after $\mathcal{O}(nt)$ steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be $\mathcal{O}(2^{cn})$ for some $c < 1$. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal $t$-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for $t=2$.

quant-pharXiv:2607.20919•Jul 24, 2026•8 citations
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).
Abstract. In this study, we generate quantum channels with random Kraus operators to typically obtain almost twirling quantum channels and quantum expanders. To prove the concentration phenomena, we use matrix Bernstein’s inequality. In this way, our random models do not utilize Haar-distributed unitary matrices or Gaussian matrices. Rather, as in the preceding research, we use unitary t-designs to generate mixed tensor-product unitary channels acting on Cdt. Although our bounds in Schatten p-norm are valid only for 1 ≤p≤ 2, we show that they are typically quantum ϵ-twirling channels with the tail bound proportional to 1/poly(dt), while such bounds were previously constants. The number of required Kraus operators was also improved by powers of logdandt, to be proportional todtlogd/ϵ2. Such random quantum channels are also typically quantum expanders, but the number of Kraus operators must grow proportionally totlogdin our case. Finally, a new non-unital model of super-operators generated by bounded and isotropic random Kraus operators was introduced, which can be typically rectified to yield almost randomizing quantum channels and quantum expanders.
We introduce the concept of quantum tensor product expanders. These generalize the concept of quantum expanders, which are quantum maps that are efficient randomizers and use only a small number of Kraus operators. Quantum tensor product expanders 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.
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.
A classical t-tensor product expander is a natural way of formalising correlated walks of t particles on a regular expander graph. A quantum t-tensor product expander is a completely positive trace preserving map that is a straightforward analogue of a classical t-tensor product expander. Interest in these maps arises from the fact that iterating a quantum t-tensor product expander gives us a unitary t-design, which has many applications to quantum computation and information. We show that the zigzag product of a high dimensional quantum expander (i.e. t = 1) of moderate degree with a moderate dimensional quantum t-tensor product expander of low degree gives us a high dimensional quantum t-tensor product expander of low degree. Previously such a result was known only for quantum expanders i.e. t = 1. Using the zigzag product we give efficient constructions of quantum t-tensor product expanders in dimension D where t = polylog(D). We then show how replacing the zigzag product by the generalised zigzag product leads to almost-Ramanujan quantum tensor product expanders i.e. having near-optimal almost quadratic tradeoff between the degree and the second largest singular value. Both the products give better tradeoffs between the degree and second largest singular value than what was previously known for efficient constructions.
Epsilon-nets and approximate unitaryttt-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, forddddimensional Hilbert space, unitaries constituting$\delta −approximate-approximate−approximatet−expandersform-expanders form−expandersform\epsilon −netsfor-nets for−netsfort\simeq \frac {d^{5/2}}{ \epsilon }andandand\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}.Wealsoshowthatforarbitrary. We also show that for arbitrary.Wealsoshowthatforarbitraryt,,,\epsilon −netscanbeusedtoconstruct-nets can be used to construct−netscanbeusedtoconstruct\delta −approximateunitary-approximate unitary−approximateunitaryt−designsfor-designs for−designsfor\delta \simeq \epsilon t,wherethenotionofapproximationisbasedonthediamondnorm.Finally,weprovethatthedegreeofanexactunitary, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary,wherethenotionofapproximationisbasedonthediamondnorm.Finally,weprovethatthedegreeofanexactunitarytdesignnecessarytoobtainandesign necessary to obtain andesignnecessarytoobtainan\epsilon −netmustgrowatleastasfastas-net must grow at least as fast as−netmustgrowatleastasfastas\frac {1}{ \epsilon }(forfixeddimension)andnotslowerthan(for fixed dimension) and not slower than(forfixeddimension)andnotslowerthand^{2}(forfixed(for fixed(forfixed\epsilon ).Thisshowsnearoptimalityofourresultconnecting). This shows near optimality of our result connecting).Thisshowsnearoptimalityofourresultconnectingt−designsand-designs and−designsand\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups SU(2n)\mathsf{SU}(2^n)SU(2n) on nnn qubits. (i) Random Pauli Rotation: choose an nnn-qubit Pauli operator PPP and an angle θ∈[0,2π)θ\in [0,2π)θ∈[0,2π), both uniformly at random, and apply eiθPe^{\mathrm i θP}eiθP. (ii) Brickwork Random Unitary Circuit: choose n−1n-1n−1 unitaries UiU_{i}Ui​ uniformly at random from SU(4)\mathsf{SU}(4)SU(4) (including central phases of the parent group) independently, and apply U2j−1U_{2j-1}U2j−1​ on two qubits 2j−1,2j2j-1, 2j2j−1,2j and then U2jU_{2j}U2j​ on two qubits 2j,2j+12j, 2j+12j,2j+1. Importantly, the gap bounds are independent of nnn and apply for all finite dimensional unitary representations of SU(2n)\mathsf{SU}(2^n)SU(2n) uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary ttt-designs after O(nt)\mathcal{O}(nt)O(nt) steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be O(2cn)\mathcal{O}(2^{cn})O(2cn) for some c<1c < 1c<1. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal ttt-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for t=2t=2t=2.