The goal of this master’s thesis is to design and analyze a Feynman–Kitaev (FK) Hamiltonian whose ground space encodes the time evolution of a classical cellular automaton, with Conway’s Game of Life (GoL) as a primary case study. The project sits at the intersection of quantum Hamiltonian complexity, reversible computation, and classical dynamical systems, and seeks to clarify how non-reversible, classical rules can be embedded into quantum Hamiltonians of the FK type.
The FK construction provides a systematic way to translate a discrete-time computation into a local Hamiltonian whose ground state is a “history state.” A local Hamiltonian is then engineered so that its ground space consists exactly of such valid history states, enforcing the constraint between consecutive clock times.
Conway’s GoL is a deterministic, local rule mapping a finite board configuration at generation t to generation t+1 via a neighborhood-based update. Unlike typical reversible cellular automata, Life is many-to-one and hence not directly unitary. A central theoretical challenge of the thesis is to construct a reversible embedding of the Life update that can be implemented by unitary gates and thus plugged into the FK framework.
The theoretical foundation will draw on:
1. Quantum circuit models and reversible computation;
2. The FK mapping from circuits to local Hamiltonians, including clock encodings and locality bounds;
3. Basic theory of cellular automata, including universality and reversibility;
4. Elements of quantum Hamiltonian complexity (e.g. local Hamiltonian problem, QMA-hardness motivation).
The main challenge of the project is to extend the FK construction from quantum circuit, where quantum gates act sequentially one at a time, to cellular automata, where local updates happen homogeneously in parallel. The project is highly exploratory in nature. Depending on the student's interest, once the Hamiltonian is constructed, the next step could be either 1) finding the correspondence between the eigensystem and patterns like still life and oscillators and solving the simpler ones analytically; or 2) Leveraging quantum annealing algorithms and platforms like D-wave to computationally search for more complex features like glider guns, and demonstrating the improved efficiency over classical search algorithms.
Milestones:
1. Month 1–2: Literature and formal setup
2. Month 3–5: Design Reversible GoL circuit and construct the FK Hamiltonian
3. Month 6–8: Analysis and extensions (theoretical or computational)
4. Month 9: Writing and polishing
Courses relevant from the bachelor's degree:
Recommended courses for theoretical curriculum in the master's programme: