Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915640676188160 |
|---|---|
| author | Fefferman, Bill Ghosh, Soumik Zhan, Wei |
| author_facet | Fefferman, Bill Ghosh, Soumik Zhan, Wei |
| contents | We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least inverse exponential in depth, on any output qubit touched by its lightcone. Our result on scrambling speed works with high probability over the choice of a circuit from an ensemble, as opposed to just working in expectation.
As an application, we give the first polynomial-time algorithm for learning log-depth random quantum circuits with Haar random gates up to polynomially small diamond distance, given oracle access to the circuit. Other applications of this new scrambling speed lower bound include:
$\bullet$ An optimal $Ω(\log \varepsilon^{-1})$ depth lower bound for $\varepsilon$-approximate unitary designs on any circuit architecture;
$\bullet$ A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit.
Our learning and depth-testing algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_19561 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits Fefferman, Bill Ghosh, Soumik Zhan, Wei Quantum Physics Computational Complexity We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least inverse exponential in depth, on any output qubit touched by its lightcone. Our result on scrambling speed works with high probability over the choice of a circuit from an ensemble, as opposed to just working in expectation. As an application, we give the first polynomial-time algorithm for learning log-depth random quantum circuits with Haar random gates up to polynomially small diamond distance, given oracle access to the circuit. Other applications of this new scrambling speed lower bound include: $\bullet$ An optimal $Ω(\log \varepsilon^{-1})$ depth lower bound for $\varepsilon$-approximate unitary designs on any circuit architecture; $\bullet$ A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit. Our learning and depth-testing algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties. |
| title | Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2407.19561 |