We prove that
We prove multi-point correlation bounds in
- NSF-PAR ID:
- 10490488
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Communications in Mathematical Physics
- Volume:
- 405
- Issue:
- 2
- ISSN:
- 0010-3616
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract -depth local random quantum circuits with two qudit nearest-neighbor gates on a$${{\,\textrm{poly}\,}}(t) \cdot 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$$ . 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$$ ) is infinite and that certain counting problems are$${{\,\mathrm{\textsf{PH}}\,}}$$ -hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth 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 “anti-concentration”, meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear 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 two-dimensional 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}}$$ depth suffices for anti-concentration. The proof is based on a previous construction of$$O(\sqrt{n})$$ t -designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasi-orthogonality 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 anti-concentration and to establish equivalence between these various norms for low-depth circuits. For random circuits with long-range gates, we use different methods to show that anti-concentration happens at circuit size corresponding to depth$$O(n\ln ^2 n)$$ . We also show a lower bound of$$O(\ln ^3 n)$$ for the size of such circuit in this case. We also prove that anti-concentration is possible in depth$$\Omega (n \ln n)$$ (size$$O(\ln n \ln \ln n)$$ ) using a different model.$$O(n \ln n \ln \ln n)$$ -
Abstract Let us fix a prime
p and a homogeneous system ofm linear equations for$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$ with coefficients$$j=1,\dots ,m$$ . Suppose that$$a_{j,i}\in \mathbb {F}_p$$ , that$$k\ge 3m$$ for$$a_{j,1}+\dots +a_{j,k}=0$$ and that every$$j=1,\dots ,m$$ minor of the$$m\times m$$ matrix$$m\times k$$ is non-singular. Then we prove that for any (large)$$(a_{j,i})_{j,i}$$ n , any subset of size$$A\subseteq \mathbb {F}_p^n$$ contains a solution$$|A|> C\cdot \Gamma ^n$$ to the given system of equations such that the vectors$$(x_1,\dots ,x_k)\in A^k$$ are all distinct. Here,$$x_1,\dots ,x_k\in A$$ C and are constants only depending on$$\Gamma $$ p ,m andk such that . The crucial point here is the condition for the vectors$$\Gamma in the solution$$x_1,\dots ,x_k$$ to be distinct. If we relax this condition and only demand that$$(x_1,\dots ,x_k)\in A^k$$ are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments.$$x_1,\dots ,x_k$$ -
Abstract Approximate integer programming is the following: For a given convex body
, either determine whether$$K \subseteq {\mathbb {R}}^n$$ is empty, or find an integer point in the convex body$$K \cap {\mathbb {Z}}^n$$ which is$$2\cdot (K - c) +c$$ K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time while the fastest known methods for exact integer programming run in time$$2^{O(n)}$$ . So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$2^{O(n)} \cdot n^n$$ can be found in time$$x^* \in (K \cap {\mathbb {Z}}^n)$$ , provided that the$$2^{O(n)}$$ remainders of each component for some arbitrarily fixed$$x_i^* \mod \ell $$ of$$\ell \ge 5(n+1)$$ are given. The algorithm is based on a$$x^*$$ cutting-plane technique , iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a new$$2^{O(n)}n^n$$ asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form . Such a problem can be reduced to the solution of$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ approximate integer programming problems. This implies, for example that$$\prod _i O(\log u_i +1)$$ knapsack orsubset-sum problems withpolynomial variable range can be solved in time$$0 \le x_i \le p(n)$$ . For these problems, the best running time so far was$$(\log n)^{O(n)}$$ .$$n^n \cdot 2^{O(n)}$$ -
Abstract We construct an example of a group
for a finite abelian group$$G = \mathbb {Z}^2 \times G_0$$ , a subset$$G_0$$ E of , and two finite subsets$$G_0$$ of$$F_1,F_2$$ G , such that it is undecidable in ZFC whether can be tiled by translations of$$\mathbb {Z}^2\times E$$ . In particular, this implies that this tiling problem is$$F_1,F_2$$ aperiodic , in the sense that (in the standard universe of ZFC) there exist translational tilings ofE by the tiles , but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in$$F_1,F_2$$ ). A similar construction also applies for$$\mathbb {Z}^2$$ for sufficiently large$$G=\mathbb {Z}^d$$ d . If one allows the group to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile$$G_0$$ F . The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles. -
Abstract Given a suitable solution
V (t ,x ) to the Korteweg–de Vries equation on the real line, we prove global well-posedness for initial data . Our conditions on$$u(0,x) \in V(0,x) + H^{-1}(\mathbb {R})$$ V do include regularity but do not impose any assumptions on spatial asymptotics. We show that periodic profiles satisfy our hypotheses. In particular, we can treat localized perturbations of the much-studied periodic traveling wave solutions (cnoidal waves) of KdV. In the companion paper Laurens (Nonlinearity. 35(1):343–387, 2022.$$V(0,x)\in H^5(\mathbb {R}/\mathbb {Z})$$ https://doi.org/10.1088/1361-6544/ac37f5 ) we show that smooth step-like initial data also satisfy our hypotheses. We employ the method of commuting flows introduced in Killip and Vişan (Ann. Math. (2) 190(1):249–305, 2019.https://doi.org/10.4007/annals.2019.190.1.4 ) where . In that setting, it is known that$$V\equiv 0$$ is sharp in the class of$$H^{-1}(\mathbb {R})$$ spaces.$$H^s(\mathbb {R})$$