Results 2011 - 2020 of 23898
Mingda Qiao is a postdoc at MIT, and an incoming assistant professor at UMass Amherst (starting Fall'25). His research focuses on the theory of prediction, learning, and decision-making in sequential settings, as well as collaborative federated learning...
Tian Li is an Assistant Professor at the Computer Science Department and Data Science Institute at the University of Chicago. Her research interests are in optimization, trustworthy machine learning, and collaborative learning. She has spent time at...
Pranjal Dutta is currently an Assistant Professor in the College of Computing and Data Science (CCDS) at Nanyang Technological University (NTU) Singapore. Before joining NTU, Pranjal Dutta was a postdoc at NUS, advised by Prof. Divesh Aggarwal. He obtained...
Recent developments in quantum algorithms, particularly the 2021 discovery of an apparent exponential quantum speedup for the SIS-infinity problem by filtering, and the 2024 discovery of an apparent exponential quantum speedup for the optimal polynomial...
In this talk, I will explain how to construct succinct classical interactive arguments for QMA, using only standard cryptographic assumptions (implied by LWE). Our approach builds on Kalai, Lombardi, Vaikuntanathan’s “compiler” to convert a two-prover interactive proof in the MIP* model into a one-prover interactive argument, and achieves succinctness by combining ideas from the MIP* literature with post-quantum succinct arguments of knowledge. Perhaps unexpectedly, our construction does not yield any form of quantum PCP—neither a “Hamiltonian” PCP nor a “games” PCP—in contrast to the situation in the classical world, where PCPs appear to be inherent to succinct arguments for NP.
Based on joint work with Tony Metger and Tina Zhang (2404.19754)
I will show how an area law in the mutual information for the maximally-mixed state in a highly-degenerate ground-space of a many-body Hamiltonian follows from the existence of a `good' approximation to the ground state projector (a good AGSP). Good AGSPs have been a pivotal ingredient in former area-law proofs, but so far, they been used only for proving area-law when the ground-space degeneracy is at most polynomial. Our proof, however, uses new tools from quantum information theory to show that the maximally-mixed state in the ground space satisfies an area-law, *regardless* of the underlying degeneracy.
As a corollary, we use existing constructions of good AGSPs to prove such area-law for the case of highly-degenerate gapped 1D systems and frustration-fee, locally-gapped, 2D systems.
Finally, I will also show how in 1D our results imply the existence of an efficient MPO approximation for the maximally-mixed state, with an inverse polynomially small error in the trace distance.
Joint work with Raz Firanko Rahul Jain, based on arXiv:2310.19028
The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low-energy Hamiltonians even when the gap between 'high' and 'low' energy is large (constant). A natural proof strategy is gap amplification: start from the fact that high- and low-energy Hamiltonians are hard to distinguish if the gap is small (inverse polynomial) [KSV02] and amplify the Hamiltonians to increase the energy gap while preserving hardness. Such a gap amplification procedure is at the heart of Dinur's proof of the classical PCP theorem [Din07]. In this work, following Dinur's model, we introduce a new quantum gap amplification procedure for Hamiltonians which uses random walks on expander graphs to derandomise (subsample the terms of) the tensor product amplification of a Hamiltonian. Curiously, our analysis relies on a new technique inspired by quantum de Finetti theorems, which have previously been used to rule out certain approaches to the quantum PCP conjecture [BH13]. Iterating our amplification procedure yields a streaming quantum PCP theorem, i.e., a quantum-PCP like statement for Hamiltonians with terms that are not necessarily local, but are very simple and can be measured in blocks of five qubits at a time.