More Like this

1. New lower bounds for matrix multiplication and

   https://doi.org/10.1017/fmp.2023.14  

   Conner, Austin ; Harper, Alicia ; Landsberg, J.M. ( January 2023 , Forum of Mathematics, Pi)

   Let$M_{\langle \mathbf {u},\mathbf {v},\mathbf {w}\rangle }\in \mathbb C^{\mathbf {u}\mathbf {v}}{\mathord { \otimes } } \mathbb C^{\mathbf {v}\mathbf {w}}{\mathord { \otimes } } \mathbb C^{\mathbf {w}\mathbf {u}}$denote the matrix multiplication tensor (and write$M_{\langle \mathbf {n} \rangle }=M_{\langle \mathbf {n},\mathbf {n},\mathbf {n}\rangle }$), and let$\operatorname {det}_3\in (\mathbb C^9)^{{\mathord { \otimes } } 3}$denote the determinant polynomial considered as a tensor. For a tensorT, let$\underline {\mathbf {R}}(T)$denote its border rank. We (i) give the first hand-checkable algebraic proof that$\underline {\mathbf {R}}(M_{\langle 2\rangle })=7$, (ii) prove$\underline {\mathbf {R}}(M_{\langle 223\rangle })=10$and$\underline {\mathbf {R}}(M_{\langle 233\rangle })=14$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was$M_{\langle 2\rangle }$, (iii) prove$\underline {\mathbf {R}}( M_{\langle 3\rangle })\geq 17$, (iv) prove$\underline {\mathbf {R}}(\operatorname {det}_3)=17$, improving the previous lower bound of$12$, (v) prove$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.32\mathbf {n}$for all$\mathbf {n}\geq 25$, where previously only$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1$was known, as well as lower bounds for$4\leq \mathbf {n}\leq 25$, and (vi) prove$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.6\mathbf {n}$for all$\mathbf {n} \ge 18$, where previously only$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+2$was known. The last two results are significant for two reasons: (i) they are essentially the first nontrivial lower bounds for tensors in an “unbalanced” ambient space and (ii) they demonstrate that the methods we use (border apolarity) may be applied to sequences of tensors.

   The methods used to obtain the results are new and “nonnatural” in the sense of Razborov and Rudich, in that the results are obtained via an algorithm that cannot be effectively applied to generic tensors. We utilize a new technique, calledborder apolaritydeveloped by Buczyńska and Buczyński in the general context of toric varieties. We apply this technique to develop an algorithm that, given a tensorTand an integerr, in a finite number of steps, either outputs that there is no border rankrdecomposition forTor produces a list of all normalized ideals which could potentially result from a border rank decomposition. The algorithm is effectively implementable whenThas a large symmetry group, in which case it outputs potential decompositions in a natural normal form. The algorithm is based on algebraic geometry and representation theory.

    

   more » « less
2. Provably efficient machine learning for quantum many-body problems

   https://doi.org/10.1126/science.abk3333  

   Huang, Hsin-Yuan ; Kueng, Richard ; Torlai, Giacomo ; Albert, Victor V. ; Preskill, John ( September 2022 , Science)

   INTRODUCTION Solving quantum many-body problems, such as finding ground states of quantum systems, has far-reaching consequences for physics, materials science, and chemistry. Classical computers have facilitated many profound advances in science and technology, but they often struggle to solve such problems. Scalable, fault-tolerant quantum computers will be able to solve a broad array of quantum problems but are unlikely to be available for years to come. Meanwhile, how can we best exploit our powerful classical computers to advance our understanding of complex quantum systems? Recently, classical machine learning (ML) techniques have been adapted to investigate problems in quantum many-body physics. So far, these approaches are mostly heuristic, reflecting the general paucity of rigorous theory in ML. Although they have been shown to be effective in some intermediate-size experiments, these methods are generally not backed by convincing theoretical arguments to ensure good performance. RATIONALE A central question is whether classical ML algorithms can provably outperform non-ML algorithms in challenging quantum many-body problems. We provide a concrete answer by devising and analyzing classical ML algorithms for predicting the properties of ground states of quantum systems. We prove that these ML algorithms can efficiently and accurately predict ground-state properties of gapped local Hamiltonians, after learning from data obtained by measuring other ground states in the same quantum phase of matter. Furthermore, under a widely accepted complexity-theoretic conjecture, we prove that no efficient classical algorithm that does not learn from data can achieve the same prediction guarantee. By generalizing from experimental data, ML algorithms can solve quantum many-body problems that could not be solved efficiently without access to experimental data. RESULTS We consider a family of gapped local quantum Hamiltonians, where the Hamiltonian H ( x ) depends smoothly on m parameters (denoted by x ). The ML algorithm learns from a set of training data consisting of sampled values of x , each accompanied by a classical representation of the ground state of H ( x ). These training data could be obtained from either classical simulations or quantum experiments. During the prediction phase, the ML algorithm predicts a classical representation of ground states for Hamiltonians different from those in the training data; ground-state properties can then be estimated using the predicted classical representation. Specifically, our classical ML algorithm predicts expectation values of products of local observables in the ground state, with a small error when averaged over the value of x . The run time of the algorithm and the amount of training data required both scale polynomially in m and linearly in the size of the quantum system. Our proof of this result builds on recent developments in quantum information theory, computational learning theory, and condensed matter theory. Furthermore, under the widely accepted conjecture that nondeterministic polynomial-time (NP)–complete problems cannot be solved in randomized polynomial time, we prove that no polynomial-time classical algorithm that does not learn from data can match the prediction performance achieved by the ML algorithm. In a related contribution using similar proof techniques, we show that classical ML algorithms can efficiently learn how to classify quantum phases of matter. In this scenario, the training data consist of classical representations of quantum states, where each state carries a label indicating whether it belongs to phase A or phase B . The ML algorithm then predicts the phase label for quantum states that were not encountered during training. The classical ML algorithm not only classifies phases accurately, but also constructs an explicit classifying function. Numerical experiments verify that our proposed ML algorithms work well in a variety of scenarios, including Rydberg atom systems, two-dimensional random Heisenberg models, symmetry-protected topological phases, and topologically ordered phases. CONCLUSION We have rigorously established that classical ML algorithms, informed by data collected in physical experiments, can effectively address some quantum many-body problems. These rigorous results boost our hopes that classical ML trained on experimental data can solve practical problems in chemistry and materials science that would be too hard to solve using classical processing alone. Our arguments build on the concept of a succinct classical representation of quantum states derived from randomized Pauli measurements. Although some quantum devices lack the local control needed to perform such measurements, we expect that other classical representations could be exploited by classical ML with similarly powerful results. How can we make use of accessible measurement data to predict properties reliably? Answering such questions will expand the reach of near-term quantum platforms. Classical algorithms for quantum many-body problems. Classical ML algorithms learn from training data, obtained from either classical simulations or quantum experiments. Then, the ML algorithm produces a classical representation for the ground state of a physical system that was not encountered during training. Classical algorithms that do not learn from data may require substantially longer computation time to achieve the same task. 

   more » « less
3. Landscape complexity beyond invariance and the elastic manifold

   https://doi.org/10.1002/cpa.22146  

   Ben Arous, Gérard ; Bourgade, Paul ; McKenna, Benjamin ( September 2023 , Communications on Pure and Applied Mathematics)

   This paper characterizes the annealed, topological complexity (both of total critical points and of local minima) of the elastic manifold. This classical model of a disordered elastic system captures point configurations with self‐interactions in a random medium. We establish the simple versus glassy phase diagram in the model parameters, with these phases separated by a physical boundary known as the Larkin mass, confirming formulas of Fyodorov and Le Doussal. One essential, dynamical, step of the proof also applies to a general signal‐to‐noise model of soft spins in an anisotropic well, for which we prove a negative‐second‐moment threshold distinguishing positive from zero complexity. A universal near‐critical behavior appears within this phase portrait, namely quadratic near‐critical vanishing of the complexity of total critical points, and cubic near‐critical vanishing of the complexity of local minima. These two models serve as a paradigm of complexity calculations for Gaussian landscapes exhibiting few distributional symmetries, that is, beyond the invariant setting. The two main inputs for the proof are determinant asymptotics for non‐invariant random matrices from our companion paper (Ben Arous, Bourgade, McKenna 2022), and the atypical convexity and integrability of the limiting variational problems.

    

   more » « less
4. A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits

   https://doi.org/10.1145/3543685  

   Volk, Ben Lee ; Kumar, Mrinal ( June 2022 , ACM Transactions on Computation Theory)

   We show that there is an equation of degree at most poly( n ) for the (Zariski closure of the) set of the non-rigid matrices: That is, we show that for every large enough field 𝔽, there is a non-zero n 2 -variate polynomial P ε 𝔽[ x 1, 1 , ..., x n, n ] of degree at most poly( n ) such that every matrix M that can be written as a sum of a matrix of rank at most n /100 and a matrix of sparsity at most n 2 /100 satisfies P(M) = 0. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer, and Landsberg [ 9 ] and improves the best upper bound known for this problem down from exp ( n 2 ) [ 9 , 12 ] to poly( n ). We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices M such that the linear transformation represented by M can be computed by an algebraic circuit with at most n 2 /200 edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [ 21 ] to construct low-degree “universal” maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low-degree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [ 11 ]. 

   more » « less
5. Pseudodeterminism: promises and lowerbounds

   https://doi.org/10.1145/3519935.3520043  

   Dixon, Peter ; Pavan, A. ; Woude, Jason Vander ; Vinodchandran, N. V. ( July 2022 , Symposium on Theory of Computing (STOC))

   Stefano Leonardi and Anupam Gupta (Ed.)

   A probabilistic algorithm A is pseudodeterministic if, on every input, there exists a canonical value that is output with high probability. If the algorithm outputs one of k canonical values with high probability, then it is called a k-pseudodeterministic algorithm. In the study of pseudodeterminism, the Acceptance Probability Estimation Problem (APEP), which is to additively approximate the acceptance probability of a Boolean circuit, is emerging as a central computational problem. This problem admits a 2-pseudodeterministic algorithm. Recently, it was shown that a pseudodeterministic algorithm for this problem would imply that any multi-valued function that admits a k-pseudodeterministic algorithm for a constant k (including approximation algorithms) also admits a pseudodeterministic algorithm (Dixon, Pavan, Vinodchandran; ITCS 2021). The contribution of the present work is two-fold. First, as our main conceptual contribution, we establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally related to the gap between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: APEP has a pseudodeterministic approximation algorithm if and only if every promise problem in PromiseBPP has a solution in BPP. A conceptual interpretation of this equivalence is that the algorithmic gap between 2-pseudodeterminism and pseudodeterminism is equivalent to the gap between PromiseBPP and BPP. Based on this connection, we show that designing pseudodeterministic algorithms for APEP leads to the solution of some open problems in complexity theory, including new Boolean circuit lower bounds. This equivalence also explains how multi-pseudodeterminism is connected to problems in SearchBPP. In particular, we show that if APEP has a pseudodeterministic algorithm, then every problem that admits a k(n)-pseudodeterministic algorithm (for any polynomial k) is in SearchBPP and admits a pseudodeterministic algorithm. Motivated by this connection, we also explore its connection to probabilistic search problems and establish that APEP is complete for certain notions of search problems in the context of pseudodeterminism. Our second contribution is establishing query complexity lower bounds for multi-pseudodeterministic computations. We prove that for every k ≥ 1, there exists a problem whose (k+1)-pseudodeterministic query complexity, in the uniform query model, is O(1) but has a k-pseudodeterministic query complexity of Ω(n), even in the more general nonadaptive query model. A key contribution of this part of the work is the utilization of Sperner’s lemma in establishing query complexity lower bounds. 

   more » « less