Robust Polynomial Method and a Sub-Volume Law for Locally Gapped Frustration-Free Spin Systems

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=tMdNENiwkpI


Duration: 58:59
401 views
5

Anurag Anshu (IQC)
The Quantum Wave in Computing
Seminar, Apr. 14, 2020

The robust polynomial method (Sherstov [2012]) was developed for the composition of polynomial approximations to boolean functions, inspired by questions on the composition of quantum query algorithms. In this talk, we discuss how it can be used to study polynomial approximations to the AND function, reproducing some known improvements over the Chebyshev-based approximation. Using these ideas and the tool of Approximate Ground Space Projectors developed in prior works , we study the entanglement entropy of frustration-free ground states on a two dimensional lattice. Under the assumption of a local spectral gap (also referred to as a uniform spectral gap), we show a sub-volume scaling of the entanglement entropy.



Other Videos By Simons Institute for the Theory of Computing


2020-04-28LWE with Side Information: Attacks and Concrete Security Estimation
2020-04-27Quantum Secure Commitments and Collapsing Hash Functions
2020-04-27Quantum Cryptography (Beyond QKD)
2020-04-27Watermarking and Traitor Tracing for PRFs
2020-04-27New Techniques for Practical Lattice-Based Zero-Knowledge
2020-04-27Signatures, Commitments, Zero-Knowledge, and Applications
2020-04-23Post-Quantum Multi-Party Computation in Constant Rounds
2020-04-23Quantum Coupon Collector
2020-04-23Laconic Function Evaluation
2020-04-20A Tale of Turing Machines, Quantum-Entangled Particles, and Operator Algebras
2020-04-15Robust Polynomial Method and a Sub-Volume Law for Locally Gapped Frustration-Free Spin Systems
2020-04-13Optimal Broadcast Encryption from Pairings and LWE
2020-04-09Secure Multi-party Quantum Computation with a Dishonest Majority
2020-04-09Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
2020-04-08NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations
2020-04-08Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
2020-04-07The Digital Fence: Taiwan’s Response to COVID-19
2020-04-06Lattices, Post-Quantum Security and Homomorphic Encryption — Q&A
2020-04-06Lattices, Post-Quantum Security and Homomorphic Encryption
2020-04-03What Do Algorithmic Fairness and COVID-19 Case-Severity Prediction Have in Common?
2020-04-02Efficient Learning of Pauli Channels


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing