A random matrix model for random approximate $t$-designs
Authors:
Preprint
Abstract
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$.
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Approximate Unitary t-Designs by Short Random Quantum Circuits Using Nearest-Neighbor and Long-Range GatesCommunications in Mathematical Physics, 2023
- Transitions in entanglement complexity in random quantum circuits by measurementsPhysics Letters A, 2021
- Three Lectures on Complexity and Black Holes2020
- Chaos and complexity by designJournal of High Energy Physics, 2017
- Local Random Quantum Circuits are Approximate Polynomial-DesignsCommunications in Mathematical Physics, 2016
- On number of partitions of an integer into a fixed number of positive integersJournal of Number Theory, 2016
- Efficient Quantum Tensor Product Expanders and k-Designs2009
- Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup ProblemAlgorithmica, 2008
- Tensor Product Representations of General Linear Groups and Their Connections with Brauer AlgebrasJournal of Algebra, 1994
- Hecke operators and distributing points on S2. IICommunications on Pure and Applied Mathematics, 1987