Quantum Complexity: Quantum PCP, Area Laws, and Quantum Gravity 2024
2024-03-18..2024-03-22
Berkeley, United States
who it's for
quantum complexity theorists, quantum information theorists, quantum gravity researchers, quantum error correction researchers, condensed matter theorists, tensor network researchers, quantum algorithm designers, computational complexity theorists
topics
commuting local Hamiltonians; strict 2D area law; quantum PCP conjectures; NLTS from qLDPC codes; quantum LDPC code constructions; injective PEPS circuit mapping; pseudo entropy in holography; pseudoentanglement and pseudorandomness; constant-temperature Gibbs sampling; QMA versus QCMA oracle separations; higher-dimensional cubical expansion
| title | author | length |
|---|---|---|
| How Quantum Complexity Found Its Way into Black Hole Physics | Leonard Susskind | 01h 12m |
Conjecture ties the black hole interior three‑volume to quantum state complexity (volume = complexity), which grows linearly for long times and saturates at… | ||
| Quantum Complexity of Clique Homology | Robbie King | 44m |
Shows a precise claim: deciding whether a graph’s clique complex has a k‑dimensional hole is in QMA and is QMA1‑hard under a polynomial spectral gap promise… | ||
| Introduction To Commuting Local Hamiltonian Problems | Jiaqing Jiang | 48m |
Claims that commuting local Hamiltonian instances sit between classical and full quantum complexity and gives concrete results: structure lemma proves all… | ||
| Classification of 2D Gapped Ground States With Strict Area Law | Isaac Kim | 50m |
Assuming a strict area law on every constant-size disk, any 2D gapped ground state on a disk is mapped by a constant‑depth quantum circuit (built by local Petz… | ||
| Oracle Separations Between QMA and QCMA | Angelos Pelecanos | 47m |
Surveys explicit constructions that separate QMA vs QCMA under nonstandard oracles: a quantum oracle that reflects one random state (needs a quantum witness… | ||
| Local Minima in Quantum Systems | Robert Huang | 46m |
Defines local minima with inverse‑polynomial epsilon under two perturbation families: local unitary perturbations (where typical random states sit on barren… | ||
| NLTS Hamiltonians (and Strongly-Explicit SoS Lower Bounds) from Low-Rate Quantum LDPC Codes | Louis Golowich | 44m |
Proves two concrete improvements: NLTS Hamiltonians arise from linear-distance qLDPC codes even when dimension is arbitrarily small, down to one logical qubit… | ||
| Circuit-To-Hamiltonian From Tensor Networks and Fault Tolerance | Quynh Nguyen | 36m |
Constructs a clock-free map from any quantum circuit to a local Hamiltonian by turning the circuit’s Choi states into an injective PEPS parent Hamiltonian; the… | ||
| The Quantum Games PCP: Results and Confessions | Anand Natarajan | 48m |
Claims a 7-prover, 1-round MIP proof system that would map QMA local Hamiltonians with 1/poly gap to a constant-gap Pauli-measurement test, using an… | ||
| Expansion of Higher-Dimensional Cubical Complexes With Application To Good ... | David Lin | 39m |
Constructs quantum locally testable codes achieving near-optimal distance (up to polylog factors) and constant weight LDPC checks after amplification, by… | ||
| Holographic Pseudo Entropy and Emergent Spacetime | Tadashi Takayanagi | 51m |
Introduces pseudo entropy as a complex generalization of entanglement entropy defined from a transition (post‑selected) matrix and shows it has a concrete… | ||
| Quantum Computational Advantage With Constant-Temperature Gibbs Sampling | Thiago Bergamaschi | 38m |
Claims a family of n‑qubit commuting parent Hamiltonians at log log n locality and a fixed inverse temperature whose Davies generator is provably rapid mixing… | ||
| Pseudoentanglement | Soumik Ghosh | 01h 00m |
Defines pseudoentanglement as two efficiently preparable ensembles that are computationally indistinguishable yet have a polynomial gap in von Neumann entropy… | ||
| Pseudorandomness and Pseudoentanglement in Holography | Lijie Chen | 01h 07m |
Constructs explicit tensor-network CFT ensembles that are computationally indistinguishable yet have different RT entropies: exact RT for tree tensor networks… | ||
| A Quantum Complexity Approach to the Problem of Weak Cosmic Censorship | Netta Engelhardt | 01h 06m |
Claim: classical weak cosmic censorship fails but a quantum version holds under a complexity hypothesis. Using AdS/CFT and modeling boundary time evolution as… | ||
| Is It Dark Matter, or Is Spacetime Undergoing a Random Walk? | Jonathan Oppenheim | 01h 12m |
Presents a concrete, completely positive trace‑preserving master equation that couples classical phase‑space variables to quantum density matrices, producing a… | ||
| Tensor Network Toy Models of Holographic Dualities: Locality and Causality | Tamara Kohler | 01h 00m |
Combines holographic quantum error-correcting codes with Hamiltonian simulation to produce a bulk→boundary mapping that preserves encoding, entanglement… | ||
| nothing matches | ||