Institute for Pure & Applied Mathematics (IPAM)
Steve Cowley - Multi-scale Plasma Turbulence — the key to fusion power - IPAM at UCLA
updated
Abstract: Quantum low-density parity-check (qLDPC) codes can achieve high encoding rates and good code distance scaling, providing a promising route to low-overhead fault-tolerant quantum computing. However, the long-range connectivity required to implement such codes makes their physical realization challenging. Here, we propose a hardware-efficient scheme to perform fault-tolerant quantum computation with high-rate qLDPC codes on reconfigurable atom arrays, directly compatible with recently demonstrated experimental capabilities. Our approach utilizes the product structure inherent in many qLDPC codes to implement the non-local syndrome extraction circuit via atom rearrangement, resulting in effectively constant overhead in practically relevant regimes. We prove the fault tolerance of these protocols, perform circuit-level simulations of memory and logical operations with these codes, and find that our qLDPC-based architecture starts to outperform the surface code with as few as several hundred physical qubits at a realistic physical error rate of 0.1%. We further find that less than 3000 physical qubits are sufficient to obtain over an order of magnitude qubit savings compared to the surface code, and quantum algorithms involving thousands of logical qubits can be performed using less than 100k physical qubits. Our work paves the way for explorations of low-overhead quantum computing with qLDPC codes at a practical scale, based on current experimental technologies.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: We argue that the chiral U(1)A_ symmetry of a Weyl fermion cannot be implemented by a shallow depth quantum circuit operation in a fermionic lattice Hamiltonian model with finite dimensional onsite Hilbert spaces. We also extend this result to discrete Z_2N subgroups of U(1)_A, in which case we show that for N_f Weyl fermions of the same helicity, this group action cannot be implemented with shallow depth circuits when N_f is not an integer multiple of 2N.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: In this talk I will present recent results about the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology. In arXiv:2209.11793 we showed that this decision problem is QMA1-hard. Moreover, we showed that a version of the problem satisfying a suitable promise is contained in QMA. This suggests that the seemingly classical problem may in fact be quantum mechanical. In fact, we were able to significantly strengthen this by showing that the problem remains QMA1-hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and homological algebra, and is inspired by a link with supersymmetric quantum mechanics. In this talk I will focus on how the link with supersymmetry inspired the result, and explain the intuition behind the proof.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: "Analogue" Hamiltonian simulation involves engineering a Hamiltonian of interest in the laboratory and studying its properties experimentally. Large-scale Hamiltonian simulation experiments have been carried out in optical lattices, ion traps and other systems for two decades. Despite this, the theoretical basis for Hamiltonian simulation is surprisingly sparse. Even a precise definition of what it means to simulate a Hamiltonian was lacking.
AdS/CFT duality postulates that quantum gravity in a d-dimensional anti-de-Sitter bulk space is equivalent to a strongly interacting field theory on its d-1 dimensional boundary. Recently, connections between AdS/CFT duality and quantum error-correcting codes have led (amongst other things) to tensor network toy models that capture important aspects of this holographic duality. However, these toy models struggle to encompass dualities between bulk and boundary energy scales and dynamics.
On the face of it, these two topics seem to have nothing whatsoever to do with one another.
In this talk, I will explain how we put analogue Hamiltonian simulation on a rigorous theoretical footing, by drawing on techniques from Hamiltonian complexity theory and Jordan algebras. I will show how this proved far more fruitful than a mere mathematical tidying-up exercise, leading to the discovery of universal quantum Hamiltonians [Science, 351:6 278, p.1180, 2016], [Proc. Natl. Acad. Sci. 115:38 p.9497, 2018]. And I will explain how this new Hamiltonian simulation formalism allowed us to extend the toy models of AdS/CFT to encompass energy scales, dynamics, and even (toy models of) black hole formation [J. High Energy Phys 2019:17; J. High Energy Phys 2022:52]. Finally, I will also discuss the significant limitations of tensor networks as toy models of AdS/CFT duality, and what these results suggest about possible ways forward.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract:Last year, Anshu, Breuckmann, and I published a proof of the NLTS conjecture based on recent developments in quantum error-correcting codes. That result demonstrates the existence of robust entanglement even at low temperatures. Our motivation for studying NLTS was that it is a necessary precursor for the quantum PCP conjecture.
In this talk, I’ll speak about why our first construction of NLTS is based on codes and what I believe are the appropriate next questions to tackle for the quantum PCP conjecture. I’ll discuss the connections of these questions to other interesting problems in quantum complexity theory.
This talk will be math-light and intuition-heavy with a particular emphasis on identifying key challenges.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: The surface code is the most popular quantum error correction code for the design of large-scale fault-tolerant quantum computers. However, it leads to a large overhead because each logical qubit is encoded into hundreds of physical qubits. Quantum LDPC codes could lead to a significant reduction of the qubit count. In this talk, I will discuss the decoding problem for these codes. I will describe a fast decoder for the correction of erasures with hypergraph product codes, which form one of the most popular families of quantum LDPC codes.
Based on joint work with Nicholas Connolly, Vivien Londe and Anthony Leverrier. (arxiv:2208.01002)
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: In this talk I will introduce a construction that takes in a stabilizer code and spits out a three dimensional topological code with related code parameters. The output codes have the special structure of being topological defect networks formed by layers of surface code joined along one dimensional junctions, with a maximum stabilizer check weight of six. When the input is a family of good low density parity check codes, the output is a three dimensional topological code with optimal scaling code parameters and a polynomial energy barrier.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: Sipser-Spielman expander codes are a variant of Tanner codes defined on expander graphs by placing code bits on edges and assigning a small linear code with sufficiently large distance to each vertex, constraining the bits on the connected edges. Expander codes are essential in coding theory since they provide explicit families of asymptotically good classical LDPC codes with very simple linear time decoding. Recent constructions of asymptotically good classical LTCs and qLDPC codes have motivated the study of generalizations of Sipser-Spielman codes defined on high-dimensional expanders (HDXs) instead of expander graphs. Toward this goal, it was proposed recently by several researchers to extend the theory of simplicial HDXs over GF(2) to a much more general context of high-dimensional cell complexes (simplicial, cubical, polyhedral, etc.) with arbitrary local systems of abelian groups attached to them. Such objects, also known as cellular sheaves, have been studied in algebraic topology since 1960s and have found many interesting applications in computer science and coding theory in the last decade. By replacing the standard Hamming weight, counting the non-zero coefficients over GF(2), with the block Hamming weight, counting the non-zero coefficients over abelian groups one can naturally extend all the standard definitions from the theory of simplicial HDXs over GF(2) (local minimality, coboundary expansion, Cheeger constants, etc.) to the general context of cellular sheaves. In this talk, I plan to focus on the coboundary expansion in the links of products of expander codes and its pivotal role in the constructions of good LTCs and qLDPC codes. The talk is based on the joint recent works with Gleb Kalachev.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: Topological qubits promise a path towards scalable, fault-tolerant quantum computation. In this talk, I will first introduce the tetron qubit, a variant of topological qubits built on Majorana zero modes in semiconductor-superconductor heterostructures. I will then describe how an array of such tetrons and a natural set of measurement-based operations on them can be used to implement scalable error correction, and review recent progress on codes that are tailored towards such an architecture.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: Toric code, an exactly solvable topological model, has a simple spectrum. However, it was recently proposed that the excitations in 3+1D toric code form a nontrivial higher-category structure. In this talk, we attempt to understand equivalence classes of topological excitations from a unitary perspective. We start from a particular defect called the Cheshire string -- a condensate line of the point charge excitations. We show that to create a Cheshire string, one needs the Sequential Quantum Circuit -- a linear depth circuit that acts sequentially along the length of the string. Once a Cheshire string is created, its deformation, movement, and fusion can be realized by finite depths circuits. Quantum circuits hence provide a way to define equivalence classes of gapped topological defects, potentially giving rise to an operational meaning of the higher category description of topological orders in 3+1D or higher.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: The space of all global unitaries that has lightcones displays an interesting topology, which leads to study of so-called quantum cellular automata. Connected components of this space correspond to local unitary circuits, and the existence of distinct connected components has been found and conjectured. I am going to discuss that a class of local measurement circuits, which includes those of Floquet codes, induce a strictly larger class of locality-preserving unitaries than that of local unitary circuits.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: I'll explain, through examples, how quantum information works in parameter families. Join work with Matt Hastings.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: When quantum computers were first discovered, it wasn’t clear that they could ever become practical, because it looked like it was impossible to correct errors on them. This was due to a theorems of quantum theory: the Heisenberg Uncertain Principle, which says that any measurement of a quantum system unavoidably changes the quantum state of the system. Thus, to figure out what the error is (so that you can correct it), you need to measure the system, which will inevitably disrupt the computation. This reasoning actually doesn’t hold, and it is possible to design quantum error correcting codes that can be used to make quantum computers fault-tolerant. We will survey the early developments of these fault-tolerant techniques.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: We define a map from an arbitrary quantum circuit to a local Hamiltonian whose ground state encodes the quantum computation. All previous maps relied on the Feynman-Kitaev construction, which introduces an ancillary `clock register' to track the computational steps. Our construction, on the other hand, relies on injective tensor networks with associated parent Hamiltonians, avoiding the introduction of a clock register. This comes at the cost of the ground state containing only a noisy version of the quantum computation, with independent stochastic noise. We can remedy this - making our construction robust - by using quantum fault tolerance. In addition to the stochastic noise, we show that any state with energy density exponentially small in the circuit depth encodes a noisy version of the quantum computation with adversarial noise. We also show that any `combinatorial state' with energy density polynomially small in depth encodes the quantum computation with adversarial noise. This serves as evidence that any state with energy density polynomially small in depth has a similar property. As an application, we show that contracting injective tensor networks to additive error is BQP-hard. We also discuss the implication of our construction to the quantum PCP conjecture, combining with an observation that QMA verification can be done in logarithmic depth.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: One framework for Hastings-Haah floquet codes is via loops in the space of gapped Hamiltonians for the toric code (arxiv 2203.11137). This raised an interesting question about the homotopy type of moduli spaces of topological theories. I will discuss some progress towards a conjectured picture of the homotopy type of such moduli spaces in a joint work with Po-shen Hsin (arxiv 2211.16535).
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: I will introduce a new class of quantum error correcting codes that can be used to describe the large-N limit of a sequence of quantum theories. The main interest is in studying the large-N limit of quantum field theories with a gravitational dual, where expected features of the gravitational theory emerge from the quantum error correcting code. I will prove various asymptotic versions of well known operator algebra error correcting results, where arbitrary hyperfinite von Neumann algebras can live on the code. This includes an asymptotic information disturbance tradeoff theorem as well as asymptotic constraints on information theoretic quantities such as relative entropy and mutual information.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: Research in quantum computing has offered many new physical insights and a potential to exponentially increase the computational power that can be harnessed to solve important problems in science and technology. The largest fundamental barrier to building a scalable quantum computer is errors caused by decoherence. Topological quantum computing overcomes this barrier by exploiting topological materials which, by their nature, limit errors. In this talk, I will discuss how to engineer topological superconductors supporting Majorana zero-energy modes at the interface of a conventional superconductor (Aluminum) and a semiconductor with spin-orbit interaction (Indium Arsenide). I will present recent results by the Microsoft Quantum team consistent with the emergence of topological superconductivity in proximitized semiconductor nanowires. Finally, I will discuss a proposal for scalable quantum computing involving topological qubits which comprise of superconducting islands in a Coulomb blockade regime hosting aggregates of four or more Majorana zero modes.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: I will discuss the factoring of primes and survey other discoveries in quantum computing—and offer recollections of my role in them.
Shortly after quantum mechanics was first formulated around 1930, the strangeness of the theory became evident. It took over 50 years, however, for people to realize just how pervasive its strangeness was.
Now, we know that information theory, the theory of computation, and the theory of cryptography all change substantially when we account for quantum mechanics. This strangeness can be used to accomplish tasks with quantum information processing that are not possible classically.
One example—the one that really drew attention to this phenomenon—was my discovery that quantum computers can factor large numbers into primes in manageable time frames, something that digital computers would take an inordinate amount of time to do.
The rapid factorization is only one example of the many strange impacts of quantum mechanics. We have discovered that the theory of information transmission changes substantially when information is transmitted over quantum channels rather than classical ones, as well as the existence of cryptographic protocols that use quantum information to perform tasks that are impossible classically.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: We propose a new model of quantum computation comprised of low-weight measurement sequences that simultaneously encode logical information, enable error correction, and apply logical gates. These measurement sequences constitute a new class of quantum error-correcting codes generalizing Floquet codes, which we call dynamic automorphism codes. We construct an explicit example, the dynamic automorphism color code, which is assembled from short measurement sequences that can realize all 72 automorphisms of the 2D color code. On a stack of N triangular patches, the dynamic automorphism color code encodes N logical qubits and can implement the full logical Clifford group by a sequence of two- and, more rarely, three-qubit Pauli measurements. We also make the first step towards universal quantum computation with dynamic automorphism codes by introducing a 3D dynamic automorphism color code and showing that a non-Clifford logical gate can be realized by adaptive two-qubit measurements.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: Error correction is needed because of the noisy nature of quantum computers. I will talk about different noise models usually described by channels. This will include a brief introduction to Lindbladians which can be used for single bit noise models and collaborative noise. Joint work with Y. Chen (collaborative) and Li, Gao, LaRacuente (Return time estimates).
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: Using bosonization, which maps fermions coupled to a Z_2 gauge field to a qubit system, we give a simple form for the non-trivial 3-fermion quantum cellular automaton (QCA) as a unitary operator realizing a phase depending on the framing of flux loops, building off work by Shirley et al. We relate this framing dependent phase to a pump of 8 copies of a p+ip state through the system. We give a resolution of an apparent paradox, namely that the pump is a shallow depth circuit (albeit with tails), while the QCA is nontrivial. We discuss also the pump of fewer copies of a p+ip state, and describe its action on topologically degenerate ground states. One consequence of our results is that a pump of n p+ip states generated by a free Fermi evolution is a free fermion unitary characterized by a non-trivial winding number n as a map from the third homotopy group of the Brilliouin Zone 3-torus to that of SU(Nb), where Nb is the number of bands. Using our simplified form of the QCA, we give higher dimensional generalizations that we conjecture are also nontrivial QCAs, and we discuss the relation to Chern-Simons theory. Joint work with L. Fidkowski.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iv-topology-quantum-error-correction-and-quantum-gravity/
Abstract: I will discuss the dynamics of monitored systems combining the ingredients of unitary evolution, measurements, and adaptive classical control. I will present various novel dynamical phases and phase transitions that arise in these systems, ranging from entanglement and teleportation phase transitions to "learnability" transitions in the ability to reconstruct quantum information from measurements. I will also discuss experimental realizations of these phenomena in noisy quantum processors.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: The ultimate dream of quantum computing, and the plan of record for many industrial efforts, is to build a fault-tolerant quantum computer. Such a device would be scientifically fascinating, but what valuable and classically intractable applications would it actually enable? This talk will survey work that the quantum algorithms team at Google has done to answer this question as it pertains to chemistry by developing, compiling, and benchmarking the most promising applications of quantum computers in chemistry and materials science. The talk will touch on algorithm development and the feasibility of applications in electronic structure, quantum dynamics, warm dense matter and simulating certain classical models of molecular vibrations.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Minimizing the energy of a many-body system is a fundamental problem in many fields. Although we hope a quantum computer can help us solve this problem better than classical computers, we have very limited understanding of where a quantum advantage may be found. In this talk, I will discuss some recent theoretical results that significantly advance our understanding. First, I describe some rigorous analyses of the Quantum Approximate Optimization Algorithm applied to minimize energy of classical spin glasses. For certain families of spin glasses, we find the QAOA has a quantum advantage over the best known classical algorithms. Second, we study the problem of finding a local minimum of the energy of a quantum system. While local minima are much easier to find than ground states, we show that finding a local minimum under thermal perturbations is computationally hard for classical computers, but easy for quantum computers.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Two key primitives in many quantum algorithms are the accurate estimation of observable expectation values and the acquisition of accurate shot counts. At present, these are challenging tasks as noise in quantum hardware affects gate fidelities as well as state preparation and measurement accuracy. These issues will be resolved once quantum error correction is available, but until then quantum error mitigation provides a viable alternative.
In this talk I will first describe how gate noise can be mitigated using probabilistic error cancellation. For this, we require an accurate and scalable model of the noise, which is achieved using out sparse Pauli-Lindblad noise model. I will explain how gate noise is shaped, learned, and finally cancelled. A second approach, which can be used to protect Clifford operations from errors and help obtain accurate shot counts, consists of coherent Pauli checks. These checks can detect certain errors, which can then be filtered out using post-selection. I will show how a simplified Markov model can be used to evaluate the (asymptotic) logical-error and post-selection rates and will discuss the results of practical experiments.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: In this talk we’ll discuss the status quo regarding the latest experimental quantum advantage claims and the evidence for their classical hardness. In particular, we’ll talk about the latest complexity theoretic results for believing that near-term, random quantum circuit experiments give rise to a provable quantum advantage over any efficient classical algorithm. We’ll then talk about the current gaps between theory and experiment. A particular focus will be on understanding if uncorrected noise, which is a defining characteristic of any near-term quantum experiment, can be exploited by fast classical simulation algorithms.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Parametrized quantum circuits (PQCs) represent a promising framework for using present-day quantum hardware to solve diverse problems in materials science, quantum chemistry, and machine learning. We introduce a "synergistic" approach that addresses two prominent issues with these models, the prevalence of barren plateaus in PQC optimization landscapes, and the difficulty of outperforming state of the art classical algorithms. This framework first uses classical resources to compute a tensor network (TN) encoding a high-quality solution to a problem of interest, and then converts this classical output into an approximating PQC which can be further improved by the use of quantum resources. Beyond simply boosting the performance of PQC models at initialization, we find this method to significantly reduce the impact of barren plateaus, in a manner that improves with increasing classical computing resources. We believe our results highlight the promise of powerful classical simulation methods not as an obstacle to be overcome in demonstrating practically useful quantum advantage, but rather as a guide to help quantum methods find their way.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: I will discuss two recent works that leverage ideas from quantum information dynamics to understand the impact of noise on large-scale quantum systems. First, I will introduce a framework based on information dynamics to describe how noise propagates in ergodic many-body quantum systems. Our framework yields immediate predictions for popular benchmarking protocols involving time-reversal, and provides a potential explanation for recent NMR experiments on ~100s of interacting quantum spins. Second, in a more rigorous context, I will provide a polynomial-time classical algorithm for simulating expectation values in almost any noisy quantum circuit. Our algorithm is provably efficient, and extends recent results on noisy random circuit sampling to a much more general setting. As a corollary, we establish that almost any quantum experiment that provides an exponential speed-up over classical computation must fail in the presence of a noise rate greater than ~1/n, where n is the number of qubits.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Entanglement is a fundamental property of quantum mechanics and emerges as a unique and essential computational resource for achieving a quantum advantage over classical computation. However, generating, verifying and preserving highly entangled states across many qubits presents significant engineering and technical challenges. This problem is central to challenging our understanding of entangled states and their role in quantum information processing, and signifies that characterizing multi-qubit entanglement can act as an important benchmark for assessing the capabilities of emerging quantum technologies. Here we review the generation and preservation of bipartite and the stronger genuine-multipartite forms of multi-qubit entanglement on IBM Quantum devices. Our results to date verified the presence of bipartite entanglement in 65-qubit graph states [1, 2] and genuine-multipartite entanglement in 27-qubit Greenberger-Horne-Zeilinger (GHZ) states respectively [3].
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: We discuss universal fluctuations that arise from natural quantum many-body dynamics. These fluctuations are unique to the statistics of global bitstring measurements and have been used in random circuit sampling tasks for recent quantum advantage claims. Based on such fluctuations, I will introduce a sample-efficient protocol which estimates the fidelity between an experimentally prepared state and an ideal target state, and is applicable to a wide class of analog quantum simulators. Finally, we apply this protocol in a 60-atom analog Rydberg quantum simulator, and further use our results to quantify the amount of mixed state entanglement present, finding that the experiment is competitive in this respect with state-of-the-art digital quantum devices performing random circuit evolution.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: This talk will present recent progress in using sophisticated trial wavefunctions in auxiliary-field quantum Monte Carlo (AFQMC).
We will highlight success and failure along with future research directions.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Computational electronic structure theory provides a probe into the microscopic details of chemical structure and processes. With a sufficiently accurate description of the wavefunction, critically important information such as ground state determination, reaction energies, spectra, etc. can be obtained, guiding new technologies and applications. Unfortunately, for strongly interacting systems, our conventional approximation schemes are often ineffective. Quantum computing provides an interesting path forward, not only due to the potential realization of advantageous quantum calculations directly, but also in the way quantum algorithm development can inspire new classical methods. In this talk, I will discuss some of the different quantum and classical techniques our team has been developing for modeling electronic structure in molecules.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Gaining insight into the equilibrium properties of quantum many-body systems is essential for advancing our understanding of fundamental physics, materials science, and a wide range of scientific and technological applications. Quantum Monte Carlo (QMC) techniques are, in the majority of cases, the only viable approach to developing a systematic understanding of large-scale quantum systems. However, current QMC schemes have limitations, with a major one being the need to tailor distinct, specific updates to each model to ensure the ergodicity of the stochastic process. In this talk, I will discuss a novel, universal, parameter-free QMC algorithm capable of simulating arbitrarily conceived physical models, including models containing mixtures of particle types and interactions in arbitrary geometries. Time permitting, I will show how these techniques can be used to devise speedy quantum Hamiltonian simulation algorithms.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: The Tensor-Train (TT) or Matrix-Product States (MPS) format stands out as a highly compact, low-rank representation for high-dimensional tensors, with numerous applications including the computation of many-body ground states with limited entanglement in spin models of condensed matter physics or quantum chemistry. The efficiency of this format hinges on the rounding operation, a process that trims the internal ranks of tensors to ensure feasible computational times and memory usage.
In this talk, we introduce a suite of randomized algorithms specifically designed for the TT rounding task, building upon and expanding existing randomized low-rank matrix approximation methodologies. These algorithms not only preserve the TT format’s integrity but also provide a considerable computational advantage, particularly evident when rounding a sum of TT-tensors or the result of a matrix-vector product—a frequent bottleneck in numerous applications. We achieve up to a 20× speedup, markedly boosting the performance of classical iterative Krylov methods such as GMRES and Lanczos when applied to vectors in TT format. This enhancement allows their use as viable alternatives to Alternating Least-Squares (ALS) or (DMRG) in certain scenarios. We present and discuss the randomized algorithms, providing a comparative analysis of their empirical accuracy and computational efficiency against deterministic counterparts.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: We first introduce a class of 1D translationally invariant and local classical and quantum dynamics that have an unusual approach to equilibrium. In one of our examples, expectation values of local operators relax in a time which is exponentially large in system size, implying an unusual kind of hydrodynamics. In another example, a system can only relax when coupled to a bath which is at least exponentially large in the system's size, a phenomenon that we call fragile fragmentation. A field of mathematics called geometric group theory plays an important role in constructing these examples. We then consider ground states of a two-dimensional generalizations of these models and find a plethora of unusual entanglement properties such as (1) area laws emerging entirely from long range correlations and (2) power law violations of area law scaling.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Approximation algorithms are a natural remedy for classical NP-hardness, where a polynomial-time algorithm produces an approximate solution whose cost is guaranteed to be within some multiplicative factor of the optimum. The Quantum Approximation Optimization Algorithm and recent work in approximating extremal energy states of local Hamiltonians have prompted the study of quantum approximation algorithms. Can we expect these to offer provable advantages over classical counterparts? A potentially promising approach is to find optimization problems that have some underlying connection to quantum mechanics. I will discuss recent work in this vein on approximating Quantum Max Cut and other physically motivated local Hamiltonians that end up generalizing well-known classical discrete optimization problems. I will also overview recent results on quantum streaming algorithms for Max Cut and related problems, including a recently established exponential quantum streaming advantage.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Quantum computers can offer dramatic speed-ups over their classical counterparts forcertain problems. However, noise remains the biggest impediment to realizing the full potential of quantum computing. While the theory of quantum error correction offers a solution to this challenge, a large scale realization of fault tolerance seems currently inaccessible. What can one hope to do then, with existing noisy processors? In this talk, I will present experiments that produce reliable expectation values from a noisy 127 qubit processor, at a scale that is well beyond brute-force classical computation. We argue that this represents evidence for the utility of quantum computing in a pre-fault-tolerant era. I will also discuss recent classical benchmarking of our experiments beyond exact verification.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: Variational quantum eigensolvers (VQEs) constitute a class of hybrid quantum-classical simulation algorithms that are envisioned as possibly appropriate for noisy intermediate scale quantum processors. For VQEs to be useful, it is important to reduce the size of the ansatz and the number of required measurements. I will present our work addressing these issues with an adaptive, problem tailored approach to ansatz construction. I will also discuss recent work showing how the overhead can be lowered in ADAPT-VQE.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-iii-many-body-quantum-systems-via-classical-and-quantum-computation/
Abstract: If we believe both that quantum computers may be able to do some computations exponentially faster than their classical counterparts and that we live in a quantum world, then our ability to learn from observational data as scientists may fundamentally change what we can do. Here, we will first review some recent results in quantum machine learning that allow us to put these ideas on a rigorous footing. We then show that quantum computers, and more specifically quantum memory, offer us an opportunity to learn from a quantum world with exponentially less data than traditional experiments. Taking an alternative perspective, we then consider the extent to which data can be put on the same footing as precomputation, and what this may mean for future distributed systems that consider quantum data and computation on the similar footings.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule
Abstract: The success of modern deep learning hinges on the ability to train neural networks at scale. Through clever reuse of intermediate information, backpropagation facilitates training through gradient computation at a total cost roughly proportional to running the function, rather than incurring an additional factor proportional to the number of parameters - which can now be in the trillions. Naively, one expects that quantum measurement collapse entirely rules out the reuse of quantum information as in backpropagation. But recent developments in shadow tomography, which assumes access to multiple copies of a quantum state, have challenged that notion. In this talk, we will investigate the feasibility of achieving backpropagation scaling for parameterized quantum models, which is essential for their use at scale.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule
Abstract: As the frontiers of artificial intelligence advance more rapidly than ever before, generative language models like GPT are already causing significant economic and social transformation. In addition to their remarkable performance on typical language tasks (such as generating text from a prompt), language models are being rapidly adopted as powerful ansatze states for quantum many-body systems. In this talk, I will discuss the use of language models for learning quantum states realized in experimental Rydberg atom arrays. By combining variational optimization with data-driven learning using qubit projective measurements, I will show how language models are poised to become one of the most powerful computational tools in our arsenal for the design and characterization of quantum simulators and computers.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule
Abstract: Quantum machine learning models have shown successful generalization performance even when trained with few data. In this talk, we will show that traditional approaches to understanding generalization fail to explain the behavior of such quantum models. We experimentally reveal that state-of-the-art quantum neural networks accurately fit random states and random labeling of training data. This ability to memorize random data defies current notions of small generalization error, problematizing approaches that build on complexity measures such as the VC dimension, the Rademacher complexity, and all their uniform relatives. We complement the empirical results with a theoretical construction showing that quantum neural networks can fit arbitrary labels to quantum states, hinting at their memorization ability. Our results do not preclude the possibility of good generalization with few training data but rather rule out any possible guarantees based only on the properties of the model family. These findings expose a fundamental challenge in the conventional understanding of generalization in quantum machine learning and highlight the need for a paradigm shift in the design of quantum models for machine learning tasks.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule
Abstract: One of the key challenges of the quantum machine learning field is identifying learning problems where quantum learning algorithms can achieve a provable exponential advantage over classical learning algorithms. Proofs of separation for learning mostly work by reductions to plausible complexity theoretic assumptions of various types. Previously known examples of advantages are all contrived, and all rely on cryptographic methods to make learning hard for a classical learner. However, the broadly shared intuition is that learning separations should in particular be most apparent when the learning task involves data from genuinely quantum sources (but still quantum, i.e., measured out), which are very different from cryptographic problems.
In the first part of this talk I will discuss this apparent discrepancy and present a series of new results showing various types of advantages that can be obtained, which will include advantages stemming from a large class complex quantum physical systems, rather than cryptography.
In the second part of the talk, I will discuss how certain complexity theoretic arguments can be used to prove learning separations in a much more restricted setting where quantum capabilities are only assumed in the training stage of the quantum machine learning system, whereas the deployment is fully classical.
The talk will be based on the following references:
-Exponential separations between classical and quantum learners, C. Gyurik, V. Dunjko, arXiv:2306.16028
-Shadows of quantum machine learning, S. Jerbi, C. Gyurik, S. C. Marshall, R. Molteni, V. Dunjko,
arXiv:2306.00061
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule
Abstract: Statistical query learning model (SQ) is a restricted learning model that learns by querying estimates of random variables. It was originally introduced by Kearns to capture effect of noisy samples in learning. It is known that there are efficiently PAC learnable problems not efficiently learnable in SQ. Does this also hold for the quantum generalizations of these models?
We discuss quantum generalization of SQ -- the quantum statistical query learning model (QSQ) -- and compare its power to both quantum PAC and quantum PAC with separable measurements. We discuss two results: the equivalence of entangled and separable measurements for boolean function classes and a separation of QSQ and noisy quantum PAC learning. Our main technical contributions are lower bounds on QSQ learning.
Part II.
- Part I. outlined a basic proof strategy for QSQ lower bounds. Here we give more detail about the QSQ lower bound proof.
- Introduces the main result: separation of QSQ and QPAC with noise.
- More on the lower bounding technique.
- Applications of QSQ?
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule
Abstract: Statistical query learning model (SQ) is a restricted learning model that learns by querying estimates of random variables. It was originally introduced by Kearns to capture effect of noisy samples in learning. It is known that there are efficiently PAC learnable problems not efficiently learnable in SQ. Does this also hold for the quantum generalizations of these models?
We discuss quantum generalization of SQ -- the quantum statistical query learning model (QSQ) -- and compare its power to both quantum PAC and quantum PAC with separable measurements. We discuss two results: the equivalence of entangled and separable measurements for boolean function classes and a separation of QSQ and noisy quantum PAC learning. Our main technical contributions are lower bounds on QSQ learning.
We split our talk into two parts; this is part I.:
Part I.
- Motivates QSQ, describes the model in detail and outlines the main results.
- Discusses the equivalence of function learning by separable vs. entangled measurements.
- Outlines a basic proof strategy for QSQ lower bounds.
Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-mathematical-aspects-of-quantum-learning/?tab=schedule


