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:2210.07872

A random matrix model for random approximate ttt-designs

Piotr Dulian, Adam Sawicki

Published Oct 14, 2022• 1 citation
arXivHTMLPDF

Abstract

For a Haar random set $\mathcal{S}\subset U(d)$ of quantum gates we consider the uniform measure $ν_\mathcal{S}$ whose support is given by $\mathcal{S}$. The measure $ν_\mathcal{S}$ can be regarded as a $δ(ν_\mathcal{S},t)$-approximate $t$-design, $t\in\mathbb{Z}_+$. We propose a random matrix model that aims to describe the probability distribution of $δ(ν_\mathcal{S},t)$ for any $t$. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined by $t$. We prove that, the operator norm of this matrix, $δ({t})$, is the random variable to which $\sqrt{|\mathcal{S}|}δ(ν_\mathcal{S},t)$ converges in distribution when the number of elements in $\mathcal{S}$ grows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilities $\mathbb{P}(δ(t)>2+ε)$, for any $ε>0$. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability $1$ there is $t\in\mathbb{Z}_+$ such that $\sup_{k\in\mathbb{Z}_{+}}δ(k)=δ(t)$. Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality of $\mathcal{S}$. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilities $\mathbb{P}(\sqrt{\mathcal{S}}δ(ν_\mathcal{S},t)>2+ε)$ are bounded from above by the tail probabilities $\mathbb{P}(δ(t)>2+ε)$ of our random matrix model. In particular our conjecture implies that a Haar random set $\mathcal{S}\subset U(d)$ satisfies the spectral gap conjecture with the probability $1$.

DOI
10.48550/arxiv.2210.07872

Related papers

A Random Matrix Model for Random Approximate t-Designs

Piotr Dulian, Adam Sawicki

For a Haar random set$\mathcal {S}\subset U(d)$of quantum gates we consider the uniform measure$\nu_{\mathcal {S}}$whose support is given by$\mathcal {S}$. The measure$\nu _{\mathcal {S}}$can be regarded as a$\delta (\nu _{\mathcal {S}},t)$-approximate$t$-design,$t\in \mathbb {Z}_{+}$. We propose a random matrix model that aims to describe the probability distribution of$\delta (\nu _{\mathcal {S}},t)$for any$t$. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined by$t$. We prove that, the operator norm of this matrix,$\delta ({t})$, is the random variable to which$\sqrt {|\mathcal {S}|}\delta (\nu _{\mathcal {S}},t)$converges in distribution when the number of elements in$\mathcal {S}$grows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilities$\mathbb {P}(\delta (t)>2+\epsilon)$, for any$\epsilon >0$. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability 1 there is$t\in \mathbb {Z}_{+}$such that$\sup _{k\in \mathbb {Z}_{+}}\delta (k)=\delta (t)$. Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality of$\mathcal {S}$. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilities$\mathbb {P}(\sqrt {\mathcal {S}}\delta (\nu _{\mathcal {S}},t)>2+\epsilon)$are bounded from above by the tail probabilities$\mathbb {P}(\delta (t)>2+\epsilon)$of our random matrix model. In particular our conjecture implies that a Haar random set$\mathcal {S}\subset U(d)$satisfies the spectral gap conjecture with the probability 1.

IEEE Transactions on Information Theory•Feb 20, 2024•1 citation

Approximate t -Designs in Generic Circuit Architectures

Daniel Belkin, James Allen, Soumik Ghosh +6 more

Unitary t -designs are distributions on the unitary group whose first t moments appear maximally random. Previous work has established several upper bounds on the depths at which certain specific random quantum circuit ensembles approximate t -designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates. This is accomplished by relating the spectral gaps of such architectures to those of one-dimensional brickwork architectures. Our bound depends on the details of the architecture only via the typical number of layers needed for a block of the circuit to form a connected graph over the sites. When this quantity is bounded, the circuit forms an approximate t -design in at most linear depth. We give numerical evidence for a stronger bound that depends only on the number of connected blocks into which the architecture can be divided. We also give an implicit bound for nondeterministic architectures in terms of properties of the corresponding distribution over fixed architectures. Published by the American Physical Society 2024

arXiv:2310.19783•PRX Quantum•Dec 17, 2024•8 citations

Stronger Welch Bounds and Optimal Approximate kkk-Designs

Riccardo Castellano, Dmitry Grinko, Sadra Boreiri +2 more

The question of how well a finite ensemble of quantum states can approximate Haar randomness is relevant in many areas of quantum physics. Here we consider this problem from a geometrical perspective, via the notion of Welch bounds. The latter are a set of inequalities, originally derived in the context of signal processing, which precisely characterize exact k-designs, i.e. a finite ensemble of states that exactly reproduces the k-th moment of the Haar measure. We derive stronger Welch bounds which enable a quantitative and operationally meaningful characterisation of approximate k-designs. Our new bounds are often tight, allowing us to characterize optimal approximate designs in regimes where the cardinality of the ensemble is small. A notable example is complete sets of mutually unbiased bases (MUBs), which form an optimal approximate 3-design among 1-designs of their cardinality. This leads to a new variational approach to determine the existence of complete sets of MUBs, which we explore numerically in dimension six. We highlight a connection to shadow tomography, relating our bounds to the shadow norm. We comment on how the method extends to other types of designs, including toric and unitary designs. A key technical ingredient, is the computation of the complete spectrum of the partially transposed symmetric-subspace projector, including multiplicities and eigenvectors, which may find further applications.

quant-pharXiv:2602.13099•Feb 16, 2026•0 citations

Exact spectral gaps of random one-dimensional quantum circuits

Andrew E. Deneris, Pablo Bermejo, Paolo Braccia +2 more

The spectral gap of local random quantum circuits is a fundamental property that determines how close the moments of the circuit's unitaries match those of a Haar random distribution. When studying spectral gaps, it is common to bound these quantities using tools from statistical mechanics or via quantum information-based inequalities. By focusing on the second moment of one-dimensional unitary circuits where nearest-neighboring gates act on sets of qudits (with open and closed boundary conditions), we show that one can exactly compute the associated spectral gaps. Indeed, having access to their functional form allows us to prove several important results, such as the fact that the spectral gap for closed boundary condition is exactly the square of the gap for open boundaries, as well as improve on previously known bounds for approximate design convergence. Finally, we verify our theoretical results by numerically computing the spectral gap for systems of up to 70 qubits, as well as comparing them to gaps of random orthogonal and symplectic circuits.

arXiv:2408.11201•Physical Review A•Nov 25, 2025•4 citations

Approximate 𝑡-Designs in Generic Circuit Architectures

Daniel Belkin, James Allen, Soumik Ghosh +6 more

Unitary 𝑡-designs are distributions on the unitary group whose first 𝑡 moments appear maximally random. Previous work has established several upper bounds on the depths at which certain specific random quantum circuit ensembles approximate 𝑡-designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates. This is accomplished by relating the spectral gaps of such architectures to those of one-dimensional brickwork architectures. Our bound depends on the details of the architecture only via the typical number of layers needed for a block of the circuit to form a connected graph over the sites. When this quantity is bounded, the circuit forms an approximate 𝑡-design in at most linear depth. We give numerical evidence for a stronger bound that depends only on the number of connected blocks into which the architecture can be divided. We also give an implicit bound for nondeterministic architectures in terms of properties of the corresponding distribution over fixed architectures.

•Dec 17, 2024•0 citations

Matrix concentration inequalities and efficiency of random universal sets of quantum gates

Piotr Dulian, Adam Sawicki

For a random set S⊂U(d) of quantum gates we provide bounds on the probability that S forms a δ -approximate t -design. In particular we have found that for S drawn from an exact t -design the probability that it forms a δ -approximate t -design satisfies the inequality P(δ≥x)≤2Dte−|S|xarctanh(x)(1−x2)|S|/2=O(2Dt(e−x21−x2)|S|) , where Dt is a sum over dimensions of unique irreducible representations appearing in the decomposition of U↦U⊗t⊗U¯⊗t . We use our results to show that to obtain a δ -approximate t -design with probability P one needs O(δ−2(tlog⁡(d)−log⁡(1−P))) many random gates. We also analyze how δ concentrates around its expected value Eδ for random S . Our results are valid for both symmetric and non-symmetric sets of gates.

arXiv:2202.05371•Quantum•Apr 20, 2023•3 citations
For a Haar random set S⊂U(d)\mathcal{S}\subset U(d)S⊂U(d) of quantum gates we consider the uniform measure νSν_\mathcal{S}νS​ whose support is given by S\mathcal{S}S. The measure νSν_\mathcal{S}νS​ can be regarded as a δ(νS,t)δ(ν_\mathcal{S},t)δ(νS​,t)-approximate ttt-design, t∈Z+t\in\mathbb{Z}_+t∈Z+​. We propose a random matrix model that aims to describe the probability distribution of δ(νS,t)δ(ν_\mathcal{S},t)δ(νS​,t) for any ttt. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined by ttt. We prove that, the operator norm of this matrix, δ(t)δ({t})δ(t), is the random variable to which ∣S∣δ(νS,t)\sqrt{|\mathcal{S}|}δ(ν_\mathcal{S},t)∣S∣​δ(νS​,t) converges in distribution when the number of elements in S\mathcal{S}S grows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilities P(δ(t)>2+ε)\mathbb{P}(δ(t)>2+ε)P(δ(t)>2+ε), for any ε>0ε>0ε>0. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability 111 there is t∈Z+t\in\mathbb{Z}_+t∈Z+​ such that sup⁡k∈Z+δ(k)=δ(t)\sup_{k\in\mathbb{Z}_{+}}δ(k)=δ(t)supk∈Z+​​δ(k)=δ(t). Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality of S\mathcal{S}S. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilities P(Sδ(νS,t)>2+ε)\mathbb{P}(\sqrt{\mathcal{S}}δ(ν_\mathcal{S},t)>2+ε)P(S​δ(νS​,t)>2+ε) are bounded from above by the tail probabilities P(δ(t)>2+ε)\mathbb{P}(δ(t)>2+ε)P(δ(t)>2+ε) of our random matrix model. In particular our conjecture implies that a Haar random set S⊂U(d)\mathcal{S}\subset U(d)S⊂U(d) satisfies the spectral gap conjecture with the probability 111.
For a Haar random setS⊂U(d)\mathcal {S}\subset U(d)S⊂U(d)of quantum gates we consider the uniform measureνS\nu_{\mathcal {S}}νS​whose support is given byS\mathcal {S}S. The measureνS\nu _{\mathcal {S}}νS​can be regarded as aδ(νS,t)\delta (\nu _{\mathcal {S}},t)δ(νS​,t)-approximatettt-design,t∈Z+t\in \mathbb {Z}_{+}t∈Z+​. We propose a random matrix model that aims to describe the probability distribution ofδ(νS,t)\delta (\nu _{\mathcal {S}},t)δ(νS​,t)for anyttt. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined byttt. We prove that, the operator norm of this matrix,δ(t)\delta ({t})δ(t), is the random variable to which∣S∣δ(νS,t)\sqrt {|\mathcal {S}|}\delta (\nu _{\mathcal {S}},t)∣S∣​δ(νS​,t)converges in distribution when the number of elements inS\mathcal {S}Sgrows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilitiesP(δ(t)>2+ϵ)\mathbb {P}(\delta (t)>2+\epsilon)P(δ(t)>2+ϵ), for anyϵ>0\epsilon >0ϵ>0. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability 1 there ist∈Z+t\in \mathbb {Z}_{+}t∈Z+​such thatsup⁡k∈Z+δ(k)=δ(t)\sup _{k\in \mathbb {Z}_{+}}\delta (k)=\delta (t)supk∈Z+​​δ(k)=δ(t). Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality ofS\mathcal {S}S. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilitiesP(Sδ(νS,t)>2+ϵ)\mathbb {P}(\sqrt {\mathcal {S}}\delta (\nu _{\mathcal {S}},t)>2+\epsilon)P(S​δ(νS​,t)>2+ϵ)are bounded from above by the tail probabilitiesP(δ(t)>2+ϵ)\mathbb {P}(\delta (t)>2+\epsilon)P(δ(t)>2+ϵ)of our random matrix model. In particular our conjecture implies that a Haar random setS⊂U(d)\mathcal {S}\subset U(d)S⊂U(d)satisfies the spectral gap conjecture with the probability 1.
Unitary t -designs are distributions on the unitary group whose first t moments appear maximally random. Previous work has established several upper bounds on the depths at which certain specific random quantum circuit ensembles approximate t -designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates. This is accomplished by relating the spectral gaps of such architectures to those of one-dimensional brickwork architectures. Our bound depends on the details of the architecture only via the typical number of layers needed for a block of the circuit to form a connected graph over the sites. When this quantity is bounded, the circuit forms an approximate t -design in at most linear depth. We give numerical evidence for a stronger bound that depends only on the number of connected blocks into which the architecture can be divided. We also give an implicit bound for nondeterministic architectures in terms of properties of the corresponding distribution over fixed architectures. Published by the American Physical Society 2024
The question of how well a finite ensemble of quantum states can approximate Haar randomness is relevant in many areas of quantum physics. Here we consider this problem from a geometrical perspective, via the notion of Welch bounds. The latter are a set of inequalities, originally derived in the context of signal processing, which precisely characterize exact k-designs, i.e. a finite ensemble of states that exactly reproduces the k-th moment of the Haar measure. We derive stronger Welch bounds which enable a quantitative and operationally meaningful characterisation of approximate k-designs. Our new bounds are often tight, allowing us to characterize optimal approximate designs in regimes where the cardinality of the ensemble is small. A notable example is complete sets of mutually unbiased bases (MUBs), which form an optimal approximate 3-design among 1-designs of their cardinality. This leads to a new variational approach to determine the existence of complete sets of MUBs, which we explore numerically in dimension six. We highlight a connection to shadow tomography, relating our bounds to the shadow norm. We comment on how the method extends to other types of designs, including toric and unitary designs. A key technical ingredient, is the computation of the complete spectrum of the partially transposed symmetric-subspace projector, including multiplicities and eigenvectors, which may find further applications.
The spectral gap of local random quantum circuits is a fundamental property that determines how close the moments of the circuit's unitaries match those of a Haar random distribution. When studying spectral gaps, it is common to bound these quantities using tools from statistical mechanics or via quantum information-based inequalities. By focusing on the second moment of one-dimensional unitary circuits where nearest-neighboring gates act on sets of qudits (with open and closed boundary conditions), we show that one can exactly compute the associated spectral gaps. Indeed, having access to their functional form allows us to prove several important results, such as the fact that the spectral gap for closed boundary condition is exactly the square of the gap for open boundaries, as well as improve on previously known bounds for approximate design convergence. Finally, we verify our theoretical results by numerically computing the spectral gap for systems of up to 70 qubits, as well as comparing them to gaps of random orthogonal and symplectic circuits.
Unitary 𝑡-designs are distributions on the unitary group whose first 𝑡 moments appear maximally random. Previous work has established several upper bounds on the depths at which certain specific random quantum circuit ensembles approximate 𝑡-designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates. This is accomplished by relating the spectral gaps of such architectures to those of one-dimensional brickwork architectures. Our bound depends on the details of the architecture only via the typical number of layers needed for a block of the circuit to form a connected graph over the sites. When this quantity is bounded, the circuit forms an approximate 𝑡-design in at most linear depth. We give numerical evidence for a stronger bound that depends only on the number of connected blocks into which the architecture can be divided. We also give an implicit bound for nondeterministic architectures in terms of properties of the corresponding distribution over fixed architectures.
For a random set S⊂U(d) of quantum gates we provide bounds on the probability that S forms a δ -approximate t -design. In particular we have found that for S drawn from an exact t -design the probability that it forms a δ -approximate t -design satisfies the inequality P(δ≥x)≤2Dte−|S|xarctanh(x)(1−x2)|S|/2=O(2Dt(e−x21−x2)|S|) , where Dt is a sum over dimensions of unique irreducible representations appearing in the decomposition of U↦U⊗t⊗U¯⊗t . We use our results to show that to obtain a δ -approximate t -design with probability P one needs O(δ−2(tlog⁡(d)−log⁡(1−P))) many random gates. We also analyze how δ concentrates around its expected value Eδ for random S . Our results are valid for both symmetric and non-symmetric sets of gates.