Quantum Complexity of Clique Homology
summary
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. Builds a vertex‑weighted graph construction that encodes n‑qubit Hamiltonians into an exponentially large chain space via the combinatorial Laplacian, uses local gadgets to implement terms, and proves gap preservation with algebraic perturbation control through spectral sequences. Labels the problem gapped clique homology.
AI-written summary · about
chapters (13)
- 0:00Quantum complexity of homology
- 1:54Motivation for quantum TDA
- 3:48Building simplicial complexes
- 5:16Homology and chain complexes
- 12:23Complexity of homology problems
- 15:17Laplacian operator in homology
- 18:53Gapped clique homology problem
- 21:35Gapped clique homology in QMA
- 23:24QMA hardness of gapped clique
- 26:18Homology and supersymmetry
- 30:30Implications for quantum TDA
- 32:35Spectral sequences overview
- 38:43Conclusion and open questions
related talks
46mSymmetries, Graph Properties, and Quantum Speedups
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
01h 10mQuantum Advantage with Shallow Clifford Circuits
24mQuantum Distributed Algorithms for Detection of Cliques
15mClassical algorithms and quantum limitations for maximum cut on high-girth graphs
01h 06mHow Hamiltonian complexity differs from quantum chemistry
44mQuantum Meets Minimum Circuit Size Problem
22mQuantum space, ground space traversal, and how to embed multi-prover...