The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems

• The fixed-rule N × N tiling problem is NEXP-complete when N is the only input, written in binary; a polynomial-time-in-N algorithm would imply EXP = NEXP.The tile set, placement constraints, and boundary conditions are fixed across inputs.Source: §1 · pp. 2–3
• Earlier hard tiling reductions varied the tile set, constraints, or boundary conditions; the paper instead proves hardness for fixed rules and an initially empty grid.Source: §1 · p. 3
• The classical construction encodes an NEXP instance in N’s binary expansion, using fixed tiles to count N and supply it as input to a universal Turing machine.This avoids varying tile types or boundary conditions to encode the instance.Source: §1 · pp. 2–3
• Translational invariance is physically natural, but unlike position-dependent Hamiltonians, identical local terms do not preclude a hard ground-state problem.The paper’s result addresses the gap between position-dependent QMA-completeness constructions and more uniform systems studied in practice.Source: §1 · p. 4
• Finding the ground state energy of a one-dimensional, translationally invariant system with nearest-neighbor interactions is QMA_EXP-complete, with particle count N as the only varying parameter.A control particle shuttles between the system’s ends, counts particles, and feeds N’s binary encoding to a quantum Turing machine.Source: §1 · p. 4
• The construction yields an ordered, translationally invariant Hamiltonian with complex ground states, suggesting emergent rather than imposed disorder in a spin-glass-like system.The authors note that they lack techniques to analyze the complexity of an arbitrary specific Hamiltonian term.Source: §1 · pp. 4–5
• In one dimension, classical tiling is solvable in polylog N time, whereas the quantum problem appears to require exp(N) time even on a quantum computer unless QMA_EXP = BQEXP.Source: §1 · p. 5

TILING

• TILING is NEXP-complete when binary N alone specifies an N × N grid with fixed tiles, adjacency rules, and a designated corner tile.The corner tiles mark the border; two layers simulate Turing machines, with a binary counter encoding N^1/k for a nondeterministic machine. Binary input matters: unary N would yield only one instance per size and put the problem in P/poly.Source: §2 · p. 5

TILING variants

• The tiling study varies boundary conditions, weighted adjacency costs, reflection or rotation symmetry, and dimension; periodic-boundary tiling is also hard.Some variants have efficient algorithms whose threshold N0 is uncomputable from the tile parameters, so this does not rule out practical hardness.Source: §2 · p. 6

Finite-chain TIH

• 1-DIM TIH is QMAEXP-complete, and setting all but one interaction to zero extends completeness to every r ≥ 1.The construction uses a clocked uniform superposition of computation states: a counter phase runs for N − 3 steps, then a verifier uses a Θ(N)-length quantum witness; nonaccepting computations are penalized. A ground-energy algorithm polynomial in system size would imply QMAEXP = BQEXP.Source: §2 · p. 7

Finite-chain TIH variants

• The finite-chain TIH problem remains QMAEXP-complete with periodic boundaries and with reflection symmetry under either open or periodic boundaries.Source: §2 · p. 7

Infinite-chain TIH

• ITIH, where the input is a two-particle Hamiltonian and the task concerns ground-state energy per particle on an infinite chain, is QMAEXP-complete.Source: §2 · pp. 7–8

N-REPRESENTABILITY

• The N-REPRESENTABILITY variant [LCV07] is QMAEXP-complete when ρ is fixed and binary N is the sole input.It asks whether ρ is close to the adjacent-particle marginal of a translationally invariant pure state on N particles arranged in a circle.Source: §2 · p. 8

3 Hardness of TILING

• The binary counter generates the encoded input from N, with its output length logarithmic in N; padding then permits reductions from arbitrary NEXP languages.For sufficiently large N, the counter output length n satisfies 2^c1n ≤ N ≤ 2^c2n, and an N is computable for any input string; the reduction chooses N so the counter outputs x.Source: §3 · p. 8
• Boundary tiles and their pairing rules mark the grid’s sides and constrain which boundary and interior tiles can meet.The four corners use designated tile types, and the boundary rules enforce the side markings.Source: §3 · pp. 8–9, Table 2 · p. 9
• The grid’s two layers simulate the counter downward and the input machine upward, copying the counter output onto the machine’s input tape.The top boundary initializes the counter; additional layer rules initialize the machine’s single head and match the copied alphabet symbols.Source: §3 · pp. 9, 11
• Turing-machine tiles encode tape symbols, head states, and moves, while adjacency constraints ensure each successive row represents a legal transition.Rows contain ordinary tape tiles and adjacent pairs of head tiles; these pairs shift one position per row according to an allowed transition.Source: §3 · p. 11
• A valid tiling exists if and only if the nondeterministic machine accepts the input in N − 3 steps.The counter’s output is copied to the machine’s input tape, and layer 2 permits only accepting-state head tiles at the boundary enforcing acceptance.Source: §3 · pp. 9, 11, 12

4 Variants of the Classical Tiling Problem

• The variants include different boundary conditions, weighted adjacent-tile pairs, and added reflection or rotation symmetry; in one dimension, TILING and these variants are easy.Weights turn absolute prohibitions on adjacent tiles into soft conditions.Source: §4 · p. 12
• Hardness results reduce from TILING, sometimes restricted to values of N; for weighted periodic TILING, the reduction requires odd N, which remains NEXP-complete.The passage says the other restrictions used likewise yield hard subclasses of TILING.Source: §4 · p. 12
• The hardness constructions use a main layer that duplicates the given tiling rules, plus additional layers that force a structure reproducing standard TILING conditions.The additional layers’ details differ by construction.Source: §4 · p. 12

4.1 Boundary Conditions

• With only a designated upper-right corner tile, valid N × N tilings exist below a threshold N0 and fail at or above it, but N0 is uncomputable from the tile rules.Cropping the leftmost column and bottommost row turns any valid N × N tiling into one of size (N −1) × (N −1); deciding the variant for fixed rules would require knowing N0.Source: §4.1 · p. 12
• Fixing tiles in two corners already suffices for hardness, whether the corners are adjacent or opposite.For opposite corners, unique corner tiles create a boundary; for adjacent corners, modified rules prevent a new Turing-machine head from appearing at the right edge.Source: §4.1 · p. 12
• PERIODIC TILING is NEXP-complete under an expected polynomial-time randomized reduction or a deterministic polynomial-space reduction.Consequently, a poly(N)-time algorithm for it would imply EXP = NEXP.Source: §4.1 · p. 13
• For odd-prime N, layered tiles force unique internal borders and square regions, allowing the data layers to enforce the usual four-corner boundary conditions.The construction uses checkerboard and diagonal constraints to ensure a single (N −1)×(N −1) square on layer 1.Source: §4.1 · pp. 13, 15
• The reduction encodes input x by choosing a prime N in a range whose most significant bits reveal x, findable by exhaustive search in polynomial space or random search in expected poly(log x) time.The interval contains a prime, and the prime density makes random selection succeed with probability about 1/log(N0(x)).Source: §4.1 · p. 16

4.2 Weighted Constraints

• The problem asks whether an N × N tiling has total edge-weight cost at most p(N), with integer horizontal and vertical weights and binary N as input.Shifting all weights by a constant shifts total cost by 2rN(N −1), so the proof assumes p(N) = o(N^2).Source: §4.2 · p. 16
• WEIGHTED TILING is NEXP-complete with four-corners, open, or periodic boundary conditions.For four-corners boundaries, the result follows immediately from unweighted TILING.Source: §4.2 · p. 16
• For open boundaries, the reduction adds a five-tile special layer whose minimum-cost arrangement enforces the original tiling’s corner conditions.The construction uses weights 0, +2, +4, and −1 with c = −4; the optimal new layer has total cost −4.Source: §4.2 · pp. 16–17
• For periodic boundaries on odd N, weights 0, +1, and +3 with c = +2 force a single horizontal and vertical line whose crossing sets the grid boundary.The lines determine an (N −1) × (N −1) grid, with corner conditions set through adjacency to the special tiles.Source: §4.2 · pp. 17–18

• Both 1-DIM TILING and WEIGHTED 1-DIM TILING are solvable in polynomial time.The proof seeks a polylogarithmic-time algorithm in N by representing tile sequences as paths in a fixed-size graph.Source: §4.3 · p. 18
• A tiling path can be decomposed into a simple path and simple cycles, leaving only constantly many simple paths and allowed cycle sets to consider.The algorithm searches over these fixed possibilities and determines how many copies of each cycle are needed to reach length N.Source: §4.3 · pp. 18–19
• For each unweighted path and allowed cycle set, reaching the remaining length reduces to a fixed-set unbounded knapsack problem, handled by a gcd test for large targets and lookup for small ones.The lookup suffices for small targets because the relevant least common multiple is constant.Source: §4.3 · p. 19
• In the weighted case, the same length decomposition yields a fixed-set cost-minimization problem, using the cheapest cycle per length and an lcm-based lookup and cycle-ratio strategy.For sufficiently large residual lengths, the algorithm adds copies of a minimum-cost-per-length cycle to an optimal smaller solution.Source: §4.3 · pp. 19–20

4.4 Additional Symmetry

• For reflection-symmetric constraints, there are even and odd thresholds Ne and No: all sizes at or above the corresponding threshold tile, while smaller sizes do not, except N=1.Either threshold may be ∞.Source: §4.4 · p. 20
• With open boundaries, either Ne=No=∞ or both equal 1; with four-corner boundaries, No=3 or both thresholds are ∞; periodically, Ne=2 or both are ∞.Source: §4.4 · pp. 20–21
• With rotation symmetry, Ne and No are computable for any boundary conditions.It suffices to find minimum even- and odd-length tilings of a single side, then use those tilings on all four sides and fill the center with diagonal stripes.Source: §4.4 · pp. 21–22
• For reflection symmetry without rotation symmetry, whether Ne and No are computable remains unresolved for four-corner and periodic boundaries, respectively.Source: §4.4 · p. 21
• Reflection symmetry lets a valid tiling of size N≥4 extend to size N+2 by repeating existing patterns.The construction strips the leftmost column and bottommost row, duplicates adjacent rows and columns, and fills the corner from a 2×2 square.Source: §4.4 · p. 21

4.5.1 Open or Four Corners Boundary Conditions

• WEIGHTED TILING is NEXP-complete with either open boundary conditions or boundary conditions fixed at the corners.The construction is described for open boundaries, with the same costs implying fixed corner tiles.Source: §4.5.1 · p. 22
• The satisfying tilings used in the proof have total cost linear in N, and the authors do not prove these boundary-condition results for a constant cost function.The paper notes costs can always be shifted so that p(N) = o(N^2).Source: §4.5.1 · p. 22
• Three extra layers break reflection symmetry locally: Layer 1 has four optimal reflected orientations, while Layers 2 and 3 extend horizontal and vertical direction cues throughout the grid.Layers 2 and 3 use only weights 0 and +30 for forbidden pairings; most nontrivial weights occur in Layer 1.Source: §4.5.1 · p. 23
• For sufficiently large N, the optimal Layer 1 tiling has cost 76 −16N.The construction restricts N to N ≡4 mod 6.Source: §4.5.1 · pp. 23, 31
• At the open-boundary minimum cost, Layer 2 rules select one of four rotations of a Layer 1 tiling, while the other optimal arrangements cannot be extended.For a selected rotation, Layer 2 cycles among three tile types across columns; Layer 3 cycles among three types across rows, letting the main layers distinguish directions.Source: §4.5.1 · pp. 31–33
• For open or four-corner boundaries, a yes instance achieves cost 76 −16N, whereas a no instance must cost more.This holds when Layer 1 is optimal and the auxiliary layers have no forbidden pairings.Source: §4.5.1 · p. 33

4.5.2 Periodic Boundary Conditions

• For periodic reflection-symmetric tiling, constant costs and even N yield polynomial-time solvability, while linear costs are NEXP-complete.For constant costs, sufficiently large even and odd sizes have computable thresholds beyond which tilings exist; for even N, the problem is in P for any cost function.Source: §4.5.2 · p. 33
• For periodic boundaries with linear costs, a four-layer construction achieves cost 6N −2 exactly when the encoded instance is a yes instance.The construction considers odd N divisible by 3; Layer 4 defines an (N −1) × (N −1) interior for the main-layer tiling.Source: §4.5.2 · pp. 34, 38

4.6 Weighted Tiling with Rotation Symmetry

• With open boundaries, a computable N0 separates a range where tiling is always possible from one where it is always impossible, in either order.N0 depends on the tile weights and maximum allowed cost p(N).Source: §4.6 · p. 38
• With periodic boundaries, tiling is eventually always possible, eventually always impossible, or possible for every even N and all odd N above a computable threshold.The odd-N threshold may be infinite.Source: §4.6 · p. 38
• With four-corners boundaries, computable thresholds separately determine whether tilings exist for all sufficiently large even N and for all sufficiently large odd N.For each parity, tilings either exist for every size above its threshold or for none; either threshold may be infinite.Source: §4.6 · p. 38
• For four-corners boundaries, the algorithm enumerates low-cost corner squares and tests their compatibility, then fills the remaining grid with tiles from a zero-cost connected component.When zero-cost pairings exist but no negative-cost pairings do, a bounded-cost tiling must have compatible corner squares of sizes c through 2c; compatible squares suffice for filling sufficiently large grids.Source: §4.6 · pp. 39–40

5.1 Preliminaries

• A reversible binary counter and padded verifier underpin a chain Hamiltonian with unique ground-state energy at most p(N) for yes instances and at least p(N)+1/q(N) for no instances.The verifier’s acceptance and rejection probabilities are amplified to 1−ε and ε, respectively, with ε=1/poly(N).Source: §5.1 · pp. 41–42

5.2 Outline of the Construction

• In the construction outline, Track 1’s arrow makes round trips while Track 2 advances the clock; sweeps trigger counter and verifier steps, and a final-state penalty requires acceptance for low energy.Each Track 1 sweep triggers a step of MBC, while Track 2’s computation phase triggers steps of verifier V.Source: §5.2 · p. 43

5.3 The Clock Tracks

• Track 1 shuttles across the chain in 2(N−2)-state iterations, advancing Track 2 through ordered counting states and then computation states until the clock’s final state.Track 2’s counting phase uses states of form 1*¯0 0*, and its computation phase uses states of form 1*¯1 2*; each Track 1 iteration advances it once.Source: §5.3 · pp. 44–46
• Well-formed states are closed under the transition rules, with at most one applicable rule in each of the forward and reverse directions.Source: §5.3 · p. 49
• Every well-formed state outside |φcl⟩’s support reaches a state with an illegal pair within 2N transition steps, forward or backward.Source: §5.3 · p. 49
• |φcl⟩ is the unique ground state of HN restricted to Sbr, and every other eigenstate has energy at least Ω(1/N^3).The path corresponding to |φcl⟩ has length O(N^2) and no illegal states; every other path has an illegal-state fraction of at least 1/(2N).Source: §5.3 · p. 51
• Track 2 records time, moving Track 1 from counting to computation and stopping it at the end of the computation phase.Source: §5.3 · p. 51

5.4 Initialization Phase

• Track 3 is initialized to blank symbols by forbidding nonblank symbols when Track 1 is in → 0.Source: §5.4 · p. 51
• Track 4 is constrained to start MBC in its designated start state at the initial location and blank elsewhere; Track 5 is initialized similarly for V.Illegal-state and pair constraints enforce the initial configuration for Track 4.Source: §5.4 · pp. 51–52
• Track 6 may contain any state on n qubits as V’s quantum witness, and each particle state is specified by a 6-tuple.Source: §5.4 · p. 52

5.5 Counting Phase

• Each left-to-right →1 sweep advances MBC once, so it runs exactly N−2 steps; →2 triggers a step of V, described in the more general quantum Turing-machine case.MBC is a classical reversible Turing machine and a special case of a quantum Turing machine.Source: §5.5 · p. 52

5.6 Computation Phase

• Applying T to a particle pair maps its computation state from SA into SB, allowing the transition rule to advance to the next pair.The extended map acts on pairs in turn to implement a Turing-machine step.Source: §5.6 · pp. 52–53
• Right-moving head transitions are split into two steps: a primed state defers movement until the control arrow reaches the new location.Left moves execute when the arrow moves from the position left of the head; the subsequent step moves a primed right-moving head and converts it to its unprimed state.Source: §5.6 · pp. 52–53
• T is a partial isometry from SA to SB, enabling its extension to a unitary and construction of the corresponding Hamiltonian term.The term combines projectors onto SA and SB with T and its adjoint, conditioned on the Track 1 arrow state.Source: §5.6 · p. 53
• Invalid states receive an energy penalty of at least one, while valid, well-formed states remain within the transition rules’ reversible, norm-preserving subspace.For such states, the rules act non-trivially on only one particle pair.Source: §5.6 · p. 54

5.7 Combining the Tracks

• Combined transitions advance the clock one tick while updating one Turing-machine step, and reverse transitions uniquely undo each noninitial tick.For valid computation-track states and nonfinal clock states, exactly one particle pair is acted on in the forward direction.Source: §5.7 · p. 54
• For combined tracks, |φX,Y⟩ superposes the clock states with the computation-track state after each transition, satisfying transition and illegal-state constraints.Tracks 3–5 begin in basis state X and Track 6 in Y.Source: §5.7 · p. 54
• Within Sbr, only |φI,Y⟩ states span the zero eigenspace; any X ≠ I incurs initialization energy, and the next eigenstate has energy Ω(1/N^3).The initialization configuration I has ∗ on Track 3 and s∗ on Tracks 4 and 5.Source: §5.7 · p. 54

5.8.1 The Finite Chain

• For the finite chain, the ground space is spanned by |φI,Y⟩ states and the spectral gap remains Ω(1/N^3).A term penalizing unbracketed states makes each standard basis state outside Sbr cost at least N − 1.Source: §5.7 · p. 54, §5.8.1 · p. 55

5.8.2 The Cycle

• On the cycle, added Track 0 penalties isolate states with exactly one segment and a co-located marker, leaving other eigenstates at least one energy higher.Odd N and alternating A/B Track 0 states are used to enforce the single-segment condition.Source: §5.8.2 · pp. 55–56
• In a chosen low-energy cycle subspace, |φI,Y⟩ has energy 1/2 and all other eigenstates have energy at least 1/2 + Ω(1/N^3).There are 2N low-energy Track 0 arrangements, and each defines a closed subspace with identical behavior under the other terms.Source: §5.8.2 · p. 56

5.9 Accepting States

• The accepting-state term gives accepting computations energy at most ε/N^2, while if no witness accepts, every state has energy at least (1 − ε)/N^2.The penalty tests whether the rightmost particle in the final clock configuration has Track 5 state qA; ε can be made arbitrarily small.Source: §5.9 · p. 56

6 Quantum Case With Reflection Symmetry

• The reflection-symmetric 1-DIM TIH problem is QMA_EXP-complete, using arrow states to break reflection symmetry locally and enforce ground-state configurations that support the computation.The construction is given for periodic boundary conditions, with a similar construction for open boundaries; choosing c = 5 gives an energy gap of at least one between configurations satisfying the required properties and those that do not.Source: §6 · pp. 56–58

6.1 Track 1 Transitions

• Track 1 swaps its control particle with adjacent non-control states, forming a loop of 2(n −1) correctly oriented states alongside a reflected, incorrectly oriented copy.The two transition sets are closed and have identical structure, allowing analysis of one orientation.Source: §6.1 · pp. 58–59

6.2 Track 2

• Track 2 preserves well-formed clock states, whose subspace has a unique ground state: the uniform superposition over valid clock states.Reflection-symmetric illegal-pair constraints penalize paths that are not well-formed, giving them energy at least 1/poly(n) above the valid-clock superposition.Source: §6.2 · p. 60

6.3 Turing Machine Initialization

• Track 4 and Track 5 constraints place the unique Turing-machine head at the left end of the chain in its designated start state.The rules tie the head position to Track 1 arrow states and enforce the same condition for Track 5.Source: §6.3 · p. 61

6.4 Turing Machine Implementation

• Turing-machine transition rules are expanded for A- and B-version states and reflected, with the control-particle direction ensuring that only the correct rules apply.Source: §6.4 · p. 61

7 The Infinite Chain

• The construction varies the fixed-form two-particle Hamiltonian coefficients at O(log N)-bit precision to make the infinite chain break into segments of size N.The Hamiltonian’s size-favoring term uses coefficients that are inverse polynomials in N.Source: §7 · pp. 61–63
• The energy per particle is well-defined in the infinite-chain limit: restricting the ground state to M particles changes the energy by a constant boundary correction, or O(1/M) per particle.The passage allows periodic or open boundary conditions and takes M → ∞.Source: §7 · p. 62
• An added track enforces N = 3 mod 4, so the verifier reads (N − 3)/4; otherwise the ground-state energy is at least Ω(1/N^3).The verifier erases the two least significant input bits, requiring approximately 2 log N steps.Source: §7 · p. 62
• A segment of length N has ground-state energy at most 0 and spectral gap Ω(1/N^4) per particle, while every other segment length has ground-state energy Ω(1/N^9) per particle.These bounds apply to well-formed bracketed states, under the section’s assumption N = 3 mod 4.Source: §7 · p. 64
• If no quantum witness makes the verifier accept input (N − 3)/4 with probability greater than ε, the restricted Hamiltonian’s ground-state energy is at least Ω(1/N^3) per particle.Source: §7 · p. 65

• The paper proves tiling and one-dimensional quantum Hamiltonian problems remain hard with translationally invariant rules and system size as the only input, although the constructions are not especially natural.Source: §8 · p. 65
• The framework offers a way to study which Hamiltonians are computationally hard, but the techniques answer that question only in special cases.For the infinite-chain example, a sequence of hard Hamiltonians converges to a non-hard Hamiltonian lacking the Hsize term, whose ground-state energy is 0 when the chain has no segments or control particles.Source: §8 · pp. 65–66
• The authors conjecture that these systems may have complicated finite-temperature dynamics resembling a spin glass, but say this behavior is uncertain.Their motivation is that the hard constructions have a complicated energy landscape and ground states highly sensitive to the exact particle count.Source: §8 · p. 66
• Open questions include borderline tiling variants, rotationally and translationally invariant Hamiltonians in multiple dimensions, and a classical hardness result for ITIH.Weighted tiling with reflection symmetry and constant allowed cost remains unresolved for four-corners or open boundaries; the 1-DIM TIH reflection construction does not extend to 2-DIM TIH with rotational invariance, and ITIH hardness currently relies on quantum properties.Source: §8 · p. 66
• The authors propose studying optimal play in Go from an empty N × N board, asking whether this size-only variant is EXPSPACE-complete, though their techniques do not solve it.Unlike GO, which takes a particular board configuration as input, the proposed problem fixes the rules and initial configuration and varies only board size.Source: §8 · p. 66