Results 2051 - 2060 of 23898
Learning the Hamiltonian underlying a quantum many-body system in thermal equilibrium is a fundamental task in quantum learning theory and experimental sciences. To learn the Gibbs state of local Hamiltonians at any inverse temperature $\beta$, the state-of-the-art provable algorithms fall short of the optimal sample and computational complexity, in sharp contrast with the locality and simplicity in the classical cases. In this work, we present a learning algorithm that learns each local term of a $n$-qubit $D$-dimensional Hamiltonian to an additive error $\epsilon$ with sample complexity ~ $e^{poly(\beta)} / \beta^2\epsilon^2 \log(n)$. The protocol uses parallelizable local quantum measurements that act within bounded regions of the lattice and near-linear-time classical post-processing. Thus, our complexity is near optimal with respect to $n,\epsilon$ and is polynomially tight with respect to $\beta$. We also give a learning algorithm for Hamiltonians with bounded interaction degree with sample and time complexities of similar scaling on $n$ but worse on $\beta, \epsilon$. At the heart of our algorithm is the interplay between locality, the Kubo-Martin-Schwinger condition, and the operator Fourier transform at arbitrary temperatures. Based on joint work with Anurag Anshu and Quynh T. Nguyen, [2504.02706].
Self-correcting quantum memories store logical quantum information for exponential time in thermal equilibrium at low temperatures. By definition, these systems are slow mixing. This raises the question of how the memory state, which we refer to as the Gibbs state within a logical sector, is created in the first place.
In this paper, we show that when initialized from a ground state of the 4D toric code, a quasi-local quantum Gibbs sampler rapidly converges to the corresponding low-temperature Gibbs state within a logical sector, which then remains meta-stable. This illustrates a dynamical view of self-correcting quantum memories, where the “syndrome sector” rapidly converges to thermal equilibrium, while the “logical sector” remains stable.
The key technical ingredients behind our approach are new, low-temperature decay-of-correlation properties for these meta-stable states. We generalize our results to a broad class of self-correcting quantum memories on lattices with parity check redundancies.
Based on joint work with Reza Gheissari and Yunchao Liu.
This reunion workshop is for long-term participants in the program " Quantum Algorithms, Complexity, and Fault Tolerance," held in the spring 2024 semester. It will provide an opportunity to meet old and new friends. Moreover, we hope that it will give...
In this deliberately provocative two-part talk from the recent workshop on Theoretical Aspects of Trustworthy AI, Somesh Jha (University of Wisconsin) makes a case for applying a security and cryptography mindset to evaluating the trustworthiness of machine learning systems, particularly in adversarial and privacy-sensitive contexts.
AI for mathematics (AI4Math) is intellectually intriguing and crucial for AI-driven system design and verification. Formal mathematical reasoning is grounded in formal systems such as Lean, which can verify the correctness of reasoning and provide automatic feedback. This talk by Kaiyu Yang (Meta) from the Simons Institute and SLMath joint workshop on AI for Math and TCS introduces the basics of formal mathematical reasoning, focusing on two central tasks: theorem proving (generating formal proofs given theorem statements) and autoformalization (translating from informal to formal).
Decision problems about infinite groups are typically undecidable, but many are semidecidable if given an oracle for the word problem. One such problem is whether a group is a counterexample to the Kaplansky unit conjecture for group rings. In this talk from the workshop AI for Mathematics and Theoretical Computer Science, Giles Gardam (University of Bonn) presents the mathematical context and content of the unit conjecture, and explains how viewing the problem as an instance of the Boolean satisfiability problem (SAT) and applying SAT solvers show that it is not just solvable in theory but also in practice.
Greetings from Berkeley, where we’ve recently welcomed a merry band of cryptographers for what promises to be an outstanding summer program on cryptography. Building on the success of the Simons Institute’s 2015 summer crypto program, legendary for its influence on the field and participants’ careers, Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation promises to be even bigger and better.