Back to search

Boston University

Word problems in physics and computation

Abstract

dc:description.abstract

This 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 × 9

Rights

dc:rights
Statement dc:rights
  • Attribution-ShareAlike 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53575

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Khudorozhkov, Alexey. Word problems in physics and computation. doctoral thesis, Boston University, 2026. https://hdl.handle.net/2144/53575