A Random Matrix Model for Random Approximate t-Designs
- 20 February 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (4) , 2637-2654
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
Funding Information
- National Science Centre, Poland (OPUS: UMO-2020/37/B/ST2/02478)
- Foundation for Polish Science through the TEAM-NET Project (POIR.04.04.00-00-17C1/18-00)
- Infrastruktura PL-Grid
This publication has 32 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