The quantum many-body systems we will consider are translationally invariant, nearest-neighbour, 2D spin–lattice models. The L × L square lattice with open boundary conditions will be denoted as Λ(L); for brevity, we leave the lattice size implicit whenever it is clear from the context. Each lattice site is associated with a spin system with local Hilbert space of dimension d, \({{\Bbb{C}}}^{d}\). The spins are coupled with a nearest-neighbour, translationally invariant Hamiltonian with local terms \(h^{\mathrm{col}},h^{\mathrm{row}}\in {\mathcal{B}}({{\Bbb{C}}}^{d}\otimes {{\Bbb{C}}}^{d})\), such that \(\max \{| | h^{\mathrm{row}}| | ,| | h^{\mathrm{col}}| | \}\le 2\). Since we are interested in phase transitions—identified by a discontinuous change of a macroscopic observable O_A/B, which strictly speaking can only occur in the thermodynamic limit of infinitely large lattices—we will take the thermodynamic limit by letting L → ∞. An alternative definition of a quantum phase transition is a non-analytic change in the ground state energy¹. This will also be satisfied with our construction. The resulting Hamiltonian over the entire lattice is then

As well as being distinguished by the observable O_A/B, the two phases are also distinguished by the spectral gap of the Hamiltonian H^Λ, defined as the difference between the smallest and second smallest eigenvalue of the Hamiltonian:

As in ref. ⁹, we then define a Hamiltonian to be gapped if there exist γ and L₀ such that the spectral gap Δ(H^Λ(L)) ≥ γ for all L > L₀; and gapless if the spectrum above the ground state becomes dense in an interval \([\lambda_{\mathrm{min}} (H^{{{\Lambda }}(L)}),\lambda_{\mathrm{min}} (H^{{{\Lambda }}(L)})+c]\) for some c > 0 in the thermodynamic limit (see Supplementary Definitions 1.1 and 1.2 for mathematically rigorous statements). Throughout the paper, we will be using the notion of a continuous family of Hamiltonians, which—loosely speaking—is a family of Hamiltonians \({\{{H}_{i}(\varphi )\}}_{i\in I}\) such that each H_i(φ) = ∑_jh_j(φ), and the matrix elements of h_j(φ) depend continuously on φ (see Supplementary Definition 1.3).

Our main result is an explicit construction of a one-parameter continuous family of Hamiltonians, such that for all values \(\varphi \in {\Bbb{R}}\) of the external parameter, the system is guaranteed to be in one of two possible phases, distinguished by an order parameter given by the ground state expectation value of a translationally invariant macroscopic observable O_A/B. However, determining which phase the system is in is undecidable, hence the phase diagram of the system as a function of φ is uncomputable. More precisely, we prove the following theorem:

Theorem 2.1 (Phase Diagram Uncomputability) For any given Turing Machine (TM), we can construct explicitly a dimension \(d\in {\Bbb{N}}\), d² × d² matrices \(a,a^{\prime} ,b,c,c^{\prime}\) and a d × d matrix m with the following properties:

1. (i)

   a, c and m are diagonal with entries in \({\Bbb{Z}}\).

2. (ii)

   \(a^{\prime}\) is Hermitian with entries in \({\Bbb{Z}}+\frac{1}{\sqrt{2}}{\Bbb{Z}}\).

3. (iii)

   b has integer entries.

4. (iv)

   \(c^{\prime}\) is Hermitian with entries in \({\Bbb{Z}}\).

5. (v)

   For any real number \(\varphi \in {\Bbb{R}}\) and any 0 ≤ β ≤ 1, which can be chosen arbitrarily small, setting

   $$\begin{array}{lll}\;\;\;\; \;\;\; h^{\mathrm{col}} := c+\beta c^{\prime} \quad \quad independent\,of\,\varphi ,\\ h^{\mathrm{row}}(\varphi ) := a+\beta \left(a^{\prime} +{{e}}^{i\pi \varphi }b+{{e}}^{-i\pi \varphi }{b}^{\dagger }\right),\end{array}$$

   we have ∥h^row(φ)∥ ≤ 2, ∥h^col(φ)∥ ≤ 1.

Define H^Λ(L) as in Eq. (1), and let O_A/B ≔ L⁻²∑_i ∈ Λm_i. Then, given φ ∈ [2^−η, 2^−η + 2^−η−ℓ) with \(\eta \in {\Bbb{N}}\), the following statements hold:

• If TM halts on input η, then for some ℓ ≥ 1, H^Λ(φ) is gapless in the sense of Supplementary Definition 1.2, with a ground state that is critical (i.e. with algebraic decay of correlations), and for all eigenstates \(\left|{{{\Psi }}}_{\mathrm{B}}\right\rangle\) with energy \(\left\langle {{{\Psi }}}_{\mathrm{B}}\right|H^{{{\Lambda }}}(\varphi )\left|{{{\Psi }}}_{\mathrm{B}}\right\rangle \le 1\) it holds that \(\left\langle {{{\Psi }}}_{\mathrm{B}}\right|{O}_{\mathrm{A/B}}\left|{{{\Psi }}}_{\mathrm{B}}\right\rangle =0\).

• If TM is non-halting on input η and ℓ = 1, then H^Λ(φ) is gapped in the sense of Supplementary Definition 1.1, with a unique, product ground state \(\left|{{{\Psi }}}_{\mathrm{A}}\right\rangle\) with \(\left\langle {{{\Psi }}}_{\mathrm{A}}\right|{O}_{\mathrm{A/B}}\left|{{{\Psi }}}_{\mathrm{A}}\right\rangle =1\).

The undecidability of which of the two cases pertains follows immediately from the undecidability of the Halting Problem, by choosing TM to be a universal TM. For simplicity, we will refer to the phases A and B determined by the value for the macroscopic observable O_A/B as the gapped and gapless phase, respectively.

As a consequence of the new Hamiltonian construction in this paper, we also obtain the following result:

Corollary 2.2 For all φ ∈ [0, 1], H^Λ(φ) is either in a phase with a product ground state and a spectral gap ≥1, or it is in a gapless phase with algebraic decay of correlations, where the two phases are distinguished by the expectation value of a macroscopic observable O_A/B. Moreover, there exists a subset S ⊂ [0, 1] with Borel measure μ(S) > 0, such that even for computable φ ∈ S, determining the phase that H^Λ(φ) is in is uncomputable.

A less precise but simple interpretation of the above corollary is:

Corollary 2.3 (informal) The phase diagram of H^Λ(φ) as a function of its parameter φ is uncomputable.

A set of schematic phase diagrams is shown in Fig. 1.

Constructing the Hamiltonian

Using well-known methods from the field of Hamiltonian complexity, it is possible to construct a quantum many-body system whose lowest-energy eigenstate represents the evolution of any desired computation¹². If we introduce a local term in the Hamiltonian that gives additional energy to any state with overlap with the halting state of the computation, we can arrange for states representing computations that halt to pick up additional energy relative to states representing computations that do not halt and open up a gap in the spectrum. In this way, Turing’s well-known Halting Problem can be transcribed into a property of the quantum many-body system, namely whether or not it has a spectral gap. Thus, determining whether the system has a spectral gap is at least as hard as the Halting Problem. Since the Halting Problem is known to be undecidable, determining whether the Hamiltonian is gapped or gapless is also undecidable. Conceptually, this is how Cubitt, Perez-Garcia & Wolf, and Bausch et al.^9,10,11 proved the undecidability of the spectral gap.

The starting point for our construction is also the undecidability of the Halting Problem¹³: in brief, this states that determining whether a universal (classical) TM (UTM) halts or not on a given input is, in general, undecidable. In the quantum computation setting, Cubitt, Perez-Garcia and Wolf⁹ showed how an input can be extracted from a phase in a quantum gate such as \(U={\rm{diag}}(1,\exp (2\pi i\varphi ))\), using quantum phase estimation (QPE, ref. ¹⁴), which outputs a binary expansion of φ. The latter can then be fed as input to a UTM. Thus, this combination of QPE and UTM runs the UTM on any desired input encoded in φ, and the Halting Problem for this combination is undecidable.

How do we reduce this QTM-based Halting Problem to a result about phases in a many-body system? This is a culmination of the following techniques from previous works. However, for each one of them, significant obstacles must be overcome to prove the uncomputability of phase diagrams .

1. 1.

   The first necessary ingredient is a QTM-to-Hamiltonian mapping, which allows the construction of local, translationally invariant couplings that result in a 1D spin chain Hamiltonian whose ground state energy is exactly zero if the encoded QTM does halts within a certain time interval; or otherwise is positive¹⁵. Using such an QTM-to-Hamiltonian mapping, a QTM running the QPE + UTM computation described above is encoded into the spin chain Hamiltonian, with φ now appearing as a parameter of the resulting Hamiltonian. However, the energy difference between the halting and non-halting cases decreases as the time interval increases, meaning we need further techniques to obtain a non-zero energy difference in the thermodynamic limit.

2. 2.

   A second ingredient is amplifying this penalty. In ref. ⁹ this is done by combining the QTM-to-Hamiltonian mapping with an aperiodic tiling Hamiltonian, thereby ensuring that, for each length of a computation, a fixed density of such circuit-to-Hamiltonian instances are distributed across the spin lattice. In this way, the ground state energy density is zero iff the QTM-to-Hamiltonian mapping always has zero energy, and thus depends on whether the QPE + UTM computation ever halts.

3. 3.

   In ref. ¹¹, point 2 is replaced by a so-called Marker Hamiltonian. This in combination with a circuit-to-Hamiltonian construction results in a ground state, which partitions the spin chain into segments just large enough for the UTM to halt, if it halts. Here, the segments do not have a fixed length, but instead self-adjust to find their own length. In contrast to ref. ⁹, this has the effect that either all encoded instances of computations halt, or none do.

4. 4.

   The final step is the addition of an Ising-type coupling as in refs. ^9,16, which breaks the local Hilbert space up into subspaces \({{\mathcal{H}}}_{\mathrm{A}}\oplus {{\mathcal{H}}}_{\mathrm{B}}\), and which ensures that the low-energy spectrum is contained either entirely in the A or B subspace, depending on the ground state energy density just constructed. Since determining the ground state energy density is uncomputable, it is also uncomputable to determine whether the system is in phase A or B with respect to the Hamiltonian parameter φ.

As mentioned, we require significant alterations to this collection of ingredients. Concretely, the issue is that if we encode an input φ to be extracted using error-free QPE, then we require the circuit gates to depend explicitly on the binary length of φ, denoted ∣φ∣. Consequently, the resulting matrix elements of the Hamiltonian will also explicitly depend on ∣φ∣—a discontinuous function of φ. To remove this dependence, we instead perform the QPE procedure approximately, by using a universal gate set that approximates all the gates depending on ∣φ∣¹⁷. However, the constructions of Cubitt, Perez-Garcia & Wolf, and Bausch et al.^9,11 crucially rely on the QPE expansion of φ to be performed exactly; any errors destroy the constructions.

To overcome this obstacle, we first encode this approximate QPE plus the evolution of a UTM in a QTM-to-Hamiltonian mapping, which has positive energy iff the QPE + UTM computation does not halt. We label the resulting Hamiltonian H_comp. This is outlined in sections ‘Encoding computation in Hamiltonians’, ‘The encoded computation’ and ‘From QTM to Hamiltonian’ where the QTM-to-Hamiltonian mapping and the computation it encodes are explained, respectively. A significant novel technical contribution of this work is then a proof that the Marker Hamiltonian used in ref. ¹¹ does, in fact, allow for some leeway in the precision to which QPE is performed and can be used to provide a correction for the energy penalty picked up as a result of any errors in the QPE.

To generate the required energy correction, we consider a 2D spin lattice and construct an underlying classical Hamiltonian, which we denote H_cb, that partitions the lattice into a uniform grid of squares. We note that the method from ref. ⁹ would be inappropriate for this construction as it would lead to an accumulation of energies we cannot correct for without matrix elements depending explicitly on ∣φ∣. Within each square, the ground state encodes the evolution of a classical TM (encoded as a tiling problem akin to the ones used in refs. ^18,19), which will calculate the energy correction necessary to offset the error introduced by approximately performing QPE. The classical Hamiltonian is then coupled to the Marker Hamiltonian. We denote this combination H^(⊞).

Section ‘Classical tiling with quantum overlay’ describes the ground state of the resulting Hamiltonian H^(⊞) such that the halting or non-halting behaviour together with the Marker Hamiltonian determines whether the energy density of the constructed Hamiltonian is non-negative (in the non-halting case) or negative (in the halting case). Crucially, it is now robust with respect to the errors present in the expansion of φ from the approximate QPE procedure. Finally, in section ‘Uncomputability of the Phase Diagram’, we show how H_comp, H_cb and H^(⊞) are combined mathematically to lift this undecidability of the ground state energy density, to uncomputability of the phase diagram, using now-standard techniques^9,11,16. For a mathematically rigorous derivation, we refer the reader to the Supplementary information.

Encoding computation in Hamiltonians

A QTM can be thought of as a classical TM, but where the TM head and tape configuration can be in a superposition of states. The updates to the QTM and tape configuration are then described by a transition unitary, U, describing the transitions of the QTM state and tape, such that the state is updated via the map \(\left|\psi\,\right\rangle \,\mapsto\,U\left|\psi \right\rangle\)²⁰.

Given a QTM, one can construct a local Hamiltonian that has a ground state encoding the evolution of the computation^9,15, closely related to the Feynman–Kitaev Hamiltonian encoding quantum circuits into Hamiltonians^12,21. The ground state encodes T steps of the computation, where T is a predefined and fixed function of the Hamiltonian’s size determined by the particular QTM-to-Hamiltonian mapping. The ground state of such a Hamiltonian is called a history state and takes the form

where the state of the quantum TM at time step t is \(\left|{\psi }_{t}\right\rangle\). The ground state energy of the Hamiltonian can be made dependent on aspects of the computation by adding a projector that penalises certain computational states, and the resulting energy is known to high precision^22,23.

The encoded computation

As in refs. ^9,11, the computation we wish to encode via such a QTM-to-Hamiltonian mapping will be a pair of QTMs running in succession: the first will run QPE on a quantum gate U_φ, which outputs a number in binary, and the second will be a UTM, which takes the output of the QPE as input. The gate U_φ is encoded in the transition unitary U describing the QTM, which is in turn encoded in the matrix elements of the Hamiltonian. The energy of the Hamiltonian encoding the computation will then be made dependent on whether the computation halts or not, allowing us to relate its ground state energy to the halting property.

Phase estimation

Given a unitary matrix \({U}_{\varphi }=\left(\begin{array}{cc}1&0\\ 0&{{e}}^{i\pi \varphi }\end{array}\right)\), the QPE algorithm takes as input the eigenvector corresponding to the eigenvalue e^iπφ, and outputs an estimate of φ in binary. If the number of qubits on which the phase estimation is performed is smaller than the number of bits required to express φ in full, the algorithm is only approximate¹⁴. Furthermore, if a finite gate set is used, some of the required unitary gates in the algorithm must be approximated rather than performed exactly¹⁷. Hence, from phase estimation, we get an output state consisting of a superposition over binary strings:

where the amplitudes β_x are concentrated around those values for which x ≈ φ and rapidly drop off away from φ. Details are in Supplementary Note 2.

Universal QTM

We then feed the output \(\left|\chi (\varphi )\right\rangle\) of this phase estimation into the input of a universal TM, as in ref. ⁹, which then runs a computation that may or may not halt. By the well-known undecidability of the Halting Problem¹³, determining whether the QTM halts for a given string is undecidable.

From QTM to Hamiltonian

Using the QTM-to-Hamiltonian mapping described in section ‘Encoding computation in Hamiltonians’, the computation outlined above is mapped to a 1D, translationally invariant, nearest-neighbour Hamiltonian H_comp(φ)¹⁵, with a penalty for the non-halting case. It can be shown that the ground state energy of H_comp(φ) scales as

where

The β_x are the QPE coefficients in Eq. (4), and S(L) is the set of inputs for which the universal TM does not halt within time T(L).

Since the β_x are concentrated around the binary expansion of φ, if the latter encodes a halting instance, there will be a length L₀ for which ϵ(L) ≈ 0 for all L > L₀; otherwise, ϵ(L) ≈ 1 for all L. This immediately yields a Hamiltonian for which the ground state energy is halting-dependent (and hence uncomputable). We refer the reader to Supplementary Note 3 for details.

Tiling and classical computation

In Eq. (5), we see that the difference between the Hamiltonian’s ground state energy in the case where ϵ(L) from Eq. (6) is ~1 or 0 decreases with the system size L. Thus, the energy gap between the two cases goes to zero irrespective of whether φ encodes a halting or non-halting instance. To amplify this gap so that there is a finite energy gap in the thermodynamic limit (as per points 2 and 3), we will combine the Feynman–Kitaev Hamiltonian with a classical Hamiltonian based on a Wang tiling that partitions the space suitably to ensure a fixed density of computation instances is spawned across the lattice. The result we achieve with this is an energy gap opening up as L grows between the cases where ϵ takes different values.

A set of Wang tiles—square, 2D tiles with coloured sides, with the rule that adjacent sides of neighbouring tiles in a tiling of the plane must have matching colours—can be mapped to a classical Hamiltonian: if tiles t_i, t_j cannot be placed next to each other, then we introduce a term \(\left|{t}_{i}\right\rangle \langle {t}_{j}|\) into the Hamiltonian. The overall Hamiltonian is the sum over all such local terms, such that its ground state represents a tiling satisfying the tiling rules (if such a tiling exists). If no such tiling exists, the ground state energy is ≥1.

Similarly, it is well known that there exist tile sets that encode the evolution of a classical TM^18,19 within a square grid: TM tape configurations are represented by rows, such that adjacent rows represent successive time steps of the TM (Fig. 2).

We combine both Wang tiles and the TM tiling ideas by constructing a tile set whose valid tilings have the following properties:

1. 1.

   A tiling pattern that creates a square grid across the lattice Λ (much like a checkerboard). The side length of the grid squares can be varied (provided all grid squares are the same size) and still correspond to a valid tiling (depicted in Fig. 3).

2. 2.

   Within each square of the grid, we use the tiles to encode a TM that first counts the size of the square it is contained in, and then outputs a marker • on the top border of the square, where the placement of this marker is a function of the size of the square (depicted in Fig. 2).

Having developed this tiling, we map it to a corresponding tiling Hamiltonian, which we denote H_cb, such that its ground states retain the properties of the valid tilings listed above. The reader is referred to Supplementary Note 4 for details.

Classical tiling with a quantum overlay

We now want to combine the classical Hamiltonian encoding the Wang tiles, and the quantum Hamiltonian encoding the Halting Problem computation, to create an overall Hamiltonian that has a large ground state energy difference between the halting and non-halting cases, without the ~1/poly(L) decay in Eq. (5). To do so, we split the local Hilbert space of each lattice spin into a classical part \({{\mathcal{H}}}_{{\rm{c}}}\) and a quantum part \({{\mathcal{H}}}_{{\rm{e}}}\oplus {{\mathcal{H}}}_{{\rm{q}}}\) giving \({\mathcal{H}}={{\mathcal{H}}}_{{\rm{c}}}\otimes ({{\mathcal{H}}}_{{\rm{e}}}\oplus {{\mathcal{H}}}_{{\rm{q}}})\), where \({{\mathcal{H}}}_{{\rm{e}}}=\{\left|e\right\rangle \}\) just contains a filler state \({\left|e\right\rangle }_{{\rm{e}}}\). The ground state can then be designed to be a product state of the form \({\left|C\right\rangle }_{{\rm{c}}}\otimes {\left|{\psi }_{0}\right\rangle }_{{\rm{eq}}}\), where \({\left|C\right\rangle }_{{\rm{c}}}\) is a valid classical tiling configuration—as described in section ‘Tiling and classical computation’—and \({\left|{\psi }_{0}\right\rangle }_{{\rm{eq}}}\) is a quantum state with the following properties:

1. 1.

   We use the 1D Marker Hamiltonian from ref. ¹¹, and couple its negative energy contribution to the size of each grid square in the classical tiling and the placement of the • marker. The negative energy each square contributes is a determined by where the • marker is placed, and thus by the action of the classical TM. We denote this combined Hamiltonian H^(⊞).

2. 2.

   We effectively place the ground state of a Hamiltonian H_comp encoding the QPE plus universal TM along the top edge of the square, by adding additional penalty terms to the Hamiltonian that penalise the classical and quantum layers to occur in this configuration elsewhere.

3. 3.

   Everywhere not along the horizontal edge of a grid square in \({{\mathcal{H}}}_{{\rm{c}}}\) is in the zero-energy \({\left|e\right\rangle }_{{\rm{e}}}\) filler state in \({{\mathcal{H}}}_{{\rm{e}}}\oplus {{\mathcal{H}}}_{{\rm{q}}}\).

As mentioned, the patterns in the degenerate ground space of H_cb are checkerboard grids of squares with periodicity w × w, where the integer square size w is not fixed.

By choosing the classical TM encoded in the tiling to place a • marker at an appropriate point, we are able to tune the ground state energy of H^(⊞) such that the total energy of a single w × w square A in the checkerboard pattern is:

where ϵ₀(w) is some cut-off point, w₀ is the halting length (recall from the previous section that the runtime of the computation encoded in the ground state depends on the size of the available tape, i.e. the size of the checkerboard square edge that the TM runs on), and where \(\lambda_{\mathrm{min}} ({w}_{0})=-\delta ({w}_{0})\,<\,0\) for the halting length w₀ is a small negative constant.

The Marker Hamiltonian’s energy bonus thus compensates for the QPE approximation errors by lowering the energy by just enough such that a halting instance has negative energy. On the other hand, the energy of the non-halting instance remains large enough that the energy of a single square remains positive^11,23.

Thus, provided ϵ(w) is sufficiently small, the ground state of H_cb + H_comp + H^(⊞)(+coupling terms) is a checkerboard grid of squares with a constant but negative energy density. Otherwise, the ground state energy density of the lattice is lower bounded by zero. Which of the two cases holds depends on determining whether ϵ(w) ≥ ϵ₀(w) or <ϵ₀(w), which is undecidable; undecidability of the ground state energy density follows. The reader is referred to Supplementary Note 5 for more details.

We define the Hamiltonian formed by H_cb, H_comp and H^(⊞) and the coupling terms as H_u(φ). Assume φ encodes a halting instance and set \(w={\mathrm{argmin}}_{s}\{\lambda_{\mathrm{min}} (s)\,<\,0\}\), and A is a single square of size w × w. Then, the ground state energy H_u(φ) on a grid Λ of size L × H is given by

Uncomputability of the phase diagram

To go from undecidability of the ground state energy density, demonstrated at the end of section ‘Classical tiling with quantum overlay’ to the undecidability of the phase (and spectral gap), we follow the approach of Cubitt, Perez-Garcia and Wolf⁹ by combining H_u(φ) with a trivial state \(\left|0\right\rangle\) such that \({\left|0\right\rangle }^{\otimes {{\Lambda }}}\) has zero energy, and the spectrum of H_u(φ) is shifted up by +1 (Supplementary Lemma 6.5). From this shift and Eq. (8) it can be shown that

Let h_u(φ) denote the local terms of H_u(φ), let h_d be the local terms of the critical XY model, and let \(\left|0\right\rangle\) be a zero energy state, such that the total Hilbert space is \(({{\mathcal{H}}}_{1}\otimes {{\mathcal{H}}}_{2})\oplus \{\left|0\right\rangle \}\). Then, the local terms of the total Hamiltonian H^Λ(φ) are defined as

The result is the following: the overall spectrum of the Hamiltonian is

where G ⊂ [1, ∞). To understand this, we consider the two cases. If a non-halting instance is encoded \(\lambda_{\mathrm{min}} \, \ge \, 0\) in Eq. (7), then H_u(φ)—from Eq. (9)—has ground state energy lower-bounded by 1; the ground state of the overall Hamiltonian is the trivial zero energy classical product state \({\left|0\right\rangle }^{\otimes {{\Lambda }}}\), and H^Λ has a constant spectral gap. If \(\lambda_{\mathrm{min}} \, < \, -{\!}| \delta |\), then H_u(φ) has a ground state with energy diverging to −∞. We further note that the critical XY model has a dense spectrum with zero ground state energy, hence from the H_d term we obtain a dense spectrum above the ground state²⁴. As a result, the Hamiltonian becomes gapless and has a highly entangled ground state with algebraically decaying correlations.

Since the existence of a halting length w₀ in Eq. (7) is undecidable, discriminating between \(\lambda_{\mathrm{min}} \, \ge \, 0\) or <−∣δ∣ is also undecidable. This implies determining whether the Hamiltonian is in the critical, quantum-correlated phase or the trivial product state gapped phase is undecidable as well.

As H^Λ(φ) is a continuous function of φ, there exist finite measure regions for which all values of φ have the same ground state and for which there is no closing of the spectral gap, which delineates the two phases. Setting \({{{\Pi }}}_{i}:= \left|0\right\rangle {\left\langle 0\right|}^{(i)}\), the observable O_A/B = L⁻²∑_i∈ΛΠ_i has expectation value 1 when in the state \({\left|0\right\rangle }^{\otimes {{\Lambda }}(L)}\), and 0 in the other case. This is true even if the observable is restricted to a finite geometrically local subset of the lattice. We refer the reader to Supplementary Note 6 for more details.