The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete

Daniel Gottesman; Jon Nelson

REVIEW 4 major objections 6 minor 14 references

For every fixed lattice dimension, deciding the ground-state energy of a single fixed rotation-invariant two-qudit term on an n×...×n torus is QMAEXP-complete, even with a constant promise gap.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

The rotation-invariant local Hamiltonian problem in any fixed lattice dimension is QMAEXP-complete.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection The EPR-monogamy trick is genuinely nice, but Theorem 5's constant gap is not supported by the proof; the result is likely fixable and worth refereeing. the 4 major comments →

arxiv 2509.00161 v1 pith:6IRWZTWQ submitted 2025-08-29 quant-ph cs.CC

The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete

Jon Nelson , Daniel Gottesman This is my paper

classification quant-ph cs.CC MSC 81P6868Q17 PACS 03.67.Lx

keywords rotation-invariant HamiltonianQMAEXP-completenesslocal Hamiltonian problemmonogamy of entanglementtiling constraintstranslation-invariant Hamiltonianquantum many-body complexityground-state energy problem

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper settles the decade-old question of whether rotation invariance erases the computational hardness of lattice Hamiltonians. It shows that for every fixed lattice dimension r, the rotation-invariant Hamiltonian problem is QMAEXP-complete: deciding whether a single fixed two-qudit interaction, repeated on all nearest-neighbor edges of an n×…×n torus, has ground-state energy below a threshold or at least one above it is as hard as any problem a quantum verifier could solve with exponential time and an exponentially large witness. This matters because it pins down the intermediate regime between one-dimensional spin chains, which are hard, and the infinite-dimensional mean-field limit, where product states become exact. The proof's engine forces low-energy states to self-organize into straight directed loops that simulate a computation, and it yields a quantitative lower bound on how badly product states approximate the ground-state energy, complementing known mean-field upper bounds.

Core claim

The central claim is Theorem 5: for every fixed lattice dimension r, the rotation-invariant Hamiltonian problem is QMAEXP-complete with a constant promise gap q(n)=1. That is, fix a single permutation-invariant two-qudit term h; on an n×⋯×n periodic lattice, decide whether E0(H)≤p(n) or E0(H)≥p(n)+1, with n given in binary. The proof first forces low-energy states, through tiling rules and monogamy of entanglement, to be disjoint straight consistently numbered loops that select two perpendicular axes, carving the lattice into 2D slices. It then embeds a 2D translation-invariant non-reflection-invariant Hamiltonian—constructed in Appendix A from [GI13]'s machinery—into those slices, which sim

What carries the argument

Each site carries two classical tile registers (a color and a number, duplicated twice) plus two qubits. A fixed two-body term rewards same-colored neighbors that share an EPR pair through the ordered qubits and penalizes other configurations; since a site has only two qubits, monogamy of entanglement caps same-colored neighbors at two, forcing low-energy tilings into disjoint loops. Further terms (coefficients 2, 8, 16) remove open chains, turns, mixed directions, and inconsistent numbering, leaving straight, uniformly directed, consistently numbered loops. Those loops select two perpendicular axes, carving the lattice into 2D slices into which a 2D translation-invariant Hamiltonian is embe

Load-bearing premise

The soundness proof relies on the claim that every low-energy tiling must be a set of straight, uniformly directed, consistently numbered loops (with penalties of at least 1, 4, or 8 for any deviation), and on the deferred 2D translation-invariant Hamiltonian of [GI13] delivering the assumed O(n^{-k}) vs Ω(1/n^3) gap; if either gives way, the constant gap q(n)=1 is not established.

What would settle it

Enumerate all tile and number assignments for a small allowed lattice (e.g., r=3, n=6 or 15) and numerically minimize the qubit degrees of freedom: if any tiling that is not straight, uniformly directed, and consistently numbered achieves energy below 4n^r(r−1)+1, the soundness lemmas fail. Alternatively, either prove Theorem 25 in full or exhibit an x∉L instance whose 2D translation-invariant Hamiltonian has ground-state energy below the promised Ω(1/n^3) after the 3×3 block simulation.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

For any fixed r, the problem remains QMAEXP-complete with promise gap 1: the full hardness of exponentially verifiable quantum problems is reproduced by one fixed two-qudit term as n grows.
Under standard complexity assumptions, no efficient quantum algorithm can solve this ground-state problem; physically, the low-energy landscape is hard enough to prevent the system from finding its own ground state, a spin-glass-like signature.
If QCMAEXP ≠ QMAEXP, the ground states have no efficient classical description and product-state approximations are provably poor, with per-term error Ω(n^{-r} r^{-1}), complementing the mean-field upper bound of [BH13].
The construction also works with open boundary conditions, so the hardness does not depend on the lattice being periodic.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Beyond the paper's direct claims, the loop/EPR gadget looks portable: the same monogamy-based constraint could be used to embed other low-dimensional geometries—planar circuits, interfaces, or fault-tolerant layouts—into rotation-invariant lattices.
The paper leaves implicit that the sharpest open question is the transition between fixed r (hard) and r→∞ (easy); the proof techniques do not yet determine whether hardness disappears gradually or at a threshold as r grows with n.
If Theorem 25 were proved in full rather than deferred, the construction would yield an explicit one-parameter family of fixed interaction terms whose ground-state energy problem is hard at every allowed lattice size—a concrete stress test for quantum optimizers and simulation algorithms.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

The EPR-monogamy trick is genuinely nice, but Theorem 5's constant gap is not supported by the proof; the result is likely fixable and worth refereeing.

read the letter

Two things to know. First, the core technique — two EPR qubits per site to force same-colored loops, then a classical tiling layer to straighten them — is a real idea and the best part of the paper. It gives a way to embed a lower-dimensional geometry inside a rotation-invariant lattice without adding symmetry-breaking terms. Second, the main theorem as stated does not follow from the proof. The completeness bound in Lemma 8 is E0 ≤ 4n^r(r−1)+1/g(n) for any g, and the soundness bound in Claim 23 is E0 ≥ 4n^r(r−1)+Ω(n^{r−5}). For r=2,3,4 the soundness surplus vanishes, so no polynomial p(n) can satisfy the promise with q=1: the yes-case energy is strictly above the baseline, while the no-case lower bound is only baseline plus o(1). The proof of Lemma 8 even states the upper bound for 'any polynomial g', which is impossible for a fixed instance unless the Hamiltonian is allowed to depend on g. This is a quantitative overclaim, not a collapse of the approach: choosing q(n)=n^4 or so should restore the gap.

What the paper does well: the high-dimensional tiling (stripes along one coordinate, numbering mod 3, the copy trick to get a second direction) is carefully worked out, and the reduction to a 2D translation-invariant Hamiltonian is a sensible way to inherit hardness from [GI13]. The mean-field discussion in the intro frames the result properly. The classification of tile states (looped, straight, uniformly directed, consistently numbered) is plausible and the penalty bookkeeping is mostly explicit.

Soft spots besides the gap: Appendix A is a sketch. Theorem 25 is load-bearing and is not proved in the paper; it points to [GI13] and gives an outline with unrendered figures. A referee will need the full construction. Also, Claims 18–22 assert penalties of 4 or 8 without an exhaustive case analysis; I'd want those tightened, though they look fixable.

Bottom line: this is a promising paper with a genuinely new technique and a correct-looking overall strategy, but the advertised constant gap is not proven. I'd send it to a serious referee with instructions to focus on the promise-gap issue and the appendix. If the authors adjust q(n) and fill in the 2D Hamiltonian details, the result should be a solid answer to the open question from [GI13]. I wouldn't cite it in its current form.

Referee Report

4 major / 6 minor

Summary. The paper claims to resolve an open question of Gottesman and Irani by proving that the rotation-invariant Hamiltonian problem on an r-dimensional periodic lattice of side length n is QMAEXP-complete for every fixed r, with a promised gap of exactly 1 (q(n)=1). The construction attaches two tile systems and two qubits per site to a single two-body, rotation-invariant interaction term. Tile rules plus EPR-pair constraints force the ground-state configurations to consist of straight, uniformly directed loops, thereby carving out 2D slices in which a translation-invariant 2D Hamiltonian can be embedded. The 2D Hamiltonian is then used to host a 1D quantum Turing machine construction from prior work. Completeness and soundness are argued through a sequence of claims about tiling energies, with the technical 2D Hamiltonian construction deferred to an appendix.

Significance. If the proof can be completed and the claimed parameters justified, the result would be significant: it would show that a single fixed interaction term, applied uniformly over a lattice of growing side length, yields QMAEXP-hard ground-state-energy estimation in any fixed dimension, answering an open question and complementing mean-field/product-state easiness results in high dimensions. The EPR-monogamy method for forcing one-dimensional geometry in a rotation-invariant setting is a novel and potentially reusable technique. The paper also claims a lower bound on product-state approximation error. However, the central quantitative claims—especially the constant promise gap and the soundness argument for low dimensions—are not supported by the supplied estimates, and the main 2D Hamiltonian is only sketched. The core idea is promising, but the manuscript needs substantial revision before the advertised theorem can be accepted.

major comments (4)

[§4.1 (Lemma 8) and Theorem 5] The claimed constant promise gap q(n)=1 is not established. Lemma 8 gives, for a yes-instance, E0(H) ≤ 4nr(r−1) + 1/g(n) for an arbitrarily large polynomial g(n), while Lemma 9 gives, for a no-instance, E0(H) ≥ 4nr(r−1) + 1. For q=1, any admissible polynomial p(n) must satisfy p(n) ≤ 4nr(r−1), because the no-case lower bound forces p(n)+1 ≤ 4nr(r−1)+1. But the yes-case is only shown to be below 4nr(r−1)+1/g(n), which is strictly above 4nr(r−1) for every finite n; the embedded 2D term contributes strictly positive energy, so E0(H) > 4nr(r−1) is not excluded. Thus no fixed polynomial p(n) can simultaneously separate the two cases with gap exactly 1. The phrase 'for any polynomial g' does not repair this, since a fixed p must be chosen independently of the instance. This is a load-bearing gap in the statement of Theorem 5.
[§4.2 (Claim 23 and Lemma 9)] Claim 23 only yields a no-case lower bound of 4nr(r−1)+Ω(n^{r−5}) for the numbered-consistent tilings. For r=2, 3, 4, the surplus Ω(n^{r−5}) is o(1), so it cannot imply the constant +1 required by Lemma 9. Even for r=5, the implicit constant in Ω(1) is not shown to be at least 1. Since Lemma 24 reduces the entire soundness proof to this claim, the soundness of the construction is not established for small lattice dimensions. This is not a cosmetic issue: a subconstant surplus cannot support any positive constant or polynomial promise gap in Definition 4. The authors need either a stronger no-case lower bound from the embedded 2D Hamiltonian or a dimension-dependent promise gap, which would be a different theorem.
[Appendix A (Theorem 6/25)] The central 2D translation-invariant Hamiltonian—with yes-case energy O(n^{-k}) and no-case energy Ω(1/n^3)—is the engine that ultimately determines the factor n^{r−5} in Claim 23, yet it is only sketched. The appendix says 'much of the proof will directly utilize techniques from [GI13]' and presents tiling rules using tile symbols that are not fully defined in the text. Because the scaling of this Hamiltonian's gap is load-bearing for the main theorem, a proof sketch is insufficient. Please provide a complete, self-contained proof of Theorem 6, or a precise reference to a theorem in [GI13] that establishes exactly these bounds with a constant-size alphabet and translation invariance.
[§4.2 (Claims 20 and 22)] The classification of low-energy tilings is under-argued at two key points. Claim 20 asserts that any looped, turn-free tiling that is not uniformly directed 'will necessarily arise' a specific local configuration (Fig. 5), but no proof is given that every such tiling contains that configuration; an unclassified tiling would break the subsequent lower bound. Claim 22 likewise asserts a penalty of at least 8 in two sentences, relying on the unstated claim that any inconsistency in numbering forces a penalty of at least 8. These claims are the backbone of the soundness proof for all non-tile and tile states, so they require rigorous local-case arguments rather than appeals to a figure.

minor comments (6)

[Definition 4 and Theorem 5] The theorem states q(n)=1 but does not explicitly name the polynomial p(n) for which the completeness holds. Given the sensitivity of the promise-gap argument to the exact form of p (see major comment above), the authors should state p(n) explicitly in the theorem.
[Equations (2)–(3)] The term hRI is written as a sum over T2 numbers only, while the text says it is applied 'only when the first copy tiles have the same color.' Since htile makes same-color and different-number conditions equivalent in valid tilings, this is correct only after htile is enforced. Please add a sentence clarifying the conditional semantics to avoid ambiguity.
[Claim 13 proof] The grouping argument says a violated htile edge costs '4 per particle involved (8 in total for the edge)' but then only uses a lower bound of 4. The logic is sound but the wording is confusing; consider stating directly that either htile or hEPR contributes at least 4.
[Appendix A] Several tile symbols (e.g., those marking the left endpoint of the 1D construction) are referenced through images that are not self-contained in the text. Provide explicit definitions or sufficiently detailed figure captions so the tiling rules can be reproduced without external images.
[Section 5] The open-boundary discussion is very brief and defers the 2D open-boundary theorem to Appendix A.2, which is again a sketch. Since the main theorem is for periodic boundary conditions this is not blocking, but the section should be clearly marked as a sketch or given a complete reference.
[Throughout] There are minor typographical issues (e.g., 'QMA EXP' in the abstract, 'Schr¨odinger' in the introduction). These do not affect the technical content.

Circularity Check

0 steps flagged

No significant circularity: the derivation is a standard reduction whose main external building block is imported from prior independent published work.

full rationale

The paper's central derivation is a reduction from QMAEXP to the rotation-invariant Hamiltonian problem. The load-bearing 2D translation-invariant Hamiltonian (Theorem 6 / Theorem 25) is taken from [GI13], a published prior result by one of the coauthors. Under the review rules this is independent support: it is peer-reviewed, does not assume the present rotation-invariant theorem, and its yes/no parameters are not fitted to the current problem. The in-paper structural claims (Claims 13-22) are proved from the explicit Hamiltonian terms and from Fact 11, a direct computation of a three-qubit projector; they do not presuppose the target completeness or soundness. The q(n)=1 promise issue flagged by the reader is a correctness concern, not a circularity: Lemma 8 gives E0 <= 4nr(r-1)+1/g(n), Lemma 9 gives E0 >= 4nr(r-1)+1, and for r=2,3,4 Claim 23's Omega(n^{r-5}) does not obviously reach the claimed +1, so the stated promise may be unsatisfiable. That would be an unsoundness or a false theorem, but it is not a case where a prediction is equivalent to its input by construction or where a fitted parameter is renamed as a prediction. The paper also openly labels Appendix A a proof sketch and defers details to [GI13]; that is a missing-proof limitation, which I weigh as a rigor risk, not as circular dependence. No equation in the derivation reduces to its own assumptions, so the circularity score is 0.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 2 invented entities

The construction introduces several hand-tuned coefficients (8, 16, 2) that are not derived from first principles but verified by inequalities. It also attaches artificial degrees of freedom (two EPR qubits, two copies of tile subspaces) to each site, which are computational scaffolding rather than physically motivated entities. The main external anchor is [GI13].

free parameters (3)

htile coefficient 8 = 8
Chosen by hand to balance competing EPR and loop penalties (Section 3.1).
hEPR coefficient 16 = 16
Chosen so that a monogamy violation costs 4 per group (Section 3.1.1, Fact 11).
hloop coefficient 2 = 2
Chosen so loop savings never outweigh EPR violation penalties (Section 3.1.2).

axioms (4)

domain assumption [GI13] 1D translation-invariant Hamiltonian is QMAEXP-complete and their 2D tiling construction (Theorem 25 in Appendix A) yields the required HTI gap.
The reduction's soundness and completeness inherit from Theorem 25, whose proof is a sketch referencing [GI13].
standard math Sabidussi's theorem: chromatic number of Cartesian product of cycles is the max, used for 3-colorability of (r-1)-lattice.
Used in Lemma 8 completeness tiling.
domain assumption Monogamy of entanglement constant (Fact 11): minimum eigenvalue 1/4 for two EPR projectors sharing one qubit.
Verified by direct computation; load-bearing for all EPR penalty claims.
domain assumption The Hamiltonian is block-diagonal in the tile basis, so the ground state can be taken as a tile state.
Used in Lemma 24; true because all terms act diagonally on tile spaces.

invented entities (2)

Two EPR qubits (sigma1, sigma2) per site no independent evidence
purpose: Force each site to have exactly two same-colored neighbors via monogamy, carving 1D chains.
Computational gadget, no external observable prediction.
Tile colors {red, yellow, blue} and numbers {0, 1, 2} on two copies no independent evidence
purpose: Define directed chains and two spatial directions for the embedded computation.
Internal to the Hamiltonian construction.

reviewed 2026-08-05 · how reviews work

0 comments

Cite this review

Pith. "Pith review of The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete." pith.science (2026). https://pith.science/paper/6IRWZTWQ

@misc{pith2026250900161,
  author       = {Pith},
  title        = {Pith review of: The rotation-invariant Hamiltonian problem is QMA$_\rm EXP$-complete},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6IRWZTWQ}},
  note         = {Machine review of arXiv:2509.00161}
}

Share X Bluesky LinkedIn Reddit HN

abstract

In this work, we study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice and are invariant under translations and rotations of the lattice. In the one-dimensional case this problem is known to be QMA$_{\rm EXP}$-complete. On the other hand, if we fix the lattice length then in the high-dimensional limit the ground state becomes unentangled due to arguments from mean-field theory. We take steps towards understanding this complexity spectrum by studying a problem that is intermediate between these two extremes. Namely, we consider the regime where the lattice dimension is arbitrary but fixed and the lattice length is scaled. We prove that this rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete answering an open question of [Gottesman, Irani 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity.

Figures

Figures reproduced from arXiv: 2509.00161 by Daniel Gottesman, Jon Nelson.

**Figure 1.** Figure 1: When a chain of sites is numbered sequentially around the cycle Z3, each qubit is matched with exactly one other qubit to form an EPR pair, and so the EPR constraint can easily be satisfied. 3.1.1 EPR projections Next, we would like to enforce that the qubits of same-colored neighbors form EPR pairs with each other. We can do this by attaching the following two additional Hilbert spaces to each site: Hσ1 ⊗… view at source ↗

**Figure 2.** Figure 2: When there are three consecutive same-color neighbors that are not numbered monotonically around Z3 (for instance 0, 1, 0) then two different qubits are matched with the same qubit to form an EPR pair. Due to the monogamy of entanglement this constraint cannot be satisfied and incurs an energy penalty. so we add another term to enforce periodic boundary conditions. In particular, we define the following te… view at source ↗

**Figure 3.** Figure 3: An example of how a 2D lattice can be tiled to optimize the Hamiltonian terms. Specifically, each copy forms a striped pattern where each stripe is numbered in a cyclic sequence. In addition, the two copies of tiles must have stripes pointing in different directions. Finally, the rows/columns that do not hold stripes must be numbered with the same number. Now a translation-invariant Hamiltonian can be simu… view at source ↗

**Figure 4.** Figure 4: Two examples of how energy penalties can arise when there is a turn in the loop. Here, the loop consists partially of u, v, and w which contains a turn since u and w differ in more than one coordinate. In (a), z is colored the same as the rest but this results in a penalty since a loop of size 4 cannot be numbered cyclically around Z3. This results in the illegal configuration of u and v having the same co… view at source ↗

**Figure 5.** Figure 5: This configuration always arises if the tiling is not uniformly directed since otherwise each loop is always pointed in the same direction. This causes a rule violation since the blue and yellow tiles must have the same number but are forced to hold different numbers due to the red tiles. So far we have given a sufficient lower bound for any tile states that do not consist of only straight loops. It will b… view at source ↗

**Figure 2.** Figure 2: A possible arrangement of layers 1 (a.) and 2 (b.) for PERIODIC T An example of an allowed configuration for a given set of translation-invariant tiling rules on a 2D grid defined in [ [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

**Figure 8.** Figure 8: The only allowed configuration for the given set of translation-invariant tiling rules on a 2D grid with open boundary conditions. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 12 canonical work pages · 3 internal anchors

[1]

Commuting Local Hamiltonians on Expanders, Locally Testable Quantum codes, and the qPCP conjecture

Dorit Aharonov and Lior Eldar. Commuting local hamiltonians on expanders, locally testable quantum codes, and the qpcp conjecture, 2013. URL: https://arxiv.org/abs/1301.3407, https://arxiv.org/abs/1301.3407 arXiv:1301.3407

work page internal anchor Pith review Pith/arXiv arXiv 2013
[2]

The power of quantum systems on a line

Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. The power of quantum systems on a line. Communications in Mathematical Physics , 287(1):41–65, January 2009. URL: http://dx.doi.org/10.1007/s00220-008-0710-3, https://doi.org/10.1007/s00220-008-0710-3 doi:10.1007/s00220-008-0710-3

doi:10.1007/s00220-008-0710-3 2009
[3]

Cubitt, and James D

Johannes Bausch, Toby S. Cubitt, and James D. Watson. Uncomputability of phase diagrams. Nature Communications , 12(1), January 2021. URL: http://dx.doi.org/10.1038/s41467-020-20504-6, https://doi.org/10.1038/s41467-020-20504-6 doi:10.1038/s41467-020-20504-6

doi:10.1038/s41467-020-20504-6 2021
[4]

Brandao and Aram W

Fernando G.S.L. Brandao and Aram W. Harrow. Product-state approximations to quantum ground states. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing , STOC '13, page 871–880, New York, NY, USA, 2013. Association for Computing Machinery. https://doi.org/10.1145/2488608.2488719 doi:10.1145/2488608.2488719

work page arXiv 2013
[5]

The complexity of translationally invariant low-dimensional spin lattices in 3d

Johannes Bausch and Stephen Piddock. The complexity of translationally invariant low-dimensional spin lattices in 3d. Journal of Mathematical Physics , 58(11), November 2017. URL: http://dx.doi.org/10.1063/1.5011338, https://doi.org/10.1063/1.5011338 doi:10.1063/1.5011338

work page doi:10.1063/1.5011338 2017
[6]

The quantum and classical complexity of translationally invariant tiling and hamiltonian problems

Daniel Gottesman and Sandy Irani. The quantum and classical complexity of translationally invariant tiling and hamiltonian problems. Theory of Computing , 9(2):31--116, 2013. URL: https://theoryofcomputing.org/articles/v009a002, https://doi.org/10.4086/toc.2013.v009a002 doi:10.4086/toc.2013.v009a002

work page doi:10.4086/toc.2013.v009a002 2013
[7]

Translationally invariant universal classical Hamiltonians

Tamara Kohler and Toby Cubitt . Translationally Invariant Universal Classical Hamiltonians . Journal of Statistical Physics , 176(1):228--261, July 2019. https://arxiv.org/abs/1807.01715 arXiv:1807.01715 , https://doi.org/10.1007/s10955-019-02295-3 doi:10.1007/s10955-019-02295-3

work page internal anchor Pith review Pith/arXiv arXiv 2019
[8]

Kraus, Maciej Lewenstein, and J

Christina V. Kraus, Maciej Lewenstein, and J. Ignacio Cirac. Ground states of fermionic lattice hamiltonians with permutation symmetry. Physical Review A , 88(2), August 2013. URL: http://dx.doi.org/10.1103/PhysRevA.88.022335, https://doi.org/10.1103/physreva.88.022335 doi:10.1103/physreva.88.022335

work page doi:10.1103/physreva.88.022335 2013
[9]

A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation . American Mathematical Society, USA, 2002

work page 2002
[10]

The complexity of quantum spin systems on a two-dimensional square lattice

Roberto Oliveira and Barbara Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum information & computation , 8, 05 2005. https://doi.org/10.26421/QIC8.10-2 doi:10.26421/QIC8.10-2

work page doi:10.26421/qic8.10-2 2005
[11]

Universal Translationally-Invariant Hamiltonians

Stephen Piddock and Johannes Bausch. Universal translationally-invariant hamiltonians, 2020. URL: https://arxiv.org/abs/2001.08050, https://arxiv.org/abs/2001.08050 arXiv:2001.08050

work page internal anchor Pith review Pith/arXiv arXiv 2020
[12]

Rickwardt, P

Ch. Rickwardt, P. Nielaba, and K. Binder. A finite size scaling study of the five-dimensional ising model. Annalen der Physik , 506(6):483--493, 1994. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/andp.19945060606, https://arxiv.org/abs/https://onlinelibrary.wiley.com/doi/pdf/10.1002/andp.19945060606 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10...

work page doi:10.1002/andp.19945060606 1994
[13]

Graphs with given group and given graph-theoretical properties

Gert Sabidussi. Graphs with given group and given graph-theoretical properties. Canadian Journal of Mathematics , 9:515–525, 1957. https://doi.org/10.4153/CJM-1957-060-7 doi:10.4153/CJM-1957-060-7

work page doi:10.4153/cjm-1957-060-7 1957
[14]

B. M. Terhal. Is entanglement monogamous? IBM Journal of Research and Development , 48(1):71–78, January 2004. URL: http://dx.doi.org/10.1147/rd.481.0071, https://doi.org/10.1147/rd.481.0071 doi:10.1147/rd.481.0071

work page doi:10.1147/rd.481.0071 2004

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.

[1] [1]

Commuting Local Hamiltonians on Expanders, Locally Testable Quantum codes, and the qPCP conjecture

Dorit Aharonov and Lior Eldar. Commuting local hamiltonians on expanders, locally testable quantum codes, and the qpcp conjecture, 2013. URL: https://arxiv.org/abs/1301.3407, https://arxiv.org/abs/1301.3407 arXiv:1301.3407

work page internal anchor Pith review Pith/arXiv arXiv 2013

[2] [2]

The power of quantum systems on a line

Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. The power of quantum systems on a line. Communications in Mathematical Physics , 287(1):41–65, January 2009. URL: http://dx.doi.org/10.1007/s00220-008-0710-3, https://doi.org/10.1007/s00220-008-0710-3 doi:10.1007/s00220-008-0710-3

doi:10.1007/s00220-008-0710-3 2009

[3] [3]

Cubitt, and James D

Johannes Bausch, Toby S. Cubitt, and James D. Watson. Uncomputability of phase diagrams. Nature Communications , 12(1), January 2021. URL: http://dx.doi.org/10.1038/s41467-020-20504-6, https://doi.org/10.1038/s41467-020-20504-6 doi:10.1038/s41467-020-20504-6

doi:10.1038/s41467-020-20504-6 2021

[4] [4]

Brandao and Aram W

Fernando G.S.L. Brandao and Aram W. Harrow. Product-state approximations to quantum ground states. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing , STOC '13, page 871–880, New York, NY, USA, 2013. Association for Computing Machinery. https://doi.org/10.1145/2488608.2488719 doi:10.1145/2488608.2488719

work page arXiv 2013

[5] [5]

The complexity of translationally invariant low-dimensional spin lattices in 3d

Johannes Bausch and Stephen Piddock. The complexity of translationally invariant low-dimensional spin lattices in 3d. Journal of Mathematical Physics , 58(11), November 2017. URL: http://dx.doi.org/10.1063/1.5011338, https://doi.org/10.1063/1.5011338 doi:10.1063/1.5011338

work page doi:10.1063/1.5011338 2017

[6] [6]

The quantum and classical complexity of translationally invariant tiling and hamiltonian problems

Daniel Gottesman and Sandy Irani. The quantum and classical complexity of translationally invariant tiling and hamiltonian problems. Theory of Computing , 9(2):31--116, 2013. URL: https://theoryofcomputing.org/articles/v009a002, https://doi.org/10.4086/toc.2013.v009a002 doi:10.4086/toc.2013.v009a002

work page doi:10.4086/toc.2013.v009a002 2013

[7] [7]

Translationally invariant universal classical Hamiltonians

Tamara Kohler and Toby Cubitt . Translationally Invariant Universal Classical Hamiltonians . Journal of Statistical Physics , 176(1):228--261, July 2019. https://arxiv.org/abs/1807.01715 arXiv:1807.01715 , https://doi.org/10.1007/s10955-019-02295-3 doi:10.1007/s10955-019-02295-3

work page internal anchor Pith review Pith/arXiv arXiv 2019

[8] [8]

Kraus, Maciej Lewenstein, and J

Christina V. Kraus, Maciej Lewenstein, and J. Ignacio Cirac. Ground states of fermionic lattice hamiltonians with permutation symmetry. Physical Review A , 88(2), August 2013. URL: http://dx.doi.org/10.1103/PhysRevA.88.022335, https://doi.org/10.1103/physreva.88.022335 doi:10.1103/physreva.88.022335

work page doi:10.1103/physreva.88.022335 2013

[9] [9]

A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation . American Mathematical Society, USA, 2002

work page 2002

[10] [10]

The complexity of quantum spin systems on a two-dimensional square lattice

Roberto Oliveira and Barbara Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum information & computation , 8, 05 2005. https://doi.org/10.26421/QIC8.10-2 doi:10.26421/QIC8.10-2

work page doi:10.26421/qic8.10-2 2005

[11] [11]

Universal Translationally-Invariant Hamiltonians

Stephen Piddock and Johannes Bausch. Universal translationally-invariant hamiltonians, 2020. URL: https://arxiv.org/abs/2001.08050, https://arxiv.org/abs/2001.08050 arXiv:2001.08050

work page internal anchor Pith review Pith/arXiv arXiv 2020

[12] [12]

Rickwardt, P

Ch. Rickwardt, P. Nielaba, and K. Binder. A finite size scaling study of the five-dimensional ising model. Annalen der Physik , 506(6):483--493, 1994. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/andp.19945060606, https://arxiv.org/abs/https://onlinelibrary.wiley.com/doi/pdf/10.1002/andp.19945060606 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10...

work page doi:10.1002/andp.19945060606 1994

[13] [13]

Graphs with given group and given graph-theoretical properties

Gert Sabidussi. Graphs with given group and given graph-theoretical properties. Canadian Journal of Mathematics , 9:515–525, 1957. https://doi.org/10.4153/CJM-1957-060-7 doi:10.4153/CJM-1957-060-7

work page doi:10.4153/cjm-1957-060-7 1957

[14] [14]

B. M. Terhal. Is entanglement monogamous? IBM Journal of Research and Development , 48(1):71–78, January 2004. URL: http://dx.doi.org/10.1147/rd.481.0071, https://doi.org/10.1147/rd.481.0071 doi:10.1147/rd.481.0071

work page doi:10.1147/rd.481.0071 2004

The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete

The reading

Core claim §

What carries the argument

Load-bearing premise §

What would settle it §

If this is right

Where Pith is reading between the lines

discussion (0)

Core claim

Load-bearing premise

What would settle it