We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gatelevel error with probability close to one. We model noise by adding a pair of weak, unital, singlequbit noise channels after each twoqubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution
We present the first unquenched latticeQCD calculation of the form factors for the decay
 Award ID(s):
 2013064
 NSFPAR ID:
 10385938
 Publisher / Repository:
 Springer Science + Business Media
 Date Published:
 Journal Name:
 The European Physical Journal C
 Volume:
 82
 Issue:
 12
 ISSN:
 14346052
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract and the corresponding noiseless output distribution$$p_{\text {noisy}}$$ ${p}_{\text{noisy}}$ shrink exponentially with the expected number of gatelevel errors. Specifically, the linear crossentropy benchmark$$p_{\text {ideal}}$$ ${p}_{\text{ideal}}$F that measures this correlation behaves as , where$$F=\text {exp}(2s\epsilon \pm O(s\epsilon ^2))$$ $F=\text{exp}(2s\u03f5\pm O\left(s{\u03f5}^{2}\right))$ is the probability of error per circuit location and$$\epsilon $$ $\u03f5$s is the number of twoqubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution and the uniform distribution$$p_{\text {noisy}}$$ ${p}_{\text{noisy}}$ decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {unif}}$$ ${p}_{\text{unif}}$ . In other words, although at least one local error occurs with probability$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1F)p_{\text {unif}}$$ ${p}_{\text{noisy}}\approx F{p}_{\text{ideal}}+(1F){p}_{\text{unif}}$ , the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$1F$$ $1F$ . Thus, the “whitenoise approximation” is meaningful when$$O(F\epsilon \sqrt{s})$$ $O\left(F\u03f5\sqrt{s}\right)$ , a quadratically weaker condition than the$$\epsilon \sqrt{s} \ll 1$$ $\u03f5\sqrt{s}\ll 1$ requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$\epsilon s\ll 1$$ $\u03f5s\ll 1$ , which corresponds to only$$s \ge \Omega (n\log (n))$$ $s\ge \Omega (nlog(n\left)\right)$logarithmic depth circuits, and if, additionally, the inverse error rate satisfies , which is needed to ensure errors are scrambled faster than$$\epsilon ^{1} \ge {\tilde{\Omega }}(n)$$ ${\u03f5}^{1}\ge \stackrel{~}{\Omega}\left(n\right)$F decays. The whitenoise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexitytheoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from secondmoment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds. 
Abstract It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.
arXiv:2010.09793 ) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators associated to a domain$$L_{\beta ,\gamma } = {\text {div}}D^{d+1+\gamma n} \nabla $$ ${L}_{\beta ,\gamma}=\text{div}{D}^{d+1+\gamma n}\nabla $ with a uniformly rectifiable boundary$$\Omega \subset {\mathbb {R}}^n$$ $\Omega \subset {R}^{n}$ of dimension$$\Gamma $$ $\Gamma $ , the now usual distance to the boundary$$d < n1$$ $d<n1$ given by$$D = D_\beta $$ $D={D}_{\beta}$ for$$D_\beta (X)^{\beta } = \int _{\Gamma } Xy^{d\beta } d\sigma (y)$$ ${D}_{\beta}{\left(X\right)}^{\beta}={\int}_{\Gamma}{Xy}^{d\beta}d\sigma \left(y\right)$ , where$$X \in \Omega $$ $X\in \Omega $ and$$\beta >0$$ $\beta >0$ . In this paper we show that the Green function$$\gamma \in (1,1)$$ $\gamma \in (1,1)$G for , with pole at infinity, is well approximated by multiples of$$L_{\beta ,\gamma }$$ ${L}_{\beta ,\gamma}$ , in the sense that the function$$D^{1\gamma }$$ ${D}^{1\gamma}$ satisfies a Carleson measure estimate on$$\big  D\nabla \big (\ln \big ( \frac{G}{D^{1\gamma }} \big )\big )\big ^2$$ $D\nabla (ln(\frac{G}{{D}^{1\gamma}})){}^{2}$ . We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear).$$\Omega $$ $\Omega $ 
Abstract We prove that
depth local random quantum circuits with two qudit nearestneighbor gates on a$${{\,\textrm{poly}\,}}(t) \cdot n^{1/D}$$ $\phantom{\rule{0ex}{0ex}}\text{poly}\phantom{\rule{0ex}{0ex}}\left(t\right)\xb7{n}^{1/D}$D dimensional lattice withn qudits are approximatet designs in various measures. These include the “monomial” measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was due to Brandão–Harrow–Horodecki (Commun Math Phys 346(2):397–434, 2016) for$${{\,\textrm{poly}\,}}(t)\cdot n$$ $\phantom{\rule{0ex}{0ex}}\text{poly}\phantom{\rule{0ex}{0ex}}\left(t\right)\xb7n$ . We also improve the “scrambling” and “decoupling” bounds for spatially local random circuits due to Brown and Fawzi (Scrambling speed of random quantum circuits, 2012). One consequence of our result is that assuming the polynomial hierarchy ($$D=1$$ $D=1$ ) is infinite and that certain counting problems are$${{\,\mathrm{\textsf{PH}}\,}}$$ $\phantom{\rule{0ex}{0ex}}\mathrm{PH}\phantom{\rule{0ex}{0ex}}$ hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constantdepth quantum circuits was known to be hard for classical computers under these assumptions. However the standard strategy for extending this hardness result to approximate sampling requires the quantum circuits to have a property called “anticoncentration”, meaning roughly that the output has nearmaximal entropy. Unitary 2designs have the desired anticoncentration property. Our result improves the required depth for this level of anticoncentration from linear depth to a sublinear value, depending on the geometry of the interactions. This is relevant to a recent experiment by the Google Quantum AI group to perform such a sampling task with 53 qubits on a twodimensional lattice (Arute in Nature 574(7779):505–510, 2019; Boixo et al. in Nate Phys 14(6):595–600, 2018) (and related experiments by USTC), and confirms their conjecture that$$\#{\textsf{P}}$$ $\#P$ depth suffices for anticoncentration. The proof is based on a previous construction of$$O(\sqrt{n})$$ $O\left(\sqrt{n}\right)$t designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasiorthogonality of permutation operators developed by Brandão et al. (2016). Different versions of the approximate design condition correspond to different norms, and part of our contribution is to introduce the norm corresponding to anticoncentration and to establish equivalence between these various norms for lowdepth circuits. For random circuits with longrange gates, we use different methods to show that anticoncentration happens at circuit size corresponding to depth$$O(n\ln ^2 n)$$ $O\left(n{ln}^{2}n\right)$ . We also show a lower bound of$$O(\ln ^3 n)$$ $O\left({ln}^{3}n\right)$ for the size of such circuit in this case. We also prove that anticoncentration is possible in depth$$\Omega (n \ln n)$$ $\Omega (nlnn)$ (size$$O(\ln n \ln \ln n)$$ $O(lnnlnlnn)$ ) using a different model.$$O(n \ln n \ln \ln n)$$ $O(nlnnlnlnn)$ 
Abstract We introduce a family of Finsler metrics, called the
Fisher–Rao metrics$$L^p$$ ${L}^{p}$ , for$$F_p$$ ${F}_{p}$ , which generalizes the classical Fisher–Rao metric$$p\in (1,\infty )$$ $p\in (1,\infty )$ , both on the space of densities$$F_2$$ ${F}_{2}$ and probability densities$${\text {Dens}}_+(M)$$ ${\text{Dens}}_{+}\left(M\right)$ . We then study their relations to the Amari–C̆encov$${\text {Prob}}(M)$$ $\text{Prob}\left(M\right)$ connections$$\alpha $$ $\alpha $ from information geometry: on$$\nabla ^{(\alpha )}$$ ${\nabla}^{\left(\alpha \right)}$ , the geodesic equations of$${\text {Dens}}_+(M)$$ ${\text{Dens}}_{+}\left(M\right)$ and$$F_p$$ ${F}_{p}$ coincide, for$$\nabla ^{(\alpha )}$$ ${\nabla}^{\left(\alpha \right)}$ . Both are pullbacks of canonical constructions on$$p = 2/(1\alpha )$$ $p=2/(1\alpha )$ , in which geodesics are simply straight lines. In particular, this gives a new variational interpretation of$$L^p(M)$$ ${L}^{p}\left(M\right)$ geodesics as being energy minimizing curves. On$$\alpha $$ $\alpha $ , the$${\text {Prob}}(M)$$ $\text{Prob}\left(M\right)$ and$$F_p$$ ${F}_{p}$ geodesics can still be thought as pullbacks of natural operations on the unit sphere in$$\nabla ^{(\alpha )}$$ ${\nabla}^{\left(\alpha \right)}$ , but in this case they no longer coincide unless$$L^p(M)$$ ${L}^{p}\left(M\right)$ . Using this transformation, we solve the geodesic equation of the$$p=2$$ $p=2$ connection by showing that the geodesic are pullbacks of projections of straight lines onto the unit sphere, and they always cease to exists after finite time when they leave the positive part of the sphere. This unveils the geometric structure of solutions to the generalized Proudman–Johnson equations, and generalizes them to higher dimensions. In addition, we calculate the associate tensors of$$\alpha $$ $\alpha $ , and study their relation to$$F_p$$ ${F}_{p}$ .$$\nabla ^{(\alpha )}$$ ${\nabla}^{\left(\alpha \right)}$ 
Abstract We introduce tools from discrete convexity theory and polyhedral geometry into the theory of West’s stacksorting map
s . Associated to each permutation is a particular set$$\pi $$ $\pi $ of integer compositions that appears in a formula for the fertility of$$\mathcal V(\pi )$$ $V\left(\pi \right)$ , which is defined to be$$\pi $$ $\pi $ . These compositions also feature prominently in more general formulas involving families of colored binary plane trees called$$s^{1}(\pi )$$ ${s}^{1}\left(\pi \right)$troupes and in a formula that converts from free to classical cumulants in noncommutative probability theory. We show that is a transversal discrete polymatroid when it is nonempty. We define the$$\mathcal V(\pi )$$ $V\left(\pi \right)$fertilitope of to be the convex hull of$$\pi $$ $\pi $ , and we prove a surprisingly simple characterization of fertilitopes as nestohedra arising from full binary plane trees. Using known facts about nestohedra, we provide a procedure for describing the structure of the fertilitope of$$\mathcal V(\pi )$$ $V\left(\pi \right)$ directly from$$\pi $$ $\pi $ using BousquetMélou’s notion of the canonical tree of$$\pi $$ $\pi $ . As a byproduct, we obtain a new combinatorial cumulant conversion formula in terms of generalizations of canonical trees that we call$$\pi $$ $\pi $quasicanonical trees . We also apply our results on fertilitopes to study combinatorial properties of the stacksorting map. In particular, we show that the set of fertility numbers has density 1, and we determine all infertility numbers of size at most 126. Finally, we reformulate the conjecture that is always realrooted in terms of nestohedra, and we propose natural ways in which this new version of the conjecture could be extended.$$\sum _{\sigma \in s^{1}(\pi )}x^{\textrm{des}(\sigma )+1}$$ ${\sum}_{\sigma \in {s}^{1}\left(\pi \right)}{x}^{\text{des}\left(\sigma \right)+1}$