Stanford Advisors

Contact

  • Academic
    tkohler@stanford.edu
    University - Scholar Department: Computer Science Position: Postdoctoral Scholar

Additional Info

  • Mail Code: 9025

All Publications

  • Clique Homology is QMA 1 -hard. Nature communications Crichigno, M., Kohler, T. 2024; 15 (1): 9846

    Abstract

    We address the long-standing question of the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology, posed by Kaibel and Pfetsch over twenty years ago. We show that decision problem is QMA 1 -hard and the exact counting version is # BQP -hard. In fact, we strengthen this by showing that the problems remains hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and algebraic topology. As we discuss, a version of the problems satisfying a suitable promise and certain constraints is contained in QMA and # BQP , respectively. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.

    View details for DOI 10.1038/s41467-024-54118-z

    View details for PubMedID 39537617

  • Security of quantum position-verification limits Hamiltonian simulation via holography JOURNAL OF HIGH ENERGY PHYSICS Apel, H., Cubitt, T., Hayden, P., Kohler, T., Perez-Garcia, D. 2024

    View details for DOI 10.1007/JHEP08(2024)152

    View details for Web of Science ID 001295052000008