Undecidability of the Spectral Gap
Publication date
Authors
DOI
Document Type
Bachelor Thesis
Metadata
Show full item recordCollections
License
CC-BY-NC-ND
Abstract
We treat the results of the 2015 paper by Cubitt et al. entitled “Undecidability of the Spectral Gap”, and the constructions required to arrive at these results. This paper showed that a specific quantum mechanical problem (the “spectral gap problem”) is algorithmically undecidable, using techniques from computer science. We also treat the theory from quantum mechanics and computer science that is required to understand these results and constructions.
Keywords
quantum mechanics; computer science; decidability; computability; quantum information; quantum computing; Turing machine; quantum Turing machine; halting problem; spectrum; spectral theory; spectral gap; domino problem;