Oracle Separations Between QMA and QCMA

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


Duration: 47:07
99 views
0

Angelos Pelecanos (UC Berkeley)
https://simons.berkeley.edu/talks/angelos-pelecanos-uc-berkeley-2024-03-19
Quantum Complexity: Quantum PCP, Area Laws, and Quantum Gravity

Recently, several non-standard oracle separations between QMA and QCMA have appeared.

In this tutorial, we will survey these results and draw some connections with sparse Hamiltonians.

Finally, we will see how these non-standard oracles highlight directions towards obtaining a standard oracle separation.



Other Videos By Simons Institute for the Theory of Computing


2024-04-15Pseudorandomness and Pseudoentanglement in Holography
2024-04-15Pseudoentanglement
2024-04-15Quantum Computational Advantage With Constant-Temperature Gibbs Sampling
2024-04-15Holographic Pseudo Entropy and Emergent Spacetime
2024-04-15What on Earth Does Complexity Theory Have to Do with Gravity?
2024-04-15Expansion of Higher-Dimensional Cubical Complexes With Application To Good ...
2024-04-15The Quantum Games PCP: Results and Confessions
2024-04-15Circuit-To-Hamiltonian From Tensor Networks and Fault Tolerance
2024-04-15NLTS Hamiltonians (and Strongly-Explicit SoS Lower Bounds) from Low-Rate Quantum LDPC Codes
2024-04-15Local Minima in Quantum Systems
2024-04-15Oracle Separations Between QMA and QCMA
2024-04-15Classification of 2D Gapped Ground States With Strict Area Law
2024-04-15Introduction To Commuting Local Hamiltonian Problems
2024-04-15Quantum Complexity of Clique Homology
2024-04-15How Quantum Complexity Found Its Way into Black Hole Physics | Special Lecture
2024-04-04Private Information Retrieval: Chasing Capacity with Algebraic Codes
2024-04-04Data Deduplication For Redundant Graph Structures Files
2024-04-04High-Rate Fair-Density Parity-Check Codes
2024-04-04Graph Neural Networks for Classical and Quantum Channel Coding
2024-04-04Sparsity and Privacy in Distributed Matrix Multiplication
2024-04-04Service Rates Of Mds Codes & Fractional Matchings In Quasi-Uniform Hypergraphs


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Quantum Complexity: Quantum PCP; Area Laws; and Quantum Gravity
Angelos Pelecanos