Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

Fefferman, Bill; Ghosh, Soumik; Zhan, Wei

doi:10.4230/LIPIcs.ITCS.2026.57

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

Bill Fefferman

Department of Computer Science, The University of Chicago, IL, USA Soumik Ghosh

Department of Computer Science, The University of Chicago, IL, USA Wei Zhan

Department of Computer Science, Purdue University, West Lafayette, IN, USA

Abstract

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:

$\blacksquare$

An optimal $\Omega(\log\varepsilon^{-1})$ depth lower bound for $\varepsilon$ -approximate unitary designs on any circuit architecture;
$\blacksquare$

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.

Keywords and phrases:

Haar measure, anti-concentration, random quanytum circuit, learning

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum computation theory

Related Version:

Full Version: https://arxiv.org/abs/2407.19561

Acknowledgements:

The authors thank Anurag Anshu, Adam Bouland, Lijie Chen, Jonas Haferkamp, Robert Huang, Issac Kim, Yunchao Liu, Tony Metger, Marcus Michelen, Tommy Schuster and Kewen Wu for helpful comments and discussions, and thank Jacob Watkins for pointing out a mistake in our previous version of Section 5.3.2.

Funding:

B.F., S.G., and W.Z. acknowledge support from AFOSR (FA9550-21-1-0008). This material is based upon work partially supported by the National Science Foundation under Grant CCF-2044923 (CAREER), by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers (Q-NEXT) and by the DOE QuantISED grant DE-SC0020360.

DOI:

10.4230/LIPIcs.ITCS.2026.57

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Random quantum circuits are one of the most popular paradigms of quantum computation in the near-term era. They are well-studied, both theoretically and experimentally, in the context of quantum advantage demonstrations: e.g., see [6, 8, 3, 7, 43, 44, 21]. They also have numerous applications in areas like benchmarking, like in [19, 37], in cryptography, as in e.g., [4, 2, 50], and in the modeling of physical objects like black holes, as in e.g., [30, 49, 52].

One reason random quantum circuits are extensively studied is because they are rapid “scramblers” of information. Intuitively, this means that the output state it generates has non-trivial correlations across spatially separated qubits. The rate of scrambling depends on the depth – the deeper the circuit is, the better it is at scrambling. However, even though previous works on scrambling have put upper bounds on the scrambling speed of random circuits – see, e.g., [28, 11, 46, 27, 33, 13, 14, 23, 42, 36, 16, 51, 17, 53] – lower bounds on the scrambling speed are not well studied.

In this work, we give a lower bound on the speed with which random quantum circuits can scramble information. Our main theorem is as follows:

Theorem 1.

Let $\mathcal{C}$ be a random quantum circuit with a fixed architecture, where each gate is a $k$ -qubit independent Haar random unitary. Let $\rho$ and $\pi$ be a pair of input and output qubits connected by $D$ layer of gates. Arbitrarily fix the inputs to $\mathcal{C}$ , except the qubit $\rho$ , and let $\Phi_{\mathcal{C}}$ be the channel that maps $\rho$ to $\pi$ .

Then for every $\gamma>0$ , with probability at least $1-\gamma$ over $\mathcal{C}$ the following holds: For every two single-qubit states $\rho$ and $\rho^{\prime}$ ,

\mathopen{}\mathclose{{\left\|\Upphi_{\mathcal{C}}(\rho)-\Upphi_{\mathcal{C}}(% \rho^{\prime})}}\right\|_{\mathrm{F}}\geq\mathopen{}\mathclose{{\left\|\rho-% \rho^{\prime}}}\right\|_{\mathrm{F}}\cdot(2^{-D}\gamma)^{c_{k}}

(1)

where $\mathopen{}\mathclose{{\left\|\cdot}}\right\|_{\mathrm{F}}$ denotes the Frobenius norm, and $c_{k}>0$ is a constant that depends only on $k$ .

In particular, our main result gives a lower bound on the influence that changing an input qubit has on a designated output qubit inside the lightcone of that input qubit and shows that it decays at most exponentially fast with depth. We articulate some points that make Theorem 1 useful for our applications:

$\blacksquare$

The bound in Theorem 1 is uniform, in the sense that ratio $(2^{-D}\gamma)^{c_{k}}$ does not depend on how the input qubits are chosen, and is applicable to any circuit architecture. Moreover, the probability quantifier over the circuit $\mathcal{C}$ is stated before the choices of $\rho$ and $\rho^{\prime}$ , which is specifically important for our application on learning random quantum circuits (Theorem 5).
$\blacksquare$

Although we stated the theorem using Frobenius norm, the norm is only over single-qubit states and thus is equivalent to any other matrix norm.
$\blacksquare$

To obtain the strongest bound, we can choose $D$ to be the shortest path from $\rho$ to $\pi$ . When $\pi$ is outside the lightcone of $\rho$ , we think of $D=\infty$ , in which case the statement still holds.
$\blacksquare$

Our bound in Theorem 1 is tight, in the sense that one could prove a matching upper bound

$\mathopen{}\mathclose{{\left\|\Upphi_{\mathcal{C}}(\rho)-\Upphi_{\mathcal{C}}(% \rho^{\prime})}}\right\|_{\mathrm{F}}\leq\mathopen{}\mathclose{{\left\|\rho-% \rho^{\prime}}}\right\|_{\mathrm{F}}\cdot(2^{-D}\gamma)^{c_{k}^{\prime}}$ (2)

for various architectures with a different constant $c_{k}^{\prime}<c_{k}$ , by calculating the moment $\mathop{\mathbf{E}\mbox{}}\limits\mathopen{}\mathclose{{\left[\mathopen{}% \mathclose{{\left\|\Upphi_{\mathcal{C}}(\rho)-\Upphi_{\mathcal{C}}(\rho^{% \prime})}}\right\|_{\mathrm{F}}^{2}}}\right]$ . Such calculation can be done by analyzing the Markov chain of Pauli operators, using the results in [28, 11, 45]. However, the moment method could not yield our lower bound, which we will explain in details below.

Implications on proving typicality statements.

Observe that Theorem 1 is a statement that works with high probability over the choice of circuit from the ensemble $\mathcal{C}$ , as opposed to just in expectation over the ensemble $\mathcal{C}$ . To the best of our knowledge, this is the first typicality result regarding the scrambling behavior of random quantum circuits.

Most of the previous work studying random quantum circuits examines their properties by computing some specific quantities of interest in expectation, such as entanglement entropy, OTOC and collision chance, by relating the quantities with the lower moments (usually the second moment) of the quantum circuit. For non-negative quantities the expectation already provides an upper bound that holds with high-probability (like in (2)) by Markov’s inequality. But for proving a strong typicality result as in (1), one also needs a corresponding lower bound, which is commonly proved by calculating the variance of the desired quantity $X$ . In particular, we would want that for some appropriately small $\epsilon$ , and for some $t\geq 1$ ,

\mathop{\mathbf{E}\mbox{}}\limits[X^{2t}]\leq(1+\epsilon)\mathop{\mathbf{E}% \mbox{}}\limits[X^{t}]^{2}.

(3)

However, for most architectures a relation like (3) is largely unknown. One reason is that when $X$ is already a second moment of the quantum circuit, and proving (3) requires computing the fourth or higher moments, which is extremely difficult even for standard brickwork circuits [9]. More importantly, in our case, $X$ can be heuristically approximated by the product $\lambda_{1}\cdots\lambda_{D}$ of i.i.d random variables $\lambda_{1},\ldots,\lambda_{D}$ that follow some distribution $\Lambda$ with constant variance; because of this, we cannot expect (3) to hold as $\mathop{\mathbf{E}\mbox{}}\limits[X^{2t}]$ will be exponentially larger than $\mathop{\mathbf{E}\mbox{}}\limits[X^{t}]^{2}$ .

In this work, we overcome this barrier by performing a more fine-grained analysis. We do not analyze the randomness present in the choice of gates all at once; Instead, we break up the randomness of the circuit into $D$ layers and lower bound the random variable $X$ with a product of $D$ random variables that are highly correlated. We then decouple these random variables using a new anti-concentration inequality on the unitary Haar measure, which will be stated in Theorem 6. This allows us to avoid calculating higher moments of the circuit, and still retrieve information about the distribution of $X$ that could be lost in the moments. Our result in Theorem 1 directly implies typicality guarantees on other quantities, such as the purity of a single output qubit, and we believe the method we use can be generalized to prove typicality results for many other useful quantities.

1.1 Applications

Intuitively, Theorem 1 means that the output state of random quantum circuits with logarithmic depth carries a signal pertaining to its input state that can be extracted from the output state using single qubit quantum state tomography. This allows us to show many applications.

1.1.1 Optimal 2-design lower bounds

First, as an immediate corollary of Theorem 1, we show a depth lower bound for random quantum circuits, defined on any architecture, forming approximate unitary designs; see Section 5.1.

Theorem 2.

Let $\mathcal{C}$ be a random quantum circuit, defined on an arbitrary fixed architecture of minimum depth $D$ , where each gate is a $k$ -qubit independent Haar random unitary. If $\mathcal{C}$ is an $\varepsilon$ -approximate $2$ -design, then

D=\Omega_{k}(\log\varepsilon^{-1}).

Here the minimum depth means the smallest number of gates that any path from input to output goes through, resulting in a stronger requirement than the previous depth lower bounds that uses the lightcone size property. Theorem 2 shows that previous works on approximate $t$ -design constructions, e.g. [28, 32, 24, 15, 50], are optimal in $\epsilon$ , assuming the gates are Haar random unitaries. And combined with the $\Omega(\log n)$ depth lower bound in [18, 50], it means that the approximate $t$ -design construction of depth $O(\log(n/\varepsilon)\cdot t\mathop{\mathrm{polylog}}t)$ from [50] is optimal in both $n$ and $\varepsilon$ .

1.1.2 Testing for depth

Our second application concerns testing the depth of a random circuit when the depth is promised to be at most logarithmic.

Theorem 3.

Let $\mathcal{C}$ be a brickwork random quantum circuit on $n$ qubits of an unknown depth $D$ promised to be bounded as $D=O(\log n)$ , where each gate is independently Haar random. Given oracle access to $\mathcal{C}$ , there is a polynomial time algorithm that outputs $D$ with probability $1-1/\mathrm{poly}(n)$ .

Although Theorem 3 is stated with brickwork circuits for simplicity, it is applicable to many other architectures satisfying the following: For a random circuit of depth $D$ , the lightcone size is strictly smaller than that of a random circuit of depth larger than $D$ . Hence, there will be a particular output qubit which will be insensitive to a change in a particular input qubit in the former case and will be sensitive in the latter case. For $D=O(\log n)$ this difference is inverse polynomially large and can be tested by state tomography. The explicit algorithm is given in Section 5.2.

Note that our algorithm outputs the exact depth instead of obtaining an approximation, in contrast with the recently proposed depth test algorithm in [26]. This is partially due to the fact that our algorithm works with high probability with respect to the choice of a circuit from the ensemble, as opposed to working only in expectation, unlike [26].

1.1.3 Learning brickwork random circuits

Third, we show that Theorem 1 allows us to learn brickwork random circuits of logarithmic depth. We start by showing that the first layer of gates can be learned given oracle access to the circuit.

Theorem 4.

Let $\mathcal{C}$ be a brickwork random quantum circuit on $n$ qubits of known depth $D=O(\log n)$ , where each gate is independently Haar random. Given oracle access to $\mathcal{C}$ , there is a polynomial time algorithm that with high probability outputs each gate in the first layer with polynomially small error.

Furthermore, in real life scenarios we can assume the distribution over the gates is a discrete approximation of the Haar measure (see Definition 28), and in this case we can actually learn the entire circuit:

Theorem 5.

Let $\mathcal{C}$ be a brickwork random quantum circuit on $n$ qubits of known depth $D=O(\log n)$ , where each gate is independently drawn from a discretized version of the Haar measure. Given oracle access to $\mathcal{C}$ , there is a polynomial time algorithm that with high probability outputs $\mathcal{C}$ with polynomially small error.

We will prove Theorem 4 and Theorem 5 in Section 5.3. Note that the learning algorithm in Theorem 5 is proper, that the learnt circuit has the exact same depth and architecture as the actual circuit $\mathcal{C}$ .

Before this work, the state-of-art learning algorithm for brickwork quantum circuits is due to [31, 35], which runs in polynomial time for circuits of $k$ -dimensional geometry up to $O(\log^{1/(k+1)}n)$ depth, and is not proper (that the outputted circuit has depth larger than the input circuit by at least a constant factor). Our algorithm works for all geometric dimensions, works up to $O(\log n)$ depth, and still has polynomial runtime. There is evidence that the depth dependence of our learning algorithm is optimal, because random circuits form high enough designs beyond $\log n$ depth [50], and possibly also pseudorandom unitaries, which hints at learning hardness.

Here we provide an informal description of the learner:

$\blacksquare$

For each gate in the first layer, the learner iteratively searches through the gate set for the correct gate. There’s only polynomially many gates in the gate set because we chose an appropriate $\varepsilon$ -net over $2$ -qubit Haar random unitaries. During each round, the learner applies the inverse of a gate chosen from the gate set at the particular location it wishes to learn.
$\blacksquare$

Select an input qubit to the gate we are trying to learn. The key observation is that, depending on whether we applied the correct inverse, the output lightcone will consist of different qubits. In particular, one qubit will lie outside the lightcone and be unaffected by a change in the selected input qubit if we hit the correct inverse, as opposed to if we didn’t. As a corollary of Theorem 1, in the former case, we can detect the influence of the input qubit by performing single qubit state tomography.

Figure 1: An illustration of the learning algorithm in Theorem 5, where we try to uncompute the gate $G$ by applying some two-qubit unitary $G^{\prime}$ before it. Left: When $G^{\prime}$ failed to uncompute $G$ , the lightcone of the input qubit $\rho$ touches an output qubit $\pi$ at distance $D$ . Right: When $G^{\prime}=G^{\dagger}$ , the output qubit $\pi$ falls out of the lightcone and will not be affected by the change in $\rho$ .

Note that the learner of [31, 35] uses a very different strategy: it looks at each output qubit, and then employs a brute force search over all possible lightcones of that circuit to find the correct one. Thereafter, it stitches together all the different local lightcones of every qubit, and then corrects for the errors in the overlapping regions of the different lightcones. The fact that we do not do a brute force search over all possible lightcones makes our algorithm efficient for any dimension, and not just $1$ -dimensional brickwork circuits.

1.2 Main Technical Tool: Anti-Concentration for Haar Measure

The intuition behind the proof of Theorem 1 is the following: We consider the path of $D+1$ qubits $\rho=\rho_{0},\rho_{1},\ldots,\rho_{D}=\Upphi_{\mathcal{C}}(\rho)$ in the circuit $\mathcal{C}$ , where gate $G_{i}$ has $\rho_{i}$ as an input and $\rho_{i+1}$ as an output. Let $\rho_{i}^{\prime}$ be the corresponding qubits when the input is $\rho^{\prime}$ , and we want to bound the ratios $\lambda_{i}=\mathopen{}\mathclose{{\left\|\rho_{i}-\rho^{\prime}_{i}}}\right\|% _{\mathrm{F}}/\mathopen{}\mathclose{{\left\|\rho_{i-1}-\rho^{\prime}_{i-1}}}% \right\|_{\mathrm{F}}$ and hence their product.

It turns out that we can prove the lower bound $\lambda_{i}\geq|F(G_{i})|$ , where $F$ is a polynomial function over the entries of $G_{i}$ in its matrix representation. Therefore, we only need to show that $|F(G_{i})|$ is often not too small, when $G_{i}$ is a Haar random unitary. In other words, we need to show that the polynomial does not concentrate around zero. Our main technical contribution is the following theorem which proves this anti-concentration phenomenon:

Theorem 6.

Let $U$ be a Haar random $n\times n$ unitary matrix, and let $F:\mathbb{C}^{2n^{2}}\to\mathbb{C}$ be a degree- $d$ polynomial on the entries of $U$ and $U^{\dagger}$ . Then for every $\varepsilon>0$ , it holds that

\Pr\mathopen{}\mathclose{{\left[\big|F(U,U^{\dagger})\big|^{2}\leq\varepsilon% \mathop{\mathbf{E}\mbox{}}\limits\!\big[|F(U,U^{\dagger})|^{2}\big]}}\right]% \leq C^{\prime}(n,d)\cdot\varepsilon^{C(n,d)}

where $C(n,d)>0$ and $C^{\prime}(n,d)>0$ are constants that depend only on $n$ and $d$ .

The anti-concentration inequality of polynomials over Gaussian random variables was famously proved by Carbery and Wright [12], and their result actually applies to any log-concave distribution over $\mathbb{R}^{n}$ . However, as the Haar measure does not even have a convex support, the proof techniques in [12] does not apply. The alternative inductive proof in [38] also fails to apply, as we are dealing with correlated input variables. We present a very different inductive proof in Section 3.

Note that if we consider $F(U,U^{\dagger})$ as a complex random variable, and define the complex variance

\mathrm{\bf Var}[F]=\mathop{\mathbf{E}\mbox{}}\limits[|F|^{2}]-\mathopen{}% \mathclose{{\left|\mathop{\mathbf{E}\mbox{}}\limits[F]}}\right|^{2}=\min_{z\in% \mathbb{C}}\mathop{\mathbf{E}\mbox{}}\limits[|F-z|^{2}],

then we obtain the form closer to the classical anti-concentration inequalities:

Corollary 7.

Let $U$ be a Haar random $n\times n$ unitary matrix, and let $F$ be a degree- $d$ polynomial on the entries of $U$ and $U^{\dagger}$ . Then for every $\varepsilon>0$ and every $z\in\mathbb{C}$ , it holds that

\Pr\mathopen{}\mathclose{{\left[|F-z|^{2}\leq\varepsilon\mathrm{\bf Var}[F]}}% \right]\leq C^{\prime}(n,d)\cdot\varepsilon^{C(n,d)}.

However in this work we will not use the form in Corollary 7, as Theorem 6 suffices for our applications.

$\blacktriangleright$ Remark 8.

Unlike the Carbery-Wright inequality which is dimension-free, meaning the right hand side is $C^{\prime}(d)\cdot\varepsilon^{C(d)}$ and does not depend on $n$ , we have $C(n,d)=(4n^{2}d)^{-1}$ and $C^{\prime}(n,d)=O(n^{3}d)$ in our proof. In fact, using the concentration bounds it is not hard to show that $C^{\prime}(n,d)$ must depends polynomially on $n$ . However, we conjecture that $C(n,d)$ could be independent of $n$ , in which case the result would be applicable to random quantum circuits with gates of higher locality.

1.3 Related Works

Concentration phenomenon on unitary Haar measures has been extensively studied, and the readers can refer to [39] for a comprehensive review of the results. In comparison, much less has been shown for the reverse direction, namely the anti-concentration inequalities.

One common way to prove such inequalities is by calculating higher moments and apply the Paley-Zygmund inequality, which was indeed used for showing the anti-concentration property of output distributions of Haar random unitaries and random quantum circuits [1, 25, 18]. However, the inequality proved this way is not strong enough for our applications, while calculating moments of a random quantum circuit is also non-trivial and depends highly on the architecture [22, 9]. Instead, we resort to prove a general anti-concentration inequality for polynomials, whose theory has been well developed for Gaussian distributions [12] and product distributions (namely the Littlewood-Offord theory) and has found numerous applications in computational complexity theory [41, 40, 34]. Our inductive proof of Theorem 6 also shares a similar spirit with the elementary proof of Carbery-Wright inequality in [38].

Multiple notions of scrambling property of random quantum circuits has been previously studied. In particular, [11] showed that in a random circuit consists of $O(n\log^{2}n)$ sequential applications of Haar random gates on a complete graph of $n$ qubits, every subset of $c n$ qubits is polynomially close to maximally mixed with high probability for some constant $c>0$ . Our Theorem 1 can be viewed as a result in the reverse direction which bounds the scrambling speed of such random circuits. Specifically, at least $\Omega(n\log n\log\log n)$ sequential gates are required, as otherwise with high probability a pair of input and output qubits are $o(\log n)$ depth apart due to a generalization of the coupon-collector problem [48]. It is also reasonable to believe that our method of proving Theorem 1, via the anti-concentration inequality, is applicable to obtain lower bounds for other measures of scrambling such as entanglement and out-of-time-ordered correlation (OTOC) [45, 46, 5, 27]. Upper bounds in the above-mentioned works are obtained by calculating moments and analyzing the averaged Markov chain on Pauli operators, which are not sufficient to prove lower bounds in the typical case.

We also review some previous works related to our applications and clarify the connections. For approximate unitary designs, many previous constructions, for example [28, 10, 24, 29, 15], employed Haar random unitary gates and achieved the optimal $O(\log\varepsilon^{-1})$ dependence on $\varepsilon$ . The construction of depth $O(\log(n/\varepsilon)\cdot t\mathop{\mathrm{polylog}}t)$ in the recent work of [50] also falls into this category. Meanwhile, they also proposed a construction of approximate 3-design with only $O(\log\log(n/\varepsilon))$ depth. This does not contradict our lower bound Theorem 2 as the construction uses random Clifford unitaries, which are not independent between layers and also fail the anti-concentration property in Theorem 6. It is intriguing, however, to see if our argument can be extended to show a matching $\Omega(\log\log\varepsilon^{-1})$ depth lower bound.

The depth test algorithm in [26] is based on the entanglement dynamics of random circuits and implemented with their Bell sampling framework. For brickwork circuits, as there is a constant gap between the upper and lower bounds for the entanglement entropy in the typical case, their algorithm gives constant approximation of the depth. For general architectures, the algorithm in [26] also requires knowledge of the entanglement velocity, while our algorithm for Theorem 3 only relies on a specific property of the architecture that the lightcone strictly expands with depth.

The learning algorithm for shallow quantum circuits in [31] is based on the idea of brute-force enumerating all possibilities in a light cone, and stitching the parts together. Therefore, their algorithm works any quantum circuit in worse case, and has complexity exponential in the lightcone size. This means that in order to have polynomial efficiency, the depth has to be $O(\log^{1/k}n)$ for $k$ -dimensional geometrically local circuits and $O(\log\log n)$ for general architectures. However, the learning algorithm is improper and the outputted circuit has a large polynomial blow-up in depth. The blow-up factor could be reduced to constant, at the cost of lowering the depth bound to $O(\log^{1/{(k+1)}}n)$ , and thus could not perform in polynomial time for log-depth circuits even for 1-dimensional geometry. In comparison, our algorithm works for random quantum circuits, on the fixed brickwork or similar geometrically local architecture, where neighboring qubits can be distinguished by their lightcones. The strength of our algorithm Theorem 5 is that it works up to logarithmic depth in polynomial time regardless of the geometric dimension, and it learns properly in that it outputs a circuit with the exact same architecture. This makes our result incomparable with [31].

We also mention that, there is a different learning task where instead given oracle access to the circuit $\mathcal{C}$ , the learner is only given copies of the state $\mathcal{C}|0^{n}\rangle$ , and needs to learn a circuit that prepares the same state with error in trace distance. Our algorithm relies on having different inputs and hence does not work in this case, whereas [31] gave a quasi-polynomial efficiency algorithm for 2D and the algorithm was extended to higher dimensions in [35].

2 Preliminaries

We start with some basic notations. We use $\mathbb{U}(d)$ to denote the unitary group of dimension $d$ , and use $\mathcal{U}(d)$ to denote the Haar measure over $\mathbb{U}(d)$ . We use Greek letters such as $\rho,\pi,\tau$ to denote density matrices of quantum states. We use $\mathopen{}\mathclose{{\left\|\cdot}}\right\|_{1}$ and $\mathopen{}\mathclose{{\left\|\cdot}}\right\|_{\mathrm{F}}$ for trace norm and Frobenius norm, and $d_{\diamond}(\cdot,\cdot)$ for diamond distance between unitary channels, defined as

d_{\diamond}(\Phi_{1},\Phi_{2})=\max_{\rho}\mathopen{}\mathclose{{\left\|(\Phi% _{1}\otimes\mathbb{I})\rho-(\Phi_{2}\otimes\mathbb{I})\rho}}\right\|_{1},

with maximum taken over all density matrices $\rho$ .

A circuit architecture determines the positions of gates in the circuit. We define the depth of an architecture as follows.

Definition 9.

In a circuit architecture, a path in space-time between two qubits $\rho$ and $\rho^{\prime}$ is a sequence of qubits $\rho=\rho_{0},\rho_{1},\ldots,\rho_{D}=\rho^{\prime}$ where for each $i$ , there is a gate in the circuit that has $\rho_{i}$ as an input and $\rho_{i+1}$ as an output.

We say the architecture has minimum depth $D$ , if there exists a pair of input and output qubits connected by a path of length $D$ , and every other path from input to output has depth at least $D$ .

A specific architecture of interest is the (1-dimensional) brickwork architecture:

Definition 10.

A brickwork quantum circuit on $n$ qubits of depth $D$ consists of $D$ layers of gates, where on layer $j$ , there is a two-qubit gate $G_{i,j}=G_{i+1,j}$ acting on the $i$ -th and $(i+1)$ -th qubit if and only if $i$ and $j$ have the same parity.

The brickwork architecture could be generalized to higher dimensional geometry, and our results still hold for any constant dimension. However, for simplicity we stick with the 1-dimensional architecture in this paper.

We will need the following statements about quantum state tomography on single qubits for our algorithms (see e.g. [47])

Proposition 11.

Given access to copies of a single-qubit state $\rho$ , one can output an estimation $\tilde{\rho}$ with $\mathopen{}\mathclose{{\left\|\rho-\tilde{\rho}}}\right\|_{\mathrm{F}}\leq\varepsilon$ in $\mathrm{poly}(1/\varepsilon)$ time.

The following simple lemma is particularly useful, which bounds the difference between states through a channel:

Lemma 12.

Let $\Upphi$ be a quantum channel that takes $k$ qubits as the input. For every input states $\rho$ and $\rho^{\prime}$ , we have

\mathopen{}\mathclose{{\left\|\Upphi(\rho)-\Upphi(\rho^{\prime})}}\right\|_{% \mathrm{F}}\leq 2^{k/2}\mathopen{}\mathclose{{\left\|\rho-\rho^{\prime}}}% \right\|_{\mathrm{F}}.

As we are frequently dealing with differences between quantum states, here we present some facts about the space of such differences. We start from the Bloch sphere presentation of a single-qubit state:

\rho=\frac{1}{2}(I+r_{x}X+r_{y}Y+r_{z}Z),\qquad r_{x},r_{y},r_{z}\in\mathbb{R}% ,\quad r_{x}^{2}+r_{y}^{2}+r_{z}^{2}\leq 1

(4)

where

I=\begin{bmatrix}1&0\\ 0&1\end{bmatrix},X=\begin{bmatrix}0&1\\ 1&0\end{bmatrix},Y=\begin{bmatrix}0&-i\\ i&0\end{bmatrix},Z=\begin{bmatrix}1&0\\ 0&-1\end{bmatrix}.

(5)

Then the difference $\rho-\rho^{\prime}$ between two single-qubit states can be written in the Pauli basis

\rho-\rho^{\prime}=r_{x}X+r_{y}Y+r_{z}Z,\quad r_{x}^{2}+r_{y}^{2}+r_{z}^{2}=% \frac{1}{2}\mathopen{}\mathclose{{\left\|\rho-\rho^{\prime}}}\right\|_{\mathrm% {F}}^{2}\leq 1.

(6)

Therefore, if we view $\rho-\rho^{\prime}$ under the coordinate system $\sqrt{2}\cdot(r_{x},r_{y},r_{z})$ , then the set $\Updelta_{1}$ of all possible single-qubit differences can be identified with a ball of radius $\sqrt{2}$ in $\mathbb{R}^{3}$ . The Euclidean space $\mathbb{R}^{3}$ is equipped with the standard trace inner product $\langle A,B\rangle=\mathrm{Tr}[A^{\dagger}B]$ , so that the norm coincides with the Frobenius norm.

More generally, let $\Updelta_{k}$ be the set of all possible differences between two $k$ -qubit states $\rho$ and $\rho^{\prime}$ . The difference $\rho-\rho^{\prime}$ can be written as a real linear combination over the Pauli basis

\{I,X,Y,Z\}^{\otimes k}\setminus\{I^{\otimes k}\}

where the identity is removed as $\mathrm{Tr}[\rho-\rho^{\prime}]=0$ . Since the Pauli basis are orthonormal, we can think of $\Updelta_{k}$ as a subset of the Euclidean space $\mathbb{R}^{4^{k}-1}$ (although the set is much more complicated than a ball for $k>1$ ). The Euclidean space is also equipped with the standard trace inner product and the Frobenius norm. As a result, a quantum channel $\Upphi$ with $k$ -qubit input and $n$ -qubit output induces a linear map from $\Updelta_{k}$ to $\Updelta_{n}$ :

\rho-\rho^{\prime}\mapsto\Upphi(\rho)-\Upphi(\rho^{\prime}),

which is also a real linear map from $\mathbb{R}^{4^{k}-1}$ to $\mathbb{R}^{4^{n}-1}$ .

3 Anti-concentration Bound

In this section we prove Theorem 6. For simplicity, we introduce the notion of semi-polynomials: A function is a degree- $d$ semi-polynomial in complex variables $z_{1},\ldots,z_{n}$ , if it is a polynomial in $z_{1},\ldots,z_{n},\overline{z_{1}},\ldots,\overline{z_{n}}$ of degree at most $d$ . Now Theorem 6 is implied by the following more general form:

Theorem 13.

Let $m\leq n$ , and $F:\mathbb{C}^{nm}\to\mathbb{C}$ be a degree- $d$ semi-polynomial. Suppose that $F$ takes as inputs the entries of the first $m$ columns of an $n\times n$ unitary matrix, and that the value of $F$ is always a non-negative real number over this domain. Then for $U\sim\mathcal{U}(n)$ ,

\Pr\mathopen{}\mathclose{{\left[F(U_{1,1},\ldots,U_{n,m})\leq\varepsilon% \mathop{\mathbf{E}\mbox{}}\limits\mathopen{}\mathclose{{\left[F}}\right]}}% \right]\leq C^{\prime}(n,m,d)\cdot\varepsilon^{C(n,m,d)}

holds for every $\varepsilon>0$ , where $C(n,m,d)>0$ and $C^{\prime}(n,m,d)>0$ are constants that depend only on $n, m$ and $d$ .

To see that Theorem 13 implies Theorem 6, it suffices to take $m=n$ and notice that $|F|^{2}=F\overline{F}$ is a degree- $2d$ semi-polynomial that is always non-negative. We prove Theorem 13 via induction, and the proof is divided into four stages.

3.1 $m=1,n=1$

We start with the simplest case when $m=n=1$ . In this case $F:\mathbb{C}\to\mathbb{C}$ is a single-variable degree- $d$ semi-polynomial over the unit circle $\{z:|z|=1\}$ . Since $\overline{z}=1/z$ over this domain, assuming $F\neq 0$ we can write $F$ as

F(z)=G(z)/z^{d}

where $G(z)=\alpha(z-z_{1})\cdots(z-z_{2d})$ is a degree $2d$ polynomial in $z$ . Without loss of generality we can assume that $|\alpha|=1$ , and therefore

F(z)=|F(z)|=|G(z)|=|z-z_{1}|\cdots|z-z_{2d}|.

(7)

Then we can bound the expectation of $F$ as

\mathop{\mathbf{E}\mbox{}}\limits[F]\leq\sup_{|z|=1}\prod|z-z_{i}|\leq\prod(1+% |z_{i}|).

(8)

On the other hand, if $|z-z_{i}|>\delta\geq 0$ for some $|z|\leq 1$ , it is easy to show that

\frac{|z-z_{i}|}{1+|z_{i}|}>\frac{\delta}{\delta+2}.

(9)

Thus if $|z-z_{i}|>\delta$ holds for all $i=1,\ldots,2d$ , then

F(z)=\prod|z-z_{i}|>\mathopen{}\mathclose{{\left(\frac{\delta}{\delta+2}}}% \right)^{2d}\prod(1+|z_{i}|)\geq\mathopen{}\mathclose{{\left(\frac{\delta}{% \delta+2}}}\right)^{2d}\mathop{\mathbf{E}\mbox{}}\limits[F].

(10)

That means, if we take $\varepsilon=\mathopen{}\mathclose{{\left(\frac{\delta}{\delta+2}}}\right)^{2d}$ , then $F(z)\leq\varepsilon\mathop{\mathbf{E}\mbox{}}\limits[F]$ only happens when $z$ falls into one of the $\delta$ -balls around some $z_{i}$ . Each $\delta$ -ball intersect with the unit circle as an arc of angle at most $4\delta$ , and thus has measure at most $2\delta/\pi$ under the Haar measure over the unit circle. Therefore we conclude that

	$\displaystyle\Pr_{\|z\|=1}\mathopen{}\mathclose{{\left[F(z)\leq\varepsilon% \mathop{\mathbf{E}\mbox{}}\limits[F]}}\right]$	$\displaystyle\leq\min\{4d\delta/\pi,1\}$
		$\displaystyle=\min\mathopen{}\mathclose{{\left\{\frac{8d}{\pi}\cdot\frac{% \varepsilon^{1/(2d)}}{1-\varepsilon^{1/(2d)}},1}}\right\}\leq\mathopen{}% \mathclose{{\left(\frac{8d}{\pi}+1}}\right)\varepsilon^{1/(2d)},$		(11)

and we can take $C(1,1,d)=1/(2d)$ and $C^{\prime}(1,1,d)=8d/\pi+1$ .

3.2 $m=1,n=1$ , Alternative Distribution

For the sake of later use, we also need a version where $z=u_{1}$ follows the distribution of the first coordinate of a Haar-random unit vector $(u_{1},\ldots,u_{n})\in\mathbb{C}^{n}$ , $n\geq 2$ . In this case $\overline{z}=1/z$ no longer holds, and we need an alternative method.

For every $r\in\mathbb{R}$ , $0\leq r\leq 1$ we define

P(r)=\mathop{\mathbf{E}\mbox{}}\limits_{|u_{1}|=r}[F(u_{1})]

where the expectation is over a Haar-random $z\in\mathbb{C}$ with $|z|=r$ . Notice that a monomial $u_{1}^{k}\overline{u_{1}}^{\ell}$ in $F$ has expectation $0$ unless $k=\ell$ , and when $k=\ell$ we have $u_{1}^{k}\overline{u_{1}}^{\ell}=r^{2k}$ . That means $P(r)$ is a degree- $d$ polynomial in $r^{2}$ .

Notice that $r^{2}$ follows the Beta distribution $\mathrm{Beta}(1,n-1)$ , with the density function

f(r;1,n-1)=(n-1)(1-r)^{n-2},

and $\mathop{\mathbf{E}\mbox{}}\limits[P(r)]$ under this distribution coincides with $\mathop{\mathbf{E}\mbox{}}\limits[F]$ .

With the analysis in the previous section which also works on $P(r)$ , we can show that if we take $\varepsilon=\mathopen{}\mathclose{{\left(\frac{\delta}{\delta+2}}}\right)^{d}$ , then $P(r)\leq\varepsilon\mathop{\mathbf{E}\mbox{}}\limits[P(r)]=\varepsilon\mathop{% \mathbf{E}\mbox{}}\limits[F]$ only happens when $r^{2}$ falls into one of the $\delta$ -balls around $d$ complex roots of $P$ , which are intervals of length at most $2\delta$ on the real line. Since the density function of $r^{2}$ has a maximum of $n-1$ , we have

\Pr[P(r)\leq\varepsilon\mathop{\mathbf{E}\mbox{}}\limits[F]]\leq\min\{2d(n-1)% \delta,1\}\leq 4dn\varepsilon^{1/d}.

(12)

On the other hand, applying Equation 11 from the previous section on $F(rz)$ for every fixed $r$ directly provides

\Pr_{|z|=r}[F(z)\leq\varepsilon P(r)]\leq\mathopen{}\mathclose{{\left(\frac{8d% }{\pi}+1}}\right)\varepsilon^{1/(2d)}.

(13)

Thus by a union bound we have

$\displaystyle\Pr[F(u_{1})\leq\varepsilon\mathop{\mathbf{E}\mbox{}}\limits[F]]$	$\displaystyle\leq\Pr\mathopen{}\mathclose{{\left[P(r)\leq\sqrt{\varepsilon}% \mathop{\mathbf{E}\mbox{}}\limits[F]}}\right]+\Pr\mathopen{}\mathclose{{\left[% F(z)\leq\sqrt{\varepsilon}P(\|z\|)}}\right]$
	$\displaystyle\leq 4dn\varepsilon^{1/(2d)}+\mathopen{}\mathclose{{\left(\frac{8% d}{\pi}+1}}\right)\varepsilon^{1/(4d)}$
	$\displaystyle\leq 4d(n+1)\varepsilon^{1/(4d)}.$	(14)

We note that not only this result will be used in the next stage, the technique itself will also be reapplied multiple times in the later proofs.

3.3 $m=1,n>1$

In this stage we consider $m=1$ with general $n$ , and thus the inputs to $F$ is a Haar-random unit vector $(u_{1},\ldots,u_{n})\in\mathbb{C}^{n}$ . The strategy is to use induction on $n$ , and show that with high probability over the choice of $u_{1}$ ,

P(u_{1})=\mathop{\mathbf{E}\mbox{}}\limits_{u_{2},\ldots,u_{n}}[F(u_{1},\ldots% ,u_{n})]

is not too small conditioned on the fixed $u_{1}$ . To handle this, we need the following lemma.

Lemma 14.

If $F:\mathbb{C}^{n}\to\mathbb{C}$ is a degree- $d$ semi-polynomial, and $(u_{1},\ldots,u_{n})\in\mathbb{C}^{n}$ is a Haar-random unit vector, then $P(u_{1})=\mathop{\mathbf{E}\mbox{}}\limits\nolimits_{u_{2},\ldots,u_{n}}[F(u_{% 1},\ldots,u_{n})]$ is a degree- $d$ semi-polynomial on $u_{1}$ .

Proof.

Omitted in this version. $\hfill\blacktriangleleft$

Since $P$ is an expectation over $F$ , it is also always non-negative and has the same expectation as $\mathop{\mathbf{E}\mbox{}}\limits[F]$ . Thus Equation 14 from the previous section gives

\Pr\mathopen{}\mathclose{{\left[P(u_{1})\leq\varepsilon\mathop{\mathbf{E}\mbox% {}}\limits[F]}}\right]\leq 4d(n+1)\varepsilon^{1/(4d)}.

(15)

Now we fix some $u_{1}$ , and consider the degree- $d$ semi-polynomial

F_{u_{1}}(u_{2},\ldots,u_{n})=F(u_{1},u_{2},\ldots,u_{n})

which is always non-negative. Since $(u_{2},\ldots,u_{n})=ru^{\prime}$ for some $r\in\mathbb{R}$ , and $u^{\prime}$ follows the Haar measure over the unit sphere in $\mathbb{C}^{n-1}$ , we can apply the induction hypothesis for $n-1$ on $F_{u_{1}}(ru^{\prime})$ to get

\Pr\mathopen{}\mathclose{{\left[F_{u_{1}}(ru^{\prime})\leq\varepsilon\mathop{% \mathbf{E}\mbox{}}\limits\nolimits_{u^{\prime}}[F_{u_{1}}(ru^{\prime})]}}% \right]\leq C^{\prime}(n-1,1,d)\cdot\varepsilon^{C(n-1,1,d)}.

(16)

Therefore we conclude that, for every $p\in(0,1)$ ,

	$\displaystyle\Pr\mathopen{}\mathclose{{\left[F(u_{1},\ldots,u_{n})\leq% \varepsilon\mathop{\mathbf{E}\mbox{}}\limits[F]}}\right]$
$\displaystyle\leq\$	$\displaystyle\Pr\mathopen{}\mathclose{{\left[P(u_{1})\leq\varepsilon^{p}% \mathop{\mathbf{E}\mbox{}}\limits[F]}}\right]+\Pr\mathopen{}\mathclose{{\left[% F(u_{1},\ldots,u_{n})\leq\varepsilon^{1-p}P(u_{1})}}\right]$
$\displaystyle=\$	$\displaystyle\Pr\mathopen{}\mathclose{{\left[P(u_{1})\leq\varepsilon^{p}% \mathop{\mathbf{E}\mbox{}}\limits[F]}}\right]+\Pr\mathopen{}\mathclose{{\left[% F_{u_{1}}(u_{2},\ldots,u_{n})\leq\varepsilon^{1-p}\mathop{\mathbf{E}\mbox{}}% \limits[F_{u_{1}}]}}\right]$
$\displaystyle\leq\$	$\displaystyle 4d(n+1)\varepsilon^{p/(4d)}+C^{\prime}(n-1,1,d)\cdot\varepsilon^% {(1-p)C(n-1,1,d)}.$	(17)

We can take

C(n,1,d)=\max_{p}\min\mathopen{}\mathclose{{\left\{\frac{p}{4d},(1-p)C(n-1,1,d% )}}\right\}=\frac{1}{4d+C(n-1,1,d)^{-1}}=\frac{1}{4nd},

and $C^{\prime}(n,1,d)=4d(n+1)+C^{\prime}(n-1,1,d)=O(n^{2}d)$ .

3.4 $m>1,n>1$

Now we handle the general case when the inputs to the semi-polynomial consist of $m$ columns of a Haar random unitary. The proof is similar to the last stage, using the fact that the input distribution can be viewed as a unitary-invariant distribution over $m$ orthonormal vectors in $\mathbb{C}^{n}$ . In particular, let the vectors be $v_{1},\ldots,v_{m}$ , and we consider the function

P(v_{1},\ldots,v_{m-1})=\mathop{\mathbf{E}\mbox{}}\limits_{v_{m}}[F(v_{1},% \ldots,v_{m})].

Here $v_{m}$ is a Haar-random vector over the unit sphere in the $(n-m)$ -dimensional orthogonal subspace of $\mathrm{span}(v_{1},\ldots,v_{m})$ . We would like to show that $P$ is a semi-polynomial in order to use induction, and we first show it with $v_{m}$ replaced with a Gaussian distribution.

Lemma 15.

Let $v_{1},\ldots,v_{m}$ be a set of $m<n$ orthonormal vectors in $\mathbb{C}^{n}$ , and let $g=(g_{1},\ldots,g_{n})\in\mathbb{C}^{n}$ distributed as a standard $(n-m)$ -dimensional complex Gaussian in the orthogonal subspace of $\mathrm{span}(v_{1},\ldots,v_{m})$ .

Let $G:\mathbb{C}^{n}\to\mathbb{C}$ be a degree- $d$ semi-polynomial in $(g_{1},\ldots,g_{n})$ . Then

Q(v_{1},\ldots,v_{m})=\mathop{\mathbf{E}\mbox{}}\limits[G(g_{1},\ldots,g_{n})]

is a degree- $d$ semi-polynomial in the entries of $v_{1},\ldots,v_{m}$ .

Proof.

Omitted in this version. $\hfill\blacktriangleleft$

Corollary 16.

$P(v_{1},\ldots,v_{m-1})=\mathop{\mathbf{E}\mbox{}}\limits\nolimits_{v_{m}}[F(v% _{1},\ldots,v_{m})]$ is a degree- $d$ semi-polynomial in the entries of $v_{1},\ldots,v_{m-1}$ .

Proof.

Notice that $v_{m}$ is equidistributed as $g/\|g\|_{2}$ , where $g=(g_{1},\ldots,g_{n})$ is the Gaussian in Lemma 15. In other words, $g=r\cdot v_{m}$ where $r\in\mathbb{R}$ follows a fixed $\chi$ distribution independent of $v_{m}$ .

Now consider each monomial in $F$ , and let $G$ be the part of monomial over entries of $v_{m}$ , then it suffices to show that $\mathop{\mathbf{E}\mbox{}}\limits[G(v_{m})]$ is a degree- $d$ semi-polynomial in $v_{1},\ldots,v_{m-1}$ . Lemma 15 already showed this for $\mathop{\mathbf{E}\mbox{}}\limits[G(g)]$ , and since $G$ is a monomial of degree $\ell\leq d$ , we have

\mathop{\mathbf{E}\mbox{}}\limits[G(g)]=\mathop{\mathbf{E}\mbox{}}\limits[G(r% \cdot v_{m})]=\mathop{\mathbf{E}\mbox{}}\limits[r^{\ell}]\mathop{\mathbf{E}% \mbox{}}\limits[G(v_{m})],

(18)

where $\mathop{\mathbf{E}\mbox{}}\limits[r^{\ell}]$ is a non-zero constant irrelevant to the choice of $v_{1},\ldots,v_{m-1}$ . Therefore $\mathop{\mathbf{E}\mbox{}}\limits[G(v_{m})]$ is also a degree- $d$ semi-polynomial in $v_{1},\ldots,v_{m}$ . $\hfill\blacktriangleleft$

Since $P$ is an expectation over $F$ , it is also always non-negative and has the same expectation as $\mathop{\mathbf{E}\mbox{}}\limits[F]$ . Thus the induction hypothesis gives

\Pr\mathopen{}\mathclose{{\left[P(v_{1},\ldots,v_{m-1})\leq\varepsilon\mathop{% \mathbf{E}\mbox{}}\limits[F]}}\right]\leq C^{\prime}(n,m-1,d)\cdot\varepsilon^% {C(n,m-1,d)}.

(19)

Now we fix some $v_{1},\ldots,v_{m-1}$ and consider the degree- $d$ semi-polynomial

F_{v_{1},\ldots,v_{m-1}}(v_{m})=F(v_{1},\ldots,v_{m-1},v_{m}),

which is always non-negative. Since there exists a linear map $A:\mathbb{C}^{n-m+1}\to\mathbb{C}^{n}$ such that $v_{m}=Au$ , where $u$ is a Haar-random unit vector in $\mathbb{C}^{n-m+1}$ , we can apply Equation 17 from the previous stage for $m=1$ on $F_{v_{1},\ldots,v_{m-1}}(Au)$ to get

\Pr\mathopen{}\mathclose{{\left[F_{v_{1},\ldots,v_{m-1}}(Au)\leq\varepsilon% \mathop{\mathbf{E}\mbox{}}\limits\nolimits_{u}\mathopen{}\mathclose{{\left[F_{% v_{1},\ldots,v_{m-1}}(Au)}}\right]}}\right]\leq C^{\prime}(n,1,d)\cdot% \varepsilon^{C(n,1,d)}.

(20)

Therefore we conclude that, for every $p\in(0,1)$ ,

	$\displaystyle\Pr\mathopen{}\mathclose{{\left[F(v_{1},\ldots,v_{m})\leq% \varepsilon\mathop{\mathbf{E}\mbox{}}\limits[F]}}\right]$
$\displaystyle\leq\$	$\displaystyle\Pr\mathopen{}\mathclose{{\left[P(v_{1},\ldots,v_{m-1})\leq% \varepsilon^{p}\mathop{\mathbf{E}\mbox{}}\limits[F]}}\right]+\Pr\mathopen{}% \mathclose{{\left[F(v_{1},\ldots,v_{m})\leq\varepsilon^{1-p}P(v_{1},\ldots,v_{% m-1})}}\right]$
$\displaystyle=\$	$\displaystyle\Pr\mathopen{}\mathclose{{\left[P(v_{1},\ldots,v_{m-1})\leq% \varepsilon^{p}\mathop{\mathbf{E}\mbox{}}\limits[F]}}\right]+\Pr\mathopen{}% \mathclose{{\left[F_{v_{1},\ldots,v_{m-1}}(v_{m})\leq\varepsilon^{1-p}\mathop{% \mathbf{E}\mbox{}}\limits[F_{v_{1},\ldots,v_{m-1}}]}}\right]$
$\displaystyle\leq\$	$\displaystyle C^{\prime}(n,m-1,d)\cdot\varepsilon^{pC(n,m-1,d)}+C^{\prime}(n,1% ,d)\cdot\varepsilon^{(1-p)C(n,1,d)},$	(21)

Similar to the previous stage, we can take

C(n,m,d)=\frac{1}{C(n,m-1,d)^{-1}+C(n,1,d)^{-1}}=\frac{1}{4nmd},

and $C^{\prime}(n,m,d)=C^{\prime}(n,m-1,d)+C^{\prime}(n,1,d)=O(n^{2}md)$ . This completes the proof of Theorem 13.

4 Mixing Bound for Random Circuits

In this section we prove Theorem 1. Since the output qubit $\Upphi_{\mathcal{C}}(\rho)$ is in the lightcone of the input qubit $\rho$ , there exists gates $G_{1},\ldots,G_{D}$ in the circuit $\mathcal{C}$ that connect the input and output qubits. That is, there are qubits $\rho_{0},\rho_{1},\ldots,\rho_{D}$ with $\rho_{0}=\rho$ and $\rho_{D}=\Upphi_{\mathcal{C}}(\rho)$ , such that the gate $G_{i}$ has $\rho_{i-1}$ as an input and $\rho_{i}$ as an output. Each gate $G_{i}$ is independently drawn from the Haar measure $\mathcal{U}(2^{k})$ .

Note that even when gate $G_{i}$ is given, we cannot directly claim any relationship between $\rho_{i-1}$ and $\rho_{i}$ , as the other input qubits to $G_{i}$ are correlated and possibly entangled with $\rho_{i-1}$ . To handle this, we let $\tau_{i-1}$ be the composite state of the $k$ input qubits to $G_{i}$ , and by Lemma 12 we have

\mathopen{}\mathclose{{\left\|\tau_{i-1}-\tau^{\prime}_{i-1}}}\right\|_{% \mathrm{F}}\geq 2^{-k/2}\mathopen{}\mathclose{{\left\|\rho_{i-1}-\rho^{\prime}% _{i-1}}}\right\|_{\mathrm{F}},

(22)

where $\rho^{\prime}_{i}$ and $\tau^{\prime}_{i}$ are the corresponding states when the input state is $\rho^{\prime}_{0}=\rho^{\prime}$ . Therefore we only need to bridge the remaining gaps by proving

\mathopen{}\mathclose{{\left\|\rho_{i}-\rho^{\prime}_{i}}}\right\|_{\mathrm{F}% }\geq\lambda_{i}\mathopen{}\mathclose{{\left\|\tau_{i-1}-\tau^{\prime}_{i-1}}}% \right\|_{\mathrm{F}}

(23)

where $\lambda_{i}$ is some function of $G_{i}$ , and then bound the distribution of $\lambda_{i}$ by applying the anti-concentration bound from Theorem 6.

At a first glance, this looks impossible as $\tau_{i-1}$ is a $k$ -qubit state while $\rho_{i}$ is single-qubit, which means that as long as $k>1$ , whatever $G_{i}$ is, there will be input states $\tau_{i-1}\neq\tau^{\prime}_{i-1}$ to $G_{i}$ with the output qubits $\rho_{i}=\rho^{\prime}_{i}$ . The key observation is that the states $\tau_{i}$ cannot be arbitrary $k$ -qubit states: Since all the input qubits to the circuit $\mathcal{C}$ are fixed except $\rho$ , when the circuit $\mathcal{C}$ is given, each $\tau_{i}$ is the result of $\rho$ through a fixed quantum channel. As the difference $\rho-\rho^{\prime}$ ranges within the 3-dimensional Euclidean space $\Updelta_{1}$ , the difference $\tau_{i-1}-\tau^{\prime}_{i-1}$ could also only range within a 3-dimensional subspace of $\Updelta_{k}$ .

This allows us to define and bound the distribution of $\lambda_{i}$ that uniformly holds for every such subspace as follows:

Lemma 17.

For every $k\in\mathbb{N}$ , there exists a distribution $\Uplambda_{k}$ over $[0,\infty)$ that satisfies:

$\blacksquare$

There exists $t>0$ such that $\mathop{\mathbf{E}\mbox{}}\limits[\Uplambda_{k}^{-t}]<\infty$ , where we use $\mathop{\mathbf{E}\mbox{}}\limits[\Uplambda_{k}^{-t}]$ as shorthand for $\mathop{\mathbf{E}\mbox{}}\limits\nolimits_{x\sim\Uplambda_{k}}[x^{-t}]$ .
$\blacksquare$

For every fixing of the input qubits other than $\rho$ , and layers $1,\ldots,i-1$ of the circuit $\mathcal{C}$ , there exists a function $\lambda_{i}\colon\mathbb{U}(2^{k})\to[0,\infty)$ at layer $i$ such that

$\mathopen{}\mathclose{{\left\|\rho_{i}-\rho^{\prime}_{i}}}\right\|_{\mathrm{F}% }\geq\lambda_{i}(G_{i})\mathopen{}\mathclose{{\left\|\tau_{i-1}-\tau^{\prime}_% {i-1}}}\right\|_{\mathrm{F}}$

holds for all input states $\rho$ and $\rho^{\prime}$ , and $\lambda_{i}(G_{i})\sim\Uplambda_{k}$ when $G_{i}\sim\mathcal{U}(2^{k})$ .

We will prove Lemma 17 in Section 4.1. For now let us show how Lemma 17 would imply Theorem 1.

Proof of Theorem 1.

From Lemma 17 and Equation 22 we get

\mathopen{}\mathclose{{\left\|\rho_{i}-\rho^{\prime}_{i}}}\right\|_{\mathrm{F}% }\geq\lambda_{i}(G_{i})\mathopen{}\mathclose{{\left\|\tau_{i-1}-\tau^{\prime}_% {i-1}}}\right\|_{\mathrm{F}}\geq 2^{-k/2}\lambda_{i}(G_{i})\mathopen{}% \mathclose{{\left\|\rho_{i-1}-\rho^{\prime}_{i-1}}}\right\|_{\mathrm{F}}

(24)

for every $i=1,\ldots,D$ . Here each function $\lambda_{i}(G_{i})$ depends on the previous layers, but as random variables $\lambda_{i}=\lambda_{i}(G_{i})$ they are independent, since $\lambda_{i}$ follows the same distribution $\Uplambda_{k}$ no matter how $\lambda_{1},\ldots,\lambda_{i-1}$ are fixed.

Since $\mathopen{}\mathclose{{\left\|\rho_{0}-\rho^{\prime}_{0}}}\right\|_{\mathrm{F}% }=\mathopen{}\mathclose{{\left\|\rho-\rho^{\prime}}}\right\|_{\mathrm{F}}$ and $\mathopen{}\mathclose{{\left\|\rho_{D}-\rho^{\prime}_{D}}}\right\|_{\mathrm{F}% }=\mathopen{}\mathclose{{\left\|\Upphi_{\mathcal{C}}(\rho)-\Upphi_{\mathcal{C}% }(\rho^{\prime})}}\right\|_{\mathrm{F}}$ , we have

\mathopen{}\mathclose{{\left\|\Upphi_{\mathcal{C}}(\rho)-\Upphi_{\mathcal{C}}(% \rho^{\prime})}}\right\|_{\mathrm{F}}\geq 2^{-kD/2}\lambda_{1}\cdots\lambda_{D% }\mathopen{}\mathclose{{\left\|\rho-\rho^{\prime}}}\right\|_{\mathrm{F}}.

(25)

To bound the product of $\lambda_{i}$ we use Markov’s inequality, which states that for every $\alpha>0$ ,

	$\displaystyle\Pr[\lambda_{1}\cdots\lambda_{D}\leq\alpha]$	$\displaystyle=\Pr[(\lambda_{1}\cdots\lambda_{D})^{-t}\geq\alpha^{-t}]$
		$\displaystyle\leq\alpha^{t}\mathop{\mathbf{E}\mbox{}}\limits[\lambda_{1}^{-t}% \cdots\lambda_{D}^{-t}]=\alpha^{t}\mathop{\mathbf{E}\mbox{}}\limits[\Uplambda_% {k}^{-t}]^{D}$		(26)

where we take $t>0$ to be the constant in Lemma 17. Take $\alpha$ such that $\gamma=\alpha^{t}\mathop{\mathbf{E}\mbox{}}\limits[\Uplambda_{k}^{-t}]^{D}$ , we conclude that with probability at least $1-\gamma$ ,

	$\displaystyle\mathopen{}\mathclose{{\left\\|\Upphi_{\mathcal{C}}(\rho)-\Upphi_{% \mathcal{C}}(\rho^{\prime})}}\right\\|_{\mathrm{F}}$	$\displaystyle\geq 2^{-kD/2}\alpha\mathopen{}\mathclose{{\left\\|\rho-\rho^{% \prime}}}\right\\|_{\mathrm{F}}$
		$\displaystyle=2^{-kD/2}\gamma^{1/t}\mathop{\mathbf{E}\mbox{}}\limits[\Uplambda% _{k}^{-t}]^{-D/t}\mathopen{}\mathclose{{\left\\|\rho-\rho^{\prime}}}\right\\|_{% \mathrm{F}}$
		$\displaystyle=(2^{-D}\gamma)^{O_{k}(1)}\mathopen{}\mathclose{{\left\\|\rho-\rho% ^{\prime}}}\right\\|_{\mathrm{F}}.\$

$\hfill\blacktriangleleft$

4.1 Proof of Lemma 17

The basic idea of the proof is to lower bound the ratio $\mathopen{}\mathclose{{\left\|\rho_{i}-\rho^{\prime}_{i}}}\right\|_{\mathrm{F}% }/\mathopen{}\mathclose{{\left\|\tau_{i-1}-\tau^{\prime}_{i-1}}}\right\|_{% \mathrm{F}}$ with a polynomial function on the entries of $G_{i}$ and apply Theorem 6.

The quantum channel defined by $G_{i}$ that maps $\tau_{i-1}$ to $\rho_{i}$ induces the linear map

M_{i}:\tau_{i-1}-\tau^{\prime}_{i-1}\mapsto\rho_{i}-\rho_{i}^{\prime}.

The domain of $M_{i}$ is a 3-dimensional subspace of $\Updelta_{k}$ which we denote as $\mathcal{S}_{i}$ , while the range of $M_{i}$ is $\Updelta_{1}$ . Notice that the map $M_{i}$ is completely determined by the domain $\mathcal{S}_{i}$ and the gate $G_{i}$ , while $\mathcal{S}_{i}$ depends only on the fixed inputs to the circuit $\mathcal{C}$ and the gates of $\mathcal{C}$ in layers $1,\ldots,i-1$ .

Since both the domain and the range are Euclidean spaces, the absolute determinant $\mathopen{}\mathclose{{\left|\det M_{i}}}\right|$ is independent of the choices of bases when writing $M_{i}$ as matrix in $\mathbb{R}^{3\times 3}$ . We will show that $\mathopen{}\mathclose{{\left|\det M_{i}}}\right|$ is basically the lower bound that we seek for, via the following propositions whose proof can be found in the full version.

Proposition 18.

It always holds that

\mathopen{}\mathclose{{\left\|\rho_{i}-\rho^{\prime}_{i}}}\right\|_{\mathrm{F}% }\geq 2^{-k}\mathopen{}\mathclose{{\left|\det M_{i}}}\right|\cdot\mathopen{}% \mathclose{{\left\|\tau_{i-1}-\tau^{\prime}_{i-1}}}\right\|_{\mathrm{F}}.

Proposition 19.

For each fixed domain $\mathcal{S}_{i}$ , $\det M_{i}$ is a degree-6 semi-polynomial in the entries of $G_{i}$ .

Proposition 20.

There exists a constant $\mu_{k}>0$ such that for every possible domain $\mathcal{S}_{i}$ ,

\mathop{\mathbf{E}\mbox{}}\limits_{G_{i}\sim\mathcal{U}(2^{k})}\mathopen{}% \mathclose{{\left[\mathopen{}\mathclose{{\left|\det M_{i}}}\right|^{2}}}\right% ]\geq\mu_{k}.

Now we are ready to prove Lemma 17.

Proof of Lemma 17.

Applying Theorem 6 with Propositions 19 and 20 gives

	$\displaystyle\Pr\mathopen{}\mathclose{{\left[2^{-k}\mathopen{}\mathclose{{% \left\|\det M_{i}}}\right\|\leq\varepsilon}}\right]$	$\displaystyle\leq\Pr\mathopen{}\mathclose{{\left[\mathopen{}\mathclose{{\left\|% \det M_{i}}}\right\|^{2}\leq 2^{2k}\mu_{k}^{-1}\varepsilon^{2}\mathop{\mathbf{E% }\mbox{}}\limits\mathopen{}\mathclose{{\left[\mathopen{}\mathclose{{\left\|\det M% _{i}}}\right\|^{2}}}\right]}}\right]$
		$\displaystyle\leq C^{\prime}(2^{k},6)\cdot(2^{2k}\mu_{k}^{-1}\varepsilon^{2})^% {C(2^{k},6)}$		(27)

which holds for every domain $\mathcal{S}_{i}$ and every $\varepsilon\geq 0$ . We define $\Uplambda_{k}$ as the distribution over $[0,\infty)$ with the following cumulative function:

\Pr[\Uplambda_{k}\leq x]=\min\mathopen{}\mathclose{{\left\{C^{\prime}(2^{k},6)% \cdot(2^{2k}\mu_{k}^{-1}x^{2})^{C(2^{k},6)},1}}\right\}.

Take $t=C(2^{k},6)>0$ and let $C=C^{\prime}(2^{k},6)\cdot(2^{2k}\mu_{k}^{-1})^{C(2^{k},6)}>0$ , then we have

$\displaystyle\mathop{\mathbf{E}\mbox{}}\limits[\Uplambda_{k}^{-t}]$	$\displaystyle=\int_{0}^{\infty}x^{-t}\mathrm{d}\Pr[\Uplambda_{k}\leq x]$
	$\displaystyle=\int_{0}^{C^{-1/(2t)}}x^{-t}\mathrm{d}(Cx^{2t})$
	$\displaystyle=\int_{0}^{C^{-1/(2t)}}2tC\cdot x^{t-1}\mathrm{d}x=2tC^{1/2}<\infty.$	(28)

Now suppose the input qubits other than $\rho$ are fixed, and the layers $1,\ldots,i-1$ of the circuit $\mathcal{C}$ is given. This fixes the domain $\mathcal{S}_{i}$ for $M_{i}$ , and provides the cumulative function

P(x)=\Pr\mathopen{}\mathclose{{\left[2^{-k}\mathopen{}\mathclose{{\left|\det M% _{i}}}\right|\leq x}}\right].

Notice that $P$ is continuous and non-decreasing, and by defining its inverse $P^{-1}(y)=\sup_{x}P(x)\leq y$ on $[0,1]$ , we can show that for every $y\in[0,1]$ ,

\Pr\mathopen{}\mathclose{{\left[P\big(2^{-k}\mathopen{}\mathclose{{\left|\det M% _{i}}}\right|\big)\leq y}}\right]=\Pr\mathopen{}\mathclose{{\left[2^{-k}% \mathopen{}\mathclose{{\left|\det M_{i}}}\right|\leq P^{-1}(y)}}\right]=P(P^{-% 1}(y))=y.

We then define the function $\lambda_{i}:\mathbb{U}(2^{k})\to[0,\infty)$ as follows: For each $G_{i}\in\mathbb{U}(2^{k})$ , let $\lambda_{i}(G_{i})$ be the smallest $\lambda\geq 0$ such that

P\big(2^{-k}\mathopen{}\mathclose{{\left|\det M_{i}}}\right|\big)=\Pr[% \Uplambda_{k}\leq\lambda].

When $G_{i}\sim\mathcal{U}(2^{k})$ , we have $\lambda_{i}(G_{i})\sim\Uplambda_{k}$ since

\Pr[\lambda_{i}(G_{i})\leq x]=\Pr\mathopen{}\mathclose{{\left[P\big(2^{-k}% \mathopen{}\mathclose{{\left|\det M_{i}}}\right|\big)\leq\Pr[\Uplambda_{k}\leq x% ]}}\right]=\Pr[\Uplambda_{k}\leq x].

(29)

We also have $2^{-k}\mathopen{}\mathclose{{\left|\det M_{i}}}\right|\geq\lambda_{i}(G_{i})$ since $P(x)\leq\Pr[\Uplambda_{k}\leq x]$ holds for all $x\geq 0$ . Combined with Proposition 18 we get

\mathopen{}\mathclose{{\left\|\rho_{i}-\rho^{\prime}_{i}}}\right\|_{\mathrm{F}% }\geq 2^{-k}\mathopen{}\mathclose{{\left|\det M_{i}}}\right|\cdot\mathopen{}% \mathclose{{\left\|\tau_{i-1}-\tau^{\prime}_{i-1}}}\right\|_{\mathrm{F}}\geq% \lambda_{i}(G_{i})\mathopen{}\mathclose{{\left\|\tau_{i-1}-\tau^{\prime}_{i-1}% }}\right\|_{\mathrm{F}}.\

$\hfill\blacktriangleleft$

5 Applications

5.1 Depth Lower Bound for Approximate Designs

In this section we prove Theorem 2. We first recall the definition of an approximate unitary design.

Definition 21.

For a distribution $\mathcal{D}$ over $\mathbb{U}(n)$ and $t\in\mathbb{N}_{+}$ , define the moment superoperator as the following channel:

\Upphi^{(t)}_{\mathcal{D}}:\rho\mapsto\int_{\mathbb{U}(n)}U^{\otimes t}\rho(U^% {\dagger})^{\otimes t}\mathrm{d}\mathcal{D}(U).

The distribution $\mathcal{D}$ is an $\varepsilon$ -approximate unitary $t$ -design if

\mathopen{}\mathclose{{\left\|\Upphi^{(t)}_{\mathcal{D}}-\Upphi^{(t)}_{% \mathcal{U}(n)}}}\right\|_{\diamond}\leq\varepsilon.

Note that there are several other definitions of the approximate design (see e.g. [10]), and we choose the weaker one so that our Theorem 2 is still compatible with the stronger definitions of designs.

Proof of Theorem 2.

Without loss of generality, let us assume that the first input qubit $\rho$ and the first output qubit $\pi$ are depth $D$ apart. We fix all other input qubits to be maximally mixed, so that when $\rho$ is also maximally mixed, the entire output is maximally mixed regardless of the circuit $\mathcal{C}$ , and thus $\pi=I/2$ . On the other hand, when $\rho=|0\rangle\langle 0|$ , we know the following about the output qubit $\pi$ via Theorem 1 that with probability $1-2^{-D}$ over the circuit $\mathcal{C}$ ,

\mathopen{}\mathclose{{\left\|\pi-I/2}}\right\|_{\mathrm{F}}\geq\mathopen{}% \mathclose{{\left\||0\rangle\langle 0|-I/2}}\right\|_{\mathrm{F}}\cdot(2^{-2D}% )^{c_{k}}=\frac{1}{\sqrt{2}}\cdot 2^{-2Dc_{k}}.

(30)

We can expand the left hand side of Equation 30 as

\mathopen{}\mathclose{{\left\|\pi-I/2}}\right\|_{\mathrm{F}}^{2}=\mathrm{Tr}[(% \pi-I/2)^{2}]=\mathrm{Tr}[\pi^{2}]-1/2.

(31)

Since $\mathrm{Tr}[\pi^{2}]\leq 1$ always holds, we get

\mathop{\mathbf{E}\mbox{}}\limits\nolimits_{\mathcal{C}}[\mathrm{Tr}[\pi^{2}]]% \geq\frac{1}{2}+\frac{1}{2}\cdot 2^{-4Dc_{k}}+\frac{1}{2}\cdot 2^{-D}.

(32)

Now imagine feeding two copies of the input state $|0\rangle\langle 0|\otimes(I/2)^{\otimes(n-1)}$ to the superoperators $\Upphi^{(2)}_{\mathcal{C}}$ and $\Upphi^{(2)}_{\mathcal{U}(n)}$ , and apply a swap test on the first output qubits in the two copies. The output probability is determined by $\mathrm{Tr}[\pi^{2}]$ . We know already from [20] that when going through an $n$ -qubit Haar random unitary, we have $\mathop{\mathbf{E}\mbox{}}\limits\nolimits_{\mathcal{U}(n)}[\mathrm{Tr}[\pi^{2% }]]=1/2$ . Therefore, we conclude that the difference $2^{-4Dc_{k}}+2^{-D}\leq O(\varepsilon)$ which means that $D\geq\Omega_{k}(\log\varepsilon^{-1})$ . $\hfill\blacktriangleleft$

5.2 Depth Test

In this section we prove Theorem 3, where we learn the exact depth of a brickwork random circuit $\mathcal{C}$ .

Algorithm 1 Algorithm for depth testing.

The processed is described in Algorithm 1. Here $c_{2}$ is the constant $c_{k}$ in Theorem 1 with $k=2$ for brickwork circuits, and $\gamma>0$ is the target error probability. Notice that in a brickwork circuit of depth $D$ , the $(D+2)$ -th output qubit lies outside the lightcone of the first input qubit. Therefore, when the algorithm iterates to the correct depth $D$ , we have $\pi=\pi^{\prime}$ and $D$ must be returned even when both $\pi$ and $\pi^{\prime}$ are estimated with $\varepsilon$ error.

On the other hand, when $D$ is smaller than the actual depth, the $(D+2)$ -th output qubit lies inside the lightcone of the first input qubit. By Theorem 1, with probability $1-2^{-D}\gamma$ over $\mathcal{C}$ we have

\mathopen{}\mathclose{{\left\|\pi-\pi^{\prime}}}\right\|_{\mathrm{F}}\geq% \mathopen{}\mathclose{{\left\||0\rangle\langle 0|-|1\rangle\langle 1|}}\right% \|_{\mathrm{F}}\cdot(2^{-2D}\gamma)^{c_{2}}>4\varepsilon.

(33)

This means when both $\pi$ and $\pi^{\prime}$ are estimated with $\varepsilon$ error, we still have $\mathopen{}\mathclose{{\left\|\pi-\pi^{\prime}}}\right\|_{\mathrm{F}}>2\varepsilon$ . By a union bound over $D$ , with probability $1-\gamma$ all those $D$ smaller than the actual depth will be skipped, and thus the outputted depth is correct.

Note that the efficiency of the algorithm depends on the single-qubit tomography process, which by Proposition 11 is $\mathrm{poly}(1/\varepsilon)$ . As a conclusion, we obtain the following more general statement which implies Theorem 3:

Theorem 22.

Let $\mathcal{C}$ be a brickwork random quantum circuit of an unknown depth $D$ , where each gate is independently Haar random.. Given oracle access to $\mathcal{C}$ , for any $\gamma\in(0,1)$ , Algorithm 1 outputs $D$ with probability at least $1-\gamma$ in time $\mathrm{poly}(2^{D},\gamma^{-1})$ .

$\blacktriangleright$ Remark 23.

The only property of the brickwork architecture we used here is that the set of qubits within the lightcone of an input qubit is strictly expanding when the depth grows, which allows us to distinguish between different depths. Therefore the algorithm can be easily modified, with the same efficiency, to work with higher dimensional brickwork circuits and other architectures.

5.3 Learning Brickwork Random Circuits

5.3.1 Learning the First Gate

Here we prove Theorem 4, where we learn the gate $G_{1,1}$ , namely the gate in the first layer acting on the first and second qubit, in a brickwork circuit of depth $D=O(\log n)$ with Haar random gates. The same arguments also work for other gates in the first layer.

To learn $G_{1,1}$ , we try to uncompute $G_{1,1}$ by first apply some two-qubit unitary $G^{\dagger}\in\mathbb{U}(4)$ and then apply the circuit $\mathbb{C}$ . We distinguish whether $G$ is close to $G_{1,1}$ or not using the similar idea as in Section 5.2. Specifically, if $G=G_{1,1}$ so that $G^{\dagger}$ perfectly uncomputes the gate $G_{1,1}$ , then the $(D+1)$ -th output qubit will lie outside the lightcone of the first input qubit. Note that this is also true when $G^{\dagger}$ cancels $G_{1,1}$ into unentangled single-qubit gates, that is when there exists $U_{1},U_{2}\in\mathbb{U}(2)$ that $G_{1,1}G^{\dagger}=U_{1}\otimes U_{2}$ . In contrast, when $G^{\dagger}$ does not cancel $G_{1,1}$ into unentangled single-qubit gates, the first two qubits will be entangled after the first layer of gates, and thus the $(D+1)$ -th output qubit will be affected when the first input qubit changes.

To put the above intuition more formally, we first define the distance between two-qubit gates when taking the quotient over unentangled single-qubit gates:

Definition 24.

For $G,G^{\prime}\in\mathbb{U}(4)$ , we define the distance

d_{\otimes}(G,G^{\prime})=\min_{U_{1},U_{2}\in\mathbb{U}(2)}d_{\diamond}(G,(U_% {1}\otimes U_{2})\cdot G^{\prime}).

We note that $d_{\otimes}$ , like the diamond distance $d_{\diamond}$ , is a pseudometric on $\mathbb{U}(4)$ . That is, a metric except that two distinct unitaries could have distance zero. However, $d_{\otimes}(G,G^{\prime})=0$ if and only if $G^{\prime}\cdot G^{-1}=U_{1}\otimes U_{2}$ for some $U_{1},U_{2}\in\mathbb{U}(2)$ .

The learning algorithm is described in Algorithm 2, with $\delta,\gamma>0$ being the target error rate. Notice that within each loop of $\sigma_{2}$ , the second input qubit $\rho_{2}$ is fixed, while the first one changes with a difference $\sigma_{1}$ that goes through the Pauli basis. The input qubits $\rho_{1}$ and $\rho_{2}$ are Pauli eigenstates except when $\sigma_{2}=\rho_{2}=I/2$ , which can be obtained by randomly choosing $|0\rangle$ or $|1\rangle$ .

Algorithm 2 Algorithm for learning the gate

G_{1,1}

.

To prove the correctness of the algorithm, we need the following lemmas that connects the distance $d_{\otimes}(U,I\otimes I)$ with the behavior of $U$ over the Pauli basis.

Lemma 25.

For $U\in\mathbb{U}(4)$ , if $d_{\otimes}(U,I\otimes I)\leq\delta$ then for every $\sigma_{1}\in\{X,Y,Z\}$ and $\sigma_{2}\in\{I,X,Y,Z\}$ ,

\mathopen{}\mathclose{{\left\|\mathrm{Tr}_{A}\mathopen{}\mathclose{{\left[U(% \sigma_{1}\otimes\sigma_{2})U^{\dagger}}}\right]}}\right\|_{\mathrm{F}}\leq 2\delta,

where $\mathrm{Tr}_{A}$ is the partial trace that traces out the first qubit.

Lemma 26.

For $U\in\mathbb{U}(4)$ , if for every $\sigma_{1}\in\{X,Y,Z\}$ and $\sigma_{2}\in\{I,X,Y,Z\}$ we have

\mathopen{}\mathclose{{\left\|\mathrm{Tr}_{A}\mathopen{}\mathclose{{\left[U(% \sigma_{1}\otimes\sigma_{2})U^{\dagger}}}\right]}}\right\|_{\mathrm{F}}\leq\delta,

then $d_{\otimes}(U,I\otimes I)\leq 20\sqrt{\delta}$ .

The proof of Lemma 26 is rather technical and thus is omitted in this version. For now, let us show how Lemmas 25 and 26 would imply the completeness and the soundness of Algorithm 2.

We apply Theorem 1 to the circuit $\mathcal{C}$ minus its first layer, which is a circuit of depth $D-1$ . Notice that among the input qubits to the second layer of $\mathcal{C}$ , the third to $n$ -th qubits only depends on the gates $G_{1,3},\ldots,G_{1,n}$ and thus can be viewed as fixed. The first qubit does not affect the $(D+1)$ -th output qubit and thus its entire lightcone can be removed from the picture. That leaves us the second qubit, which is

\mathrm{Tr}_{A}\mathopen{}\mathclose{{\left[G_{1,1}G^{\dagger}(\rho_{1}\otimes% \rho_{2})GG_{1,1}^{\dagger}}}\right].

Therefore, with $\rho_{1}$ changed with a difference $\sigma_{1}$ and $\rho_{2}=(I+\sigma_{2})/2$ unchanged, Theorem 1 implies that with probability $1-\gamma$ , the following holds for every $G$ .

\mathopen{}\mathclose{{\left\|\pi-\pi^{\prime}}}\right\|_{\mathrm{F}}\geq% \mathopen{}\mathclose{{\left\|\mathrm{Tr}_{A}\mathopen{}\mathclose{{\left[G_{1% ,1}G^{\dagger}(\sigma_{1}\otimes\rho_{2})GG_{1,1}^{\dagger}}}\right]}}\right\|% _{\mathrm{F}}\cdot(2^{-D+1}\gamma)^{c_{2}}.

(34)

Meanwhile, Lemma 12 implies that

\mathopen{}\mathclose{{\left\|\pi-\pi^{\prime}}}\right\|_{\mathrm{F}}\leq% \mathopen{}\mathclose{{\left\|\mathrm{Tr}_{A}\mathopen{}\mathclose{{\left[G_{1% ,1}G^{\dagger}(\sigma_{1}\otimes\rho_{2})GG_{1,1}^{\dagger}}}\right]}}\right\|% _{\mathrm{F}}\cdot\sqrt{2}.

(35)

For completeness, since we take $G$ from an $\varepsilon$ -net, the algorithm must have tested some $G$ with $d_{\otimes}(G_{1,1},G)=d_{\otimes}(G_{1,1}G^{\dagger},I\otimes I)\leq% \varepsilon\leq\delta$ . Hence by Lemma 25 and Equation 35, for such $G$ it always holds that $\mathopen{}\mathclose{{\left\|\pi-\pi^{\prime}}}\right\|_{\mathrm{F}}\leq 2% \sqrt{2}\varepsilon$ , and thus $G$ will not be rejected even with $\varepsilon$ tomography errors in $\pi$ and $\pi^{\prime}$ .

For soundness, assume that $d_{\otimes}(G_{1,1},G)>\delta$ , then by Lemma 26 we know that for some $\sigma_{1}\in\{X,Y,Z\}$ and $\sigma_{2}\in\{I,X,Y,Z\}$ ,

\mathopen{}\mathclose{{\left\|\mathrm{Tr}_{A}\mathopen{}\mathclose{{\left[G_{1% ,1}G^{\dagger}(\sigma_{1}\otimes\sigma_{2})GG_{1,1}^{\dagger}}}\right]}}\right% \|_{\mathrm{F}}>\frac{1}{400}\delta^{2}.

(36)

As $\sigma_{2}=2\rho_{2}-I$ , that means there exists some $\rho_{2}$ such that

\mathopen{}\mathclose{{\left\|\mathrm{Tr}_{A}\mathopen{}\mathclose{{\left[G_{1% ,1}G^{\dagger}(\sigma_{1}\otimes\rho_{2})GG_{1,1}^{\dagger}}}\right]}}\right\|% _{\mathrm{F}}>\frac{1}{1200}\delta^{2}.

(37)

Thus by Equation 34 we have $\mathopen{}\mathclose{{\left\|\pi-\pi^{\prime}}}\right\|_{\mathrm{F}}>\delta^{% 2}(2^{-D+1}\gamma)^{c_{2}}/1200>7\varepsilon$ , and $G$ will be rejected when $\pi$ and $\pi^{\prime}$ are estimated with $\varepsilon$ error.

The efficiency of the algorithm depends on the size of the $\varepsilon$ -net and the state tomography process, which are both $\mathrm{poly}(1/\varepsilon)=\mathrm{poly}(1/\delta,1/\gamma)$ . Notice that the algorithm similarly works for every gate in the first layer, and as a result, we obtained the following formal statement of Theorem 4:

Theorem 27.

Let $\mathcal{C}$ be a brickwork random quantum circuit of depth $D$ , where each gate is independently Haar random. Let $G_{1,1}$ be the gate in the first layer of $\mathcal{C}$ that acts on the first and second qubit. Given oracle access to $\mathcal{C}$ , for any $\delta,\gamma\in(0,1)$ , with probability at least $1-\gamma$ over $\mathcal{C}$ , Algorithm 2 outputs some $G\in\mathbb{U}(4)$ such that $d_{\otimes}(G,G_{1,1})\leq\delta$ in time $\mathrm{poly}(2^{D},1/\delta,1/\gamma)$ .

5.3.2 Learning the Circuit with Discretized Distribution

It is tempting to use Theorem 27 to learn the entire circuit $\mathcal{C}$ . Indeed, if the statement is errorless that $d_{\otimes}(G,G_{1,1})=0$ , we could view the single-qubit gates $G_{1,1}G^{\dagger}=U_{1}\otimes U_{2}$ as part of the second layer. That means after learning the first layer, we can perfectly uncompute it and hence use Algorithm 2 to learn the second layer, and proceed until we are only left with single qubit gates, which are easily learnable.

However, when there are learning errors, which are inevitable for a continuous gate distribution like $\mathcal{U}(4)$ , the above framework runs into a problem. Since we cannot perfectly uncompute the first layer, the inputs to the rest of the circuit are not clean enough: In particular, the error in $\sigma_{1}\otimes\rho_{2}$ could have much larger influence on the output difference $\pi-\pi^{\prime}$ than $\sigma_{1}$ itself. To control the influence of the errors, we need to reduce the learn error in the previous layer to be polynomially smaller than the target error in the current layer, and therefore a circuit of depth $D=\Uptheta(\log n)$ would require error as small as $2^{-\Omega(\log^{2}n)}$ and incur quasi-polynomial running time.

Here we present a bypass to the problem which allows us to prove an errorless version of Theorem 27 and thus make the proposed framework work. The idea is to change the distribution from $\mathbb{U}(4)$ into a discrete one that approximates $\mathbb{U}(4)$ . Intuitively, any $\varepsilon$ -net where the elements are distributed according to $\mathcal{U}(4)$ would be a good approximation. We formalize this intuition as the following:

Definition 28.

An $\varepsilon$ -net of a distribution $\mathcal{D}$ over a pseudometric space $(S,d)$ is a distribution $\mathcal{D}_{\varepsilon}$ over $S$ with a finite support, such that $\mathcal{D}_{\varepsilon}=f(\mathcal{D})$ for some (possibly randomized) map $f:S\to S$ , with the following properties:

$\blacksquare$

For every $x\in S$ , $d(x,f(x))\leq\varepsilon$ .
$\blacksquare$

For every $x_{1},x_{2}\in S$ , either $f(x_{1})=f(x_{2})$ or $d(f(x_{1}),f(x_{2}))\geq\varepsilon$ .

Notice that under Definition 28, the set $\mathop{\mathrm{supp}}\mathcal{D}_{\varepsilon}$ is indeed an $\varepsilon$ -net in the normal sense. Actually, the definition is general enough so that we can first choose any $\varepsilon$ -net as the support, remove the redundant elements with zero distances, and then take $f$ to be an arbitrary rounding scheme into the support. We show that $\mathcal{D}_{\varepsilon}$ approximates $\mathcal{D}$ via the following lemma.

Lemma 29.

If $F:S\to\mathbb{R}$ is $L$ -Lipschitz, that is for all $x_{1},x_{2}\in S$ ,

|F(x_{1})-F(x_{2})|\leq L\cdot d(x_{1},x_{2}),

then for every $\delta\in\mathbb{R}$ we have

\Pr_{x\sim\mathcal{D}_{\varepsilon}}[F(x)\leq\delta]\leq\Pr_{x\sim\mathcal{D}}% [F(x)\leq\delta+\varepsilon L].

From now on, for each $\varepsilon>0$ we fix some $\varepsilon$ -net of the Haar measure $\mathcal{U}(4)$ under the $d_{\otimes}$ distance, and denote it by $\mathcal{U}_{\varepsilon}(4)$ . We will show that when the gates in the brickwork circuit are drawn the net, we can actually use the framework at the start of this section to learn the circuit. To do so, we first prove an errorless version of Theorem 27 as follows.

Theorem 30.

Let $\mathcal{C}$ be a brickwork random quantum circuit of depth $D$ , where each gate is independently drawn from $\mathcal{U}_{\varepsilon}(4)$ . Let $G_{1,1}$ be the gate in the first layer of $\mathcal{C}$ that acts on the first and second qubit. Given oracle access to $\mathcal{C}$ , for every $\gamma\in(0,1)$ there is an algorithm that with probability at least $1-\gamma$ over $\mathcal{C}$ outputs $G_{1,1}$ in time $\mathrm{poly}(2^{D},1/\gamma)$ .

Proof.

The algorithm is basically the same as Algorithm 2, except that we now iterate $G$ through the support of $\mathcal{U}_{\varepsilon}(4)$ . The proof is also mostly the same: When $G=G_{1,1}$ , we have $\pi=\pi^{\prime}$ and thus $G$ will not be rejected; Otherwise $d_{\otimes}(G,G_{1,1})\geq\varepsilon$ , and the proof goes through as long as we have the corresponding version of Theorem 1.

Since Theorem 1 is proved via Lemma 17, it suffices to prove Lemma 17 where $\mathcal{U}(4)$ is replaced with $\mathcal{U}_{\varepsilon}(4)$ . The crux is to prove the inequality Equation 27, that is for some $C,C^{\prime}>0$ , it holds for all $x\geq 0$ that

\Pr[\mathopen{}\mathclose{{\left|\det M}}\right|\leq x]\leq C^{\prime}x^{C},

(38)

where $M$ is the matrix form of the linear map $M:\tau-\tau^{\prime}\mapsto\mathrm{Tr}_{A}[G(\tau-\tau^{\prime})G^{\dagger}]$ , for $\tau-\tau^{\prime}$ in a certain fixed 3-dimensional subspace of $\Delta_{2}$ .

Note that by Proposition 18, each entry of $M$ is in $[-2,2]$ , while by Proposition 19, each entry of $M$ is a Lipschitz function of $G$ under distance $d_{\diamond}$ . This is because when $G,G^{\prime}\in\mathbb{U}(4)$ that $d_{\diamond}(G,G^{\prime})\leq\delta$ corresponds to matrices $M$ and $M^{\prime}$ , for any $\tau-\tau^{\prime}\in\Delta_{2}$ and $\sigma\in\Delta_{1}$ with $\mathopen{}\mathclose{{\left\|\tau-\tau^{\prime}}}\right\|_{\mathrm{F}}=% \mathopen{}\mathclose{{\left\|\sigma}}\right\|_{\mathrm{F}}=1$ we have

\displaystyle\mathopen{}\mathclose{{\left|\mathrm{Tr}[\sigma M(\tau-\tau^{% \prime})]-\mathrm{Tr}[\sigma M^{\prime}(\tau-\tau^{\prime})]}}\right|\leq 2\delta.

(39)

As $\det M$ consists of $6$ monomials of degree $3$ in the entries of $M$ , we conclude that $\mathopen{}\mathclose{{\left|\det M}}\right|$ is $2^{3}\cdot 3\cdot 6=144$ -Lipschitz in $G$ under $d_{\diamond}$ . But when $G^{\prime}=(U_{1}\otimes U_{2})G$ we have $M^{\prime}=U_{2}MU_{2}^{\dagger}$ which means $\mathopen{}\mathclose{{\left|\det M}}\right|=\mathopen{}\mathclose{{\left|\det M% ^{\prime}}}\right|$ , and thus $\mathopen{}\mathclose{{\left|\det M}}\right|$ is also 144-Lipschitz in $G$ under $d_{\otimes}$ .

As a result, since we already know that Equation 38 holds when $G\sim\mathcal{U}(4)$ , by Lemma 29 we have

\Pr_{G\sim\mathcal{U}_{\varepsilon}(4)}[\mathopen{}\mathclose{{\left|\det M}}% \right|\leq x]\leq\Pr_{G\sim\mathcal{U}(4)}[\mathopen{}\mathclose{{\left|\det M% }}\right|\leq x+144\varepsilon]\leq C^{\prime}(x+144\varepsilon)^{C}.

(40)

However, this will not yield Lemma 17 as the bound is even non-zero when $x=0$ . Fortunately, we can simply use the union bound to ignore the cases when $\mathopen{}\mathclose{{\left|\det M}}\right|\leq\varepsilon$ for any gate $G$ on the path, which will only add $\mathrm{poly}(\varepsilon)D$ to the error probability $\gamma$ . And conditioned on $\mathopen{}\mathclose{{\left|\det M}}\right|>\varepsilon$ , for every $x\geq 0$ we have

\Pr_{G\sim\mathcal{U}_{\varepsilon}(4)}[\mathopen{}\mathclose{{\left|\det M}}% \right|\leq x]\leq C^{\prime}(145x)^{C},

(41)

which allows us to prove Lemma 17 on $\mathcal{U}_{\varepsilon}(4)$ , albeit with different constants. $\hfill\blacktriangleleft$

As a result, we can use Theorem 30 to exactly learn the circuit $\mathcal{C}$ layer by layer, and obtain Theorem 5 formally as follows.

Theorem 31.

Let $\mathcal{C}$ be a brickwork random quantum circuit on $n$ qubits of depth $D$ , where each gate is independently drawn from $\mathcal{U}_{\varepsilon}(4)$ . Given oracle access to $\mathcal{C}$ , for every $\gamma\in(0,1)$ there is an algorithm that with probability at least $1-\gamma$ outputs $\mathcal{C}$ in time $\mathrm{poly}(n,2^{D},1/\gamma)$ .

References

[1] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, STOC ’11, pages 333–342, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1993636.1993682.
[2] Scott Aaronson and Shih-Han Hung. Certified randomness from quantum supremacy. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 933–944, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585145.
[3] Frank Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, October 2019. doi:10.1038/s41586-019-1666-5.
[4] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, and Avishay Tal. On certified randomness from fourier sampling or random circuit sampling, 2024. arXiv:2111.14846.
[5] Bruno Bertini and Lorenzo Piroli. Scrambling in random unitary circuits: Exact results. Phys. Rev. B, 102:064305, August 2020. doi:10.1103/PhysRevB.102.064305.
[6] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6):595–600, April 2018. doi:10.1038/s41567-018-0124-x.
[7] Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu. Noise and the frontier of quantum supremacy. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, February 2022. doi:10.1109/focs52979.2021.00127.
[8] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159–163, October 2018. doi:10.1038/s41567-018-0318-2.
[9] Paolo Braccia, Pablo Bermejo, Lukasz Cincio, and M. Cerezo. Computing exact moments of local random quantum circuits via tensor networks, 2024. arXiv:2403.01706.
[10] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Commun. Math. Phys., 346(2):397–434, 2016. doi:10.1007/s00220-016-2706-8.
[11] Winton Brown and Omar Fawzi. Scrambling speed of random quantum circuits, 2013. arXiv:1210.6644.
[12] Anthony Carbery and James Wright. Distributional and $L^{q}$ norm inequalities for polynomials over convex bodies in $\mathbb{R}^{n}$ . Mathematical Research Letters, 8(3):233–248, 2001. doi:10.4310/mrl.2001.v8.n3.a1.
[13] Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão, Jordan Docter, Patrick Hayden, and Michelle Xu. Efficient unitary designs and pseudorandom unitaries from permutations, 2024. doi:10.48550/arXiv.2404.16751.
[14] Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, and Patrick Hayden. Efficient unitary t-designs from random sums, 2024. doi:10.48550/arXiv.2402.09335.
[15] Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. Incompressibility and spectral gaps of random circuits, 2024. doi:10.48550/arXiv.2406.07478.
[16] Chi-Fang Chen and Andrew Lucas. Operator growth bounds from graph theory. Communications in Mathematical Physics, 385(3):1273–1323, July 2021. doi:10.1007/s00220-021-04151-6.
[17] Chi-Fang Chen, Andrew Lucas, and Chao Yin. Speed limits and locality in many-body quantum dynamics. Reports on Progress in Physics, 86(11):116001, September 2023. doi:10.1088/1361-6633/acfaae.
[18] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão. Random quantum circuits anticoncentrate in log depth. PRX Quantum, 3(1), March 2022. doi:10.1103/prxquantum.3.010333.
[19] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A, 80:012304, July 2009. doi:10.1103/PhysRevA.80.012304.
[20] Joseph Emerson, Robert Alicki, and Karol Zyczkowski. Scalable noise estimation with random unitary operators. Journal of Optics B: Quantum and Semiclassical Optics, 7, March 2005. doi:10.1088/1464-4266/7/10/021.
[21] Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. Effect of non-unital noise on random circuit sampling, 2023. doi:10.48550/arXiv.2306.16659.
[22] Matthew P.A. Fisher, Vedika Khemani, Adam Nahum, and Sagar Vijay. Random quantum circuits. Annual Review of Condensed Matter Physics, 14(1):335–379, 2023. doi:10.1146/annurev-conmatphys-031720-030658.
[23] Jeongwan Haah, Yunchao Liu, and Xinyu Tan. Efficient approximate unitary designs from random pauli rotations, 2024. doi:10.48550/arXiv.2402.05239.
[24] Jonas Haferkamp. Random quantum circuits are approximate unitary $t$ -designs in depth $O\mathopen{}\mathclose{{\left(nt^{5+o(1)}}}\right)$ . Quantum, 6:795, September 2022. doi:10.22331/q-2022-09-08-795.
[25] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert. Anticoncentration theorems for schemes showing a quantum speedup. Quantum, 2:65, May 2018. doi:10.22331/q-2018-05-22-65.
[26] Dominik Hangleiter and Michael J. Gullans. Bell sampling from quantum circuits. Phys. Rev. Lett., 133:020601, July 2024. doi:10.1103/PhysRevLett.133.020601.
[27] Aram W. Harrow, Linghang Kong, Zi-Wen Liu, Saeed Mehraban, and Peter W. Shor. Separation of out-of-time-ordered correlation and entanglement. PRX Quantum, 2:020339, June 2021. doi:10.1103/PRXQuantum.2.020339.
[28] Aram W. Harrow and Richard A. Low. Random quantum circuits are approximate 2-designs. Communications in Mathematical Physics, 291(1):257–302, July 2009. doi:10.1007/s00220-009-0873-6.
[29] Aram W. Harrow and Saeed Mehraban. Approximate unitary $t$ -designs by short random quantum circuits using nearest-neighbor and long-range gates. Commun. Math. Phys., 401(2):1531–1626, 2023. doi:10.1007/s00220-023-04675-z.
[30] Patrick Hayden and John Preskill. Black holes as mirrors: quantum information in random subsystems. Journal of High Energy Physics, 2007(09):120–120, September 2007. doi:10.1088/1126-6708/2007/09/120.
[31] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean. Learning shallow quantum circuits. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1343–1351, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649722.
[32] Nicholas Hunter-Jones. Unitary designs from statistical mechanics in random quantum circuits, 2019. arXiv:1905.12053.
[33] Shao-Kai Jian, Gregory Bentsen, and Brian Swingle. Linear growth of circuit complexity from brownian dynamics, 2022. arXiv:2206.14205.
[34] Daniel Kane. A structure theorem for poorly anticoncentrated polynomials of gaussians and applications to the study of polynomial threshold functions. The Annals of Probability, 45(3):1612–1679, 2017. doi:10.1214/16-AOP1097.
[35] Zeph Landau and Yunchao Liu. Learning quantum states prepared by shallow circuits in polynomial time, 2024. doi:10.48550/arXiv.2410.23618.
[36] Elliott H. Lieb and Derek W. Robinson. The finite group velocity of quantum spin systems. Communications In Mathematical Physics, 28(3):251–257, September 1972. doi:10.1007/BF01645779.
[37] Yunchao Liu, Matthew Otten, Roozbeh Bassirianjahromi, Liang Jiang, and Bill Fefferman. Benchmarking near-term quantum computers via random circuit sampling, 2022. arXiv:2105.05232.
[38] Shachar Lovett. An elementary proof of anti-concentration of polynomials in gaussian variables. Electronic Colloquium on Computational Complexity (ECCC), 2010. URL: https://eccc.weizmann.ac.il/report/2010/182.
[39] Elizabeth S Meckes. The random matrix theory of the classical compact groups, volume 218. Cambridge University Press, 2019. doi:10.1017/9781108303453.
[40] Raghu Meka, Oanh Nguyen, and Van Vu. Anti-concentration for polynomials of independent random variables. Theory of Computing, 12(11):1–17, 2016. doi:10.4086/toc.2016.v012a011.
[41] Raghu Meka and David Zuckerman. Pseudorandom generators for polynomial threshold functions. SIAM Journal on Computing, 42(3):1275–1301, 2013. doi:10.1137/100811623.
[42] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Simple constructions of linear-depth t-designs and pseudorandom unitaries, 2024. doi:10.48550/arXiv.2404.12647.
[43] A. Morvan et al. Phase transition in random circuit sampling, 2023. arXiv:2304.11119.
[44] Ramis Movassagh. The hardness of random quantum circuits. Nature Physics, 19(11):1719–1724, November 2023. doi:10.1038/s41567-023-02131-2.
[45] Adam Nahum, Jonathan Ruhman, Sagar Vijay, and Jeongwan Haah. Quantum entanglement growth under random unitary dynamics. Physical Review X, 7(3), July 2017. doi:10.1103/physrevx.7.031016.
[46] Adam Nahum, Sagar Vijay, and Jeongwan Haah. Operator spreading in random unitary circuits. Phys. Rev. X, 8:021014, April 2018. doi:10.1103/PhysRevX.8.021014.
[47] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.
[48] Erdős Paul and Alfréd Rényi. On a classical problem of probability theory. Magyar Tud. Akad. Mat. Kutató Int. Közl, 6(1):215–220, 1961.
[49] Lorenzo Piroli, Christoph Sünderhauf, and Xiao-Liang Qi. A random unitary circuit model for black hole evaporation. Journal of High Energy Physics, 2020(4), April 2020. doi:10.1007/jhep04(2020)063.
[50] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth, 2024. doi:10.48550/arXiv.2407.07754.
[51] Henrik Wilming and Albert H. Werner. Lieb-robinson bounds imply locality of interactions. Phys. Rev. B, 105:125101, March 2022. doi:10.1103/PhysRevB.105.125101.
[52] Lisa Yang and Netta Engelhardt. The complexity of learning (pseudo)random dynamics of black holes and other chaotic systems, 2023. arXiv:2302.11013.
[53] Tianci Zhou, Shenglong Xu, Xiao Chen, Andrew Guo, and Brian Swingle. Operator lévy flight: Light cones in chaotic long-range interacting systems. Phys. Rev. Lett., 124:180601, May 2020. doi:10.1103/PhysRevLett.124.180601.

[bib.bib1] [1] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, STOC ’11, pages 333–342, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1993636.1993682.

[bib.bib2] [2] Scott Aaronson and Shih-Han Hung. Certified randomness from quantum supremacy. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 933–944, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585145.

[bib.bib3] [3] Frank Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, October 2019. doi:10.1038/s41586-019-1666-5.

[bib.bib4] [4] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, and Avishay Tal. On certified randomness from fourier sampling or random circuit sampling, 2024. arXiv:2111.14846.

[bib.bib5] [5] Bruno Bertini and Lorenzo Piroli. Scrambling in random unitary circuits: Exact results. Phys. Rev. B, 102:064305, August 2020. doi:10.1103/PhysRevB.102.064305.

[bib.bib6] [6] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6):595–600, April 2018. doi:10.1038/s41567-018-0124-x.

[bib.bib7] [7] Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu. Noise and the frontier of quantum supremacy. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, February 2022. doi:10.1109/focs52979.2021.00127.

[bib.bib8] [8] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159–163, October 2018. doi:10.1038/s41567-018-0318-2.

[bib.bib9] [9] Paolo Braccia, Pablo Bermejo, Lukasz Cincio, and M. Cerezo. Computing exact moments of local random quantum circuits via tensor networks, 2024. arXiv:2403.01706.

[bib.bib10] [10] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Commun. Math. Phys., 346(2):397–434, 2016. doi:10.1007/s00220-016-2706-8.

[bib.bib11] [11] Winton Brown and Omar Fawzi. Scrambling speed of random quantum circuits, 2013. arXiv:1210.6644.

[bib.bib12] [12] Anthony Carbery and James Wright. Distributional and $L^{q}$ norm inequalities for polynomials over convex bodies in $\mathbb{R}^{n}$ . Mathematical Research Letters, 8(3):233–248, 2001. doi:10.4310/mrl.2001.v8.n3.a1.

[bib.bib13] [13] Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão, Jordan Docter, Patrick Hayden, and Michelle Xu. Efficient unitary designs and pseudorandom unitaries from permutations, 2024. doi:10.48550/arXiv.2404.16751.

[bib.bib14] [14] Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, and Patrick Hayden. Efficient unitary t-designs from random sums, 2024. doi:10.48550/arXiv.2402.09335.

[bib.bib15] [15] Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. Incompressibility and spectral gaps of random circuits, 2024. doi:10.48550/arXiv.2406.07478.

[bib.bib16] [16] Chi-Fang Chen and Andrew Lucas. Operator growth bounds from graph theory. Communications in Mathematical Physics, 385(3):1273–1323, July 2021. doi:10.1007/s00220-021-04151-6.

[bib.bib17] [17] Chi-Fang Chen, Andrew Lucas, and Chao Yin. Speed limits and locality in many-body quantum dynamics. Reports on Progress in Physics, 86(11):116001, September 2023. doi:10.1088/1361-6633/acfaae.

[bib.bib18] [18] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão. Random quantum circuits anticoncentrate in log depth. PRX Quantum, 3(1), March 2022. doi:10.1103/prxquantum.3.010333.

[bib.bib19] [19] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A, 80:012304, July 2009. doi:10.1103/PhysRevA.80.012304.

[bib.bib20] [20] Joseph Emerson, Robert Alicki, and Karol Zyczkowski. Scalable noise estimation with random unitary operators. Journal of Optics B: Quantum and Semiclassical Optics, 7, March 2005. doi:10.1088/1464-4266/7/10/021.

[bib.bib21] [21] Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. Effect of non-unital noise on random circuit sampling, 2023. doi:10.48550/arXiv.2306.16659.

[bib.bib22] [22] Matthew P.A. Fisher, Vedika Khemani, Adam Nahum, and Sagar Vijay. Random quantum circuits. Annual Review of Condensed Matter Physics, 14(1):335–379, 2023. doi:10.1146/annurev-conmatphys-031720-030658.

[bib.bib23] [23] Jeongwan Haah, Yunchao Liu, and Xinyu Tan. Efficient approximate unitary designs from random pauli rotations, 2024. doi:10.48550/arXiv.2402.05239.

[bib.bib24] [24] Jonas Haferkamp. Random quantum circuits are approximate unitary $t$ -designs in depth $O\mathopen{}\mathclose{{\left(nt^{5+o(1)}}}\right)$ . Quantum, 6:795, September 2022. doi:10.22331/q-2022-09-08-795.

[bib.bib25] [25] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert. Anticoncentration theorems for schemes showing a quantum speedup. Quantum, 2:65, May 2018. doi:10.22331/q-2018-05-22-65.

[bib.bib26] [26] Dominik Hangleiter and Michael J. Gullans. Bell sampling from quantum circuits. Phys. Rev. Lett., 133:020601, July 2024. doi:10.1103/PhysRevLett.133.020601.

[bib.bib27] [27] Aram W. Harrow, Linghang Kong, Zi-Wen Liu, Saeed Mehraban, and Peter W. Shor. Separation of out-of-time-ordered correlation and entanglement. PRX Quantum, 2:020339, June 2021. doi:10.1103/PRXQuantum.2.020339.

[bib.bib28] [28] Aram W. Harrow and Richard A. Low. Random quantum circuits are approximate 2-designs. Communications in Mathematical Physics, 291(1):257–302, July 2009. doi:10.1007/s00220-009-0873-6.

[bib.bib29] [29] Aram W. Harrow and Saeed Mehraban. Approximate unitary $t$ -designs by short random quantum circuits using nearest-neighbor and long-range gates. Commun. Math. Phys., 401(2):1531–1626, 2023. doi:10.1007/s00220-023-04675-z.

[bib.bib30] [30] Patrick Hayden and John Preskill. Black holes as mirrors: quantum information in random subsystems. Journal of High Energy Physics, 2007(09):120–120, September 2007. doi:10.1088/1126-6708/2007/09/120.

[bib.bib31] [31] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean. Learning shallow quantum circuits. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1343–1351, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649722.

[bib.bib32] [32] Nicholas Hunter-Jones. Unitary designs from statistical mechanics in random quantum circuits, 2019. arXiv:1905.12053.

[bib.bib33] [33] Shao-Kai Jian, Gregory Bentsen, and Brian Swingle. Linear growth of circuit complexity from brownian dynamics, 2022. arXiv:2206.14205.

[bib.bib34] [34] Daniel Kane. A structure theorem for poorly anticoncentrated polynomials of gaussians and applications to the study of polynomial threshold functions. The Annals of Probability, 45(3):1612–1679, 2017. doi:10.1214/16-AOP1097.

[bib.bib35] [35] Zeph Landau and Yunchao Liu. Learning quantum states prepared by shallow circuits in polynomial time, 2024. doi:10.48550/arXiv.2410.23618.

[bib.bib36] [36] Elliott H. Lieb and Derek W. Robinson. The finite group velocity of quantum spin systems. Communications In Mathematical Physics, 28(3):251–257, September 1972. doi:10.1007/BF01645779.

[bib.bib37] [37] Yunchao Liu, Matthew Otten, Roozbeh Bassirianjahromi, Liang Jiang, and Bill Fefferman. Benchmarking near-term quantum computers via random circuit sampling, 2022. arXiv:2105.05232.

[bib.bib38] [38] Shachar Lovett. An elementary proof of anti-concentration of polynomials in gaussian variables. Electronic Colloquium on Computational Complexity (ECCC), 2010. URL: https://eccc.weizmann.ac.il/report/2010/182.

[bib.bib39] [39] Elizabeth S Meckes. The random matrix theory of the classical compact groups, volume 218. Cambridge University Press, 2019. doi:10.1017/9781108303453.

[bib.bib40] [40] Raghu Meka, Oanh Nguyen, and Van Vu. Anti-concentration for polynomials of independent random variables. Theory of Computing, 12(11):1–17, 2016. doi:10.4086/toc.2016.v012a011.

[bib.bib41] [41] Raghu Meka and David Zuckerman. Pseudorandom generators for polynomial threshold functions. SIAM Journal on Computing, 42(3):1275–1301, 2013. doi:10.1137/100811623.

[bib.bib42] [42] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Simple constructions of linear-depth t-designs and pseudorandom unitaries, 2024. doi:10.48550/arXiv.2404.12647.

[bib.bib43] [43] A. Morvan et al. Phase transition in random circuit sampling, 2023. arXiv:2304.11119.

[bib.bib44] [44] Ramis Movassagh. The hardness of random quantum circuits. Nature Physics, 19(11):1719–1724, November 2023. doi:10.1038/s41567-023-02131-2.

[bib.bib45] [45] Adam Nahum, Jonathan Ruhman, Sagar Vijay, and Jeongwan Haah. Quantum entanglement growth under random unitary dynamics. Physical Review X, 7(3), July 2017. doi:10.1103/physrevx.7.031016.

[bib.bib46] [46] Adam Nahum, Sagar Vijay, and Jeongwan Haah. Operator spreading in random unitary circuits. Phys. Rev. X, 8:021014, April 2018. doi:10.1103/PhysRevX.8.021014.

[bib.bib47] [47] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.

[bib.bib48] [48] Erdős Paul and Alfréd Rényi. On a classical problem of probability theory. Magyar Tud. Akad. Mat. Kutató Int. Közl, 6(1):215–220, 1961.

[bib.bib49] [49] Lorenzo Piroli, Christoph Sünderhauf, and Xiao-Liang Qi. A random unitary circuit model for black hole evaporation. Journal of High Energy Physics, 2020(4), April 2020. doi:10.1007/jhep04(2020)063.

[bib.bib50] [50] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth, 2024. doi:10.48550/arXiv.2407.07754.

[bib.bib51] [51] Henrik Wilming and Albert H. Werner. Lieb-robinson bounds imply locality of interactions. Phys. Rev. B, 105:125101, March 2022. doi:10.1103/PhysRevB.105.125101.

[bib.bib52] [52] Lisa Yang and Netta Engelhardt. The complexity of learning (pseudo)random dynamics of black holes and other chaotic systems, 2023. arXiv:2302.11013.

[bib.bib53] [53] Tianci Zhou, Shenglong Xu, Xiao Chen, Andrew Guo, and Brian Swingle. Operator lévy flight: Light cones in chaotic long-range interacting systems. Phys. Rev. Lett., 124:180601, May 2020. doi:10.1103/PhysRevLett.124.180601.

	$\displaystyle\mathopen{}\mathclose{{\left\\|\Upphi_{\mathcal{C}}(\rho)-\Upphi_{% \mathcal{C}}(\rho^{\prime})}}\right\\|_{\mathrm{F}}$	$\displaystyle\geq 2^{-kD/2}\alpha\mathopen{}\mathclose{{\left\\|\rho-\rho^{% \prime}}}\right\\|_{\mathrm{F}}$
		$\displaystyle=2^{-kD/2}\gamma^{1/t}\mathop{\mathbf{E}\mbox{}}\limits[\Uplambda% _{k}^{-t}]^{-D/t}\mathopen{}\mathclose{{\left\\|\rho-\rho^{\prime}}}\right\\|_{% \mathrm{F}}$
		$\displaystyle=(2^{-D}\gamma)^{O_{k}(1)}\mathopen{}\mathclose{{\left\\|\rho-\rho% ^{\prime}}}\right\\|_{\mathrm{F}}.\$

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Theorem 1.

Implications on proving typicality statements.

1.1 Applications

1.1.1 Optimal 2-design lower bounds

Theorem 2.

1.1.2 Testing for depth

Theorem 3.

1.1.3 Learning brickwork random circuits

Theorem 4.

Theorem 5.

1.2 Main Technical Tool: Anti-Concentration for Haar Measure

Theorem 6.

Corollary 7.

▶ Remark 8.

1.3 Related Works

2 Preliminaries

Definition 9.

Definition 10.

Proposition 11.

Lemma 12.

3 Anti-concentration Bound

Theorem 13.

3.1 𝒎=𝟏,𝒏=𝟏

3.2 𝒎=𝟏,𝒏=𝟏, Alternative Distribution

3.3 𝒎=𝟏,𝒏>𝟏

Lemma 14.

Proof.

3.4 𝒎>𝟏,𝒏>𝟏

Lemma 15.

Proof.

Corollary 16.

Proof.

4 Mixing Bound for Random Circuits

Lemma 17.

Proof of Theorem 1.

4.1 Proof of Lemma 17

Proposition 18.

Proposition 19.

Proposition 20.

Proof of Lemma 17.

5 Applications

5.1 Depth Lower Bound for Approximate Designs

Definition 21.

Proof of Theorem 2.

5.2 Depth Test

Theorem 22.

▶ Remark 23.

5.3 Learning Brickwork Random Circuits

5.3.1 Learning the First Gate

Definition 24.

Lemma 25.

Lemma 26.

Theorem 27.

5.3.2 Learning the Circuit with Discretized Distribution

Definition 28.

Lemma 29.

Theorem 30.

Proof.

Theorem 31.

References

$\blacktriangleright$ Remark 8.

3.1 $m=1,n=1$

3.2 $m=1,n=1$ , Alternative Distribution

3.3 $m=1,n>1$

3.4 $m>1,n>1$

$\blacktriangleright$ Remark 23.