Abstract
dc:description.abstractThis dissertation develops a unified research program at the interface of physics and computer science, with geometric group theory as the common language. Its central object is the group word problem, used as both a decision problem and a constructive design principle. In many-body physics, words become physical configurations and relations become local dynamical rules; the complexity of the word problem then produces glassy and non-ergodic behavior. In computation, this viewpoint recasts classical reversible circuit equivalence as a word problem for groups generated by reversible gates. The physics contributions construct "group word models'' exhibiting complexity-controlled relaxation, Hilbert space fragmentation, finite-size jamming, and, in higher dimensions, fragmentation topologically robust to arbitrary local perturbations. On the computation side, the dissertation develops an equational theory of classical reversible circuits. Its main result is an explicit presentation of Alt(2^n), the group of even reversible computations on n bits, generated by all C^(n-2)NOT gates, with diagrammatic relators uniform in n. This axiomatizes equivalence for that gate family. The construction also advances the broader goal of a complete equational theory of classical reversible circuits and the locality conjecture, which asks whether all equivalences over a fixed bounded-support universal gate set follow from identities involving only a bounded number of wires. The conjecture remains open.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Physics
- Grantor
- Boston University
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Khudorozhkov, Alexey
- Advisor dc:contributor.advisor
-
- Chamon, Claudio
- ORCID dc:identifier.orcid
Subjects
dc:subject × 9Rights
dc:rights- Statement dc:rights
-
- Attribution-ShareAlike 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53575