Complexity classification of local Hamiltonian problems
- Submitting institution
-
University College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 14109
- Type
- E - Conference contribution
- DOI
-
10.1109/FOCS.2014.21
- Title of conference / published proceedings
- 2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014)
- First page
- 120
- Volume
- -
- Issue
- -
- ISSN
- 0272-5428
- Open access status
- Out of scope for open access requirements
- Month of publication
- January
- Year of publication
- 2014
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 11
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- First classification theorem in quantum Hamiltonian complexity, analogous to Schaeffer’s seminal dichotomy theorem for classical constraint satisfaction problems. Influenced the field to move beyond proving specific computational hardness results, to giving complete classifications (e.g. “The Classification of Reversible Bit Operations”, Aaronson, Grier, Schaeffer, 2015; “Complexity classification of two-qubit commuting Hamiltonians”, Bouland, Mancinska, Zhang, 2016). Covered in all subsequent review articles in this area (Grillo 2018; Wigderson 2018; Albash & Lidar, Rev. Mod. Phys. 2018; Gharibian, Huang & Landau, Foundations & Trends Theor. Comp. Sci. 2015).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -