RECORD
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
Quantum Physics · Submitted 14 May 2009
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that the classical problem is NEXP-complete and the quantum problem is QMA_EXP-complete.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We study the complexity of a class of problems involving satisfying constraints which remain the same under translations in one or more spatial directions. In this paper, we show hardness of a classical tiling problem on an N x N 2-dimensional grid and a quantum problem involving finding the ground state energy of a 1-dimensional quantum system of N particles. In both cases, the only input is N, provided in binary. We show that the classical problem is NEXP-complete and the quantum problem is QMA_EXP-complete. Thus, an algorithm for these problems which runs in time polynomial in N (exponential in the input size) would imply that EXP = NEXP or BQEXP = QMA_EXP, respectively. Although tiling in general is already known to be NEXP-complete, to our knowledge, all previous reductions require that either the set of tiles and their constraints or some varying boundary conditions be given as part of the input. In the problem considered here, these are fixed, constant-sized parameters of the problem. Instead, the problem instance is encoded solely in the size of the system.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study the complexity of a class of problems involving satisfying constraints which remain the same under translations in one or more spatial directions. | background 0.72 | 0.65 | 0.03 | asserted 0.81 |
| s1 | In this paper, we show hardness of a classical tiling problem on an N x N 2-dimensional grid and a quantum problem involving finding the ground state energy of a 1-dimensional quantum system of N particles. | contribution 0.79 | 0.95 | 0.23 | asserted 1.00 |
| s2 | In both cases, the only input is N, provided in binary. | contribution 0.39 | 0.70 | 0.03 | asserted 1.00 |
| s3 | We show that the classical problem is NEXP-complete and the quantum problem is QMA_EXP-complete. | result 0.99 | 0.95 | 0.80 | asserted 1.00 |
| s4 | Thus, an algorithm for these problems which runs in time polynomial in N (exponential in the input size) would imply that EXP = NEXP or BQEXP = QMA_EXP, respectively. | interpretation 0.99 | 0.77 | 0.18 | asserted 0.84 |
| s5 | Although tiling in general is already known to be NEXP-complete, to our knowledge, all previous reductions require that either the set of tiles and their constraints or some varying boundary conditions be given as part of the input. | gap 0.83 | 0.08 | 0.05 | asserted 0.98 |
| s6 | In the problem considered here, these are fixed, constant-sized parameters of the problem. | contribution 0.80 | 0.58 | 0.05 | asserted 1.00 |
| s7 | Instead, the problem instance is encoded solely in the size of the system. | contribution 0.89 | 0.76 | 0.08 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We study the complexity of a class of problems involving satisfying constraints which remain the same under translations in one or more spatial directions. In this paper, we show hardness of a classical tiling problem on an N x N 2-dimensional grid and a quantum problem involving finding the ground state energy of a 1-dimensional quantum system of N particles. In both cases, the only input is N, provided in binary. We show that the classical problem is NEXP-complete and the quantum problem is QMA_EXP-complete. Thus, an algorithm for these problems which runs in time polynomial in N (exponential in the input size) would imply that EXP = NEXP or BQEXP = QMA_EXP, respectively. Although tiling in general is already known to be NEXP-complete, to our knowledge, all previous reductions require that either the set of tiles and their constraints or some varying boundary conditions be given as part of the input. In the problem considered here, these are fixed, constant-sized parameters of the problem. Instead, the problem instance is encoded solely in the size of the system.
Human review
References
How the literature uses it
11 arXiv papers cite this in 27 sentences
Papers citing it · 18 sentences without a confident label
Uses its method or tool 2 papers
-
As a second step, we employ a boundary trick by [ref] to ensure that blocks not terminated by a boundary marker have a ground state energy at least $2$ higher than $$-terminated blocks.
Undecidability of the Spectral Gap in One Dimension · Construction · 0.99
-
Furthermore, we use an idea from [ref] to first run a binary counter TM which computes the length of the tape it is running on in binary, and feeds this as input to the machine.
Computational Complexity of the Ground State Energy Density Problem · Proof techniques · 0.97
Cites it as background 4 papers
-
Gottesman and Irani [ref] proved that the ground state energy density problem for translationally invariant, nearest-neighbour, quantum Hamiltonians on a 1D chain with a $Ω(1/2^n)$ promise-gap is -complete.
Computational Complexity of the Ground State Energy Density Problem · Related work · 0.86
-
While it is known that approximating a 1D quantum system's ground state energy to inverse polynomial precision is in general QMA hard [ref] —even with translationally-invariant nearest neighbour interactions [ref] —currently there are no examples of gapped QMA-hard Hamiltonians and and there are indications [ref] that gaplessness is required in order to have a hard to compute ground state energy.
Undecidability of the Spectral Gap in One Dimension · Introduction · 0.83
-
Since then there have been several developments showing that simpler classes of local Hamiltonians are still hard [ref] , culminating in the $$-completeness of the problem for Hamiltonians on a line [ref] even when all the local terms are the same and the only input is the length of the line expressed in unary [ref] .
Product-state Approximations to Quantum Ground States · Background · 0.88
What it cites · 6 sentences without a confident label
Builds on 1 paper
-
As a corollary of Theorem [ref], the following version of $N$-REPRESENTABILITY [ref] is also $$-complete: Given a density matrix $ρ$ on two $d$-state particles, is it within $ϵ$ of a state $ρ'$ such that there exists a translationally-invariant pure state $|ψ⟩$ for $N$ particles arranged in a circle for which $ρ'$ is the marginal state of two adjacent particles? $ρ$ is a parameter of the problem, and $N$, given in binary, is the only input, as in our Hamiltonian problem.
N-representability is QMA-complete · Problems and Results · 0.93
Uses the method or tool of 1 paper
-
When $ϵ$ is small enough (polynomially small is sufficient), using standard $$-completeness proof techniques (see, e.g. [ref] ), we can show that there will be an energy penalty of at least $Ω(1/T_N^2)$ for that segment, which is $Ω(1/N^5)$ per particle.
The power of quantum systems on a line · The Infinite Chain · 0.87
Cites as background 1 paper
-
Some other systems with “self-induced disorder” have been introduced previously, although not in the context of computational complexity [ref] .
Self Induced Quenched Disorder: A Model for the Glass Transition · Introduction · 0.97
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.