Undecidability of the Spectral Gap in One Dimension
Johannes Bausch
CQIF, DAMTP, University of Cambridge, UK
Toby S. Cubitt
Department of Computer Science, University College London, UK
Angelo Lucia
QMATH, Department of Mathematical Sciences and NBIA,
Niels Bohr Institute, University of Copenhagen, 2100 Copenhagen, DK and
Walter Burke Institute for Theoretical Physics and Institute for Quantum Information & Matter,
California Institute of Technology, Pasadena, CA 91125, USA
David Perez-Garcia
Dept. An ́alisis y Matem ́atica Aplicada,Universidad Complutense de Madrid, 28040 Madrid, Spain and
Instituto de Ciencias Matem ́aticas, 28049 Madrid, Spain
The spectral gap problem—determining whether the energy spectrum of a system has an energy
gap above ground state, or if there is a continuous range of low-energy excitations—pervades quantum
many-body physics. Recently, this important problem was shown to be undecidable for quantum spin
systems in two (or more) spatial dimensions: there exists no algorithm that determines in general
whether a system is gapped or gapless, a result which has many unexpected consequences for the
physics of such systems. However, there are many indications that one dimensional spin systems
are simpler than their higher-dimensional counterparts: for example, they cannot have thermal
phase transitions or topological order, and there exist highly-effective numerical algorithms such as
DMRG—and even provably polynomial-time ones—for gapped 1D systems, exploiting the fact that
such systems obey an entropy area-law. Furthermore, the spectral gap undecidability construction
crucially relied on aperiodic tilings, which are not possible in 1D.
So does the spectral gap problem become decidable in 1D? In this paper we prove this is not the
case, by constructing a family of 1D spin chains with translationally-invariant nearest neighbour
interactions for which no algorithm can determine the presence of a spectral gap. This not only
proves that the spectral gap of 1D systems is just as intractable as in higher dimensions, but also
predicts the existence of qualitatively new types of complex physics in 1D spin chains. In particular,
it implies there are 1D systems with constant spectral gap and non-degenerate classical ground state
for all systems sizes up to an uncomputably large size, whereupon they switch to a gapless behaviour
with dense spectrum.
I. INTRODUCTION
One-dimensional spin chains are an important and
widely-studied class of quantum many-body systems. The
quantum Ising model, for example, is a classic model of
magnetism; the 1D Ising model with transverse fields is
the textbook example of a quantum phase transition. It
is also one of a handful of quantum many-body systems
which can be completely solved analytically. Indeed, most
known exactly solvable quantum many-body models are
in 1D [
1
–
3
]. Even for 1D systems that are not exactly solv-
able, the density matrix renormalisation group (DMRG)
algorithm [
4
] works extremely well in practice, and re-
cent results have even yielded provably efficient classical
algorithms for all 1D gapped systems [5].
While it is known that approximating a 1D quan-
tum system’s ground state energy to inverse polyno-
mial precision is in general QMA hard [
6
,
7
]—even
with translationally-invariant nearest neighbour interac-
tions [
8
,
9
]—currently there are no examples of gapped
QMA-hard Hamiltonians and and there are indica-
tions [
10
] that gaplessness is required in order to have a
hard to compute ground state energy.
There are several other indications that ground states of
(finite) gapped 1D systems are qualitatively simpler than
in higher dimensions. They obey an entanglement area-
law, hence have an efficient classical descriptions in terms
of matrix product states [
11
,
12
]. Furthermore, thermal
phase transitions [
13
] and topological order [
14
] are both
ruled out for 1D quantum systems. For classical 1D sys-
tems, satisfiability and tiling problems become tractable.
For the simplest class of spin chains—qubit chains with
translationally invariant nearest-neighbour interactions—
the spectral gap problem has been completely solved when
the system is frustration-free [15].
Contrast this with the situation in 2D and higher, where
even simple theoretical models such as the 2D Fermi-
Hubbard model (believed to underlie high-temperature
superconductivity) cannot be reliably solved numerically
even for moderately large system sizes [
16
,
17
]; the entropy
area-law remains an unproven conjecture [
18
]; and the
spectral gap problem—i.e. the question of existence of a
spectral gap above the ground state in the thermodynamic
arXiv:1810.01858v2 [quant-ph] 12 Jun 2020
2
limit—is undecidable [
19
,
20
]. This latter result holds
under the assumption that either the ground state is non-
degenerate with a constant spectral gap above it in the
gapped case, or that the entire spectrum is continuous
in the gapless case: therefore the undecidability of the
problem of distinguishing the two cases is not due to the
presence of ambiguous cases (for example cases where low-
excited states collapse onto the groundstate in the limit).
For classical systems, satisfiability and tiling problems
are NP-hard [
21
] and undecidable [
22
] (respectively) in
two dimensions and higher.
Despite these indications that one-dimensional systems
appear qualitatively easier to analyse than their higher-
dimensional counterparts, we show in this paper that
the spectral gap problem is undecidable, even in 1D.
The many-body quantum systems we consider in this
work are one-dimensional spin chains, i.e. with a Hilbert
space (
C
d
)
⊗
N
, where
d
is the local physical dimension,
and
N
the length of the chain. The spins are coupled
by translationally-invariant local interactions: a nearest-
neighbour term
h
(2)
, which is a
d
2
×
d
2
Hermitian matrix,
and a
d
×
d
-sized local term
h
(1)
which is also Hermitian.
Both
h
(1)
and
h
(2)
are independent of the system size
N
.
The overall Hamiltonian
H
N
will be a sum of the local
terms:
H
N
=
N
−
1
∑
i
=1
h
(2)
i,i
+1
+
N
∑
i
=1
h
(1)
i
.
(1)
(Following standard notation, subscripts indicate the
spin(s) on which the operator acts non-trivially, with
the operator implicitly extended to the whole chain by
tensoring with
1
on all other spins.) More precisely,
h
(1)
and
h
(2)
define a sequence of Hamiltonians
{
H
N
}
on in-
creasing chain lengths. The thermodynamic limit will be
taken by letting
N
grow to infinity.
In order to be completely unambiguous about what we
mean by the two terms
gapped
and
gapless
, we use a very
strong definition. For
{
H
N
}
to be gapless, we require
that there exists a finite interval of size
c >
0 above its
ground state energy
E
0
(
N
) such that the spectrum of
H
N
becomes dense therein as
N
goes to infinity, in the
sense that any value in the interval [
E
0
(
N
)
,E
0
(
N
) +
c
] is
arbitrarily well approximated by a
N
-dependent sequence
of eigenvalues of
H
N
. In contrast,
{
H
N
}
is gapped if there
exists
γ >
0 such that for all
N
∈
N
,
H
N
have a non-
degenerate ground state and a spectral gap ∆(
H
N
)
> γ
where ∆(
H
N
) is the difference in energy between the
(unique) ground state and the first excited state [
23
] (see
Fig. 1).
II. MAIN RESULT
Our main result is a construction of a nearest-
neighbour coupling
h
(2)
(
η
) and a single site term
h
(1)
(
η
),
parametrized by an integer
η
, with the guarantee that
each of the corresponding Hamiltonians
{
H
N
(
η
)
}
, de-
fined via
(1)
, is either gapped or gapless according to
the definitions given above. For this particular class of
Hamiltonians, we show that determining which
η
corre-
spond to gapped instances and which
η
correspond to
gapless instances is as hard as determining whether a
given Turing machine halts, a problem known as the Halt-
ing problem. Since the latter problem is undecidable [
24
],
this immediately implies that the question of existence of
a spectral gap is also undecidable for 1D Hamiltonians,
both algorithmically, as well as in the axiomatic sense of
G ̈odel [25].
The construction of the interactions
h
(2)
(
η
) and
h
(1)
(
η
)
is based on an embedding of a fixed universal Turing
machine (UTM), in such a way that the spectral gap
problem for
{
H
N
(
η
)
}
encodes the behaviour of the UTM
when given
η
as an input: if the UTM halts on input
η
, then
{
H
N
(
η
)
}
will be gapless, while if the UTM does
not halt on input
η
, it will be gapped with spectral gap
uniform in
η
.
Moreover, we can show that
h
(2)
(
η
) and
h
(1)
(
η
) can be
choosen to be small quantum perturbations around of a
classical interaction (i.e. diagonal in the computational
basis), and that their depedence on
η
is only due to
some numerical factors. We present this explicit form,
toghether with a summary of the above discussion, in the
following theorem.
Theorem 1.
Fix a universal Turing machine (UTM).
There exist (explicitly constructible) nearest-neighbor in-
teractions
h
(2)
(
η
)
and a local term
h
(1)
(
η
)
, parametrized
by an integer
η
, such that
‖
h
(1)
(
η
)
‖ ≤
2
,
‖
h
(2)
(
η
)
‖ ≤
1
and the family of Hamiltonians
{
H
N
(
η
)
}
defined on a
spin chain with
N
sites and local dimension
d
by
H
N
(
η
) =
N
−
1
∑
i
=1
h
(2)
i,i
+1
(
η
) +
N
∑
i
=1
h
(1)
i
(
η
)
,
satisfies the following:
1.
if the UTM halts on input
η
, then
{
H
N
(
η
)
}
is gapless.
2.
if the UTM does not halt on input
η
, then
{
H
N
(
η
)
}
is
gapped. Moreover the spectral gap
∆(
H
N
(
η
))
≥
1
for
all
N
∈
N
.
The interactions
h
(2)
(
η
)
and
h
(1)
(
η
)
can be chosen to
be of the form
h
(1)
(
η
) =
a
+
β
(2
−
2
|
η
|
a
′
+
a
′′
)
,
(2)
h
(2)
(
η
) =
b
+
β
(2
−
2
|
η
|
b
′
+
b
′′
+
e
i
πφ
(
η
)
b
′′′
+ e
−
i
πφ
(
η
)
b
′′′†
+
e
i
π
2
−
2
|
η
|
b
′′′′
+ e
−
i
π
2
−
2
|
η
|
b
′′′′†
)
.
(3)
where
0
< β
≤
1
is any rational number (which can
be chosen arbitrarily small),
|
η
|
denotes the number of
digits in the binary expansion
η
=
η
1
η
2
...
η
|
η
|
,
φ
(
η
)
de-
notes its binary fraction with interleaved
1
s, i.e.
φ
(
η
) =
0
.
η
1
1
η
2
1
...
η
|
η
|−
1
1
η
|
η
|
, and
a
,
a
′
,
a
′′
are
d
×
d
matrices
and
b
,
b
′
,
b
′′
,
b
′′′
,
b
′′′′
are
d
2
×
d
2
matrices with the fol-
lowing properties:
3
FIG. 1. Competing spectra of gapless versus gapped phase
for the Hamiltonian
H
= (
H
C
+
H
dense
)
⊕
0 + 0
⊕
H
trivial
. a)
The system is gapped with ∆
>
0 and unique product ground
state. The thermodynamic limit is in a gapped phase. b) If
and only if the encoded universal Turing machine halts, there
exists a critical threshold system size after which the dense
spectrum of
H
C
+
H
dense
is pulled towards
−∞
as the system
size increases, covering up the gap in the spectrum of
H
trivial
.
The thermodynamic limit is in a gapless phase.
1.
a
and
b
are diagonal with entries in
Z
, i.e. they
correspond to a purely classical spin coupling.
2.
a
′
,
a
′′
,
b
′
,
b
′′
are Hermitian with entries in
Q
[
√
2
]
,
i.e. they are of the form
x
+
y
√
2
with
x
and
y
being
rational numbers.
3.
b
′′′
,
b
′′′′
have entries in
Q
.
Since the matrices constructed have entries in
Q
[
√
2
]
, they
can be specified by a finite description, which toghether
with the binary expansion of
η
completely determines the
interactions
h
(2)
(
η
)
and
h
(1)
(
η
)
.
As in the 2D case, we emphasize that, since
β
can
be an arbitrarily small parameter, the theorem proves
that even an arbitrarily small perturbation of a classical
Hamiltonian can have an undecidable spectral gap in the
thermodynamic limit. This also shows that even for classi-
cal Hamiltonians, the gapped phase is not stable in general
and is susceptible to arbitrarily small perturbations.
There have been many previous results over the
years relating undecidability to classical and quantum
physics [
22
,
26
–
49
]. We refer to the introduction of [
20
]
for a detailed historical account of these previous results.
So where is the difficulty in extending the two-
dimensional result of Cubitt
et al.
[19]
to one-dimensional
systems? One of the key ingredients in the 2D construc-
tion is a classical aperiodic tiling. The particular tiling
used in [
20
], due to Robinson [
50
], exhibits a fractal struc-
ture, i.e. a fixed density of structures at all length scales.
This ingredient is crucial if one were to directly translate
the original undecidability result to a one-dimensional
system.
A Wang tile set [
51
] consists of a finite set of different
types of square tiles, each tile type having one colour
assigned to each of its four sides [
33
]. Translated to
Hamiltonians, the computational basis state at each site
indicates which tile is placed there; the interactions of the
corresponding tiling Hamiltonian are diagonal projectors
in the computational basis; each of these projectors con-
strains neighbouring sites to be in states that correspond
to a matching tile configuration (i.e. where two tiles can
only be placed next to each other if the colours of the
abutting sides match). A constant local dimension implies
we can only have a constant number of tiles and thus of
colors. But in 1D, as soon as any tile occurs a second time
along the chain, the entire pattern that followed that tile
previously can repeat indefinitely. (Conversely, just as
in 2D, if any finite segment cannot be tiled, then neither
can the infinite chain.) Thus the Tiling problem in 1D is
known to be decidable, even by a simple algorithm.
For this reason, an underlying tile set like the Robinson
tiles used in 2D—with patterns of all length scales—is im-
possible in 1D, under the physical constraint of retaining
a finite local dimension.
Quantum mechanics can in principle circumvent this
constraint, since entanglement can introduce long-range
correlations, even in unfrustrated qudit chains [
52
]. Yet
even though it is known that one can obtain correlations
between far-away sites that decay only polynomially, the
resulting Hamiltonians are gapless [53, 54].
The key new idea is a 1D construction, which we denote
the Marker Hamiltonian, that creates—within the sys-
tem’s ground state—a
periodic
partition of the spin chain
into segments, but whose length and period are related
to the halting time of a Turing machine. This subtle
interplay between the dynamics of a Turing machine, the
periodic quantum ground state structure and the energy
spectrum, plays the role of the classical aperiodic tilings
of the 2D construction.
The paper is organized as follows. In Section III we
present a summary of the construction and how it differs
from the 2D one. In Section IV we detail the construction
of the Marker Hamiltonian. In Section V we present the
modifications that are required to the encoding of UTM
into Hamiltonian interactions due to this modified set-up.
These two components will be combined in Section VI.
The main result on the undecidability of the spectral gap
will be proven in Section VII. Finally we present some
extensions to our result in Section VIII.
III. OUTLINE OF THE CONSTRUCTION
Let us now give an outline of how we circumvent the
problems in extending the 2D construction to 1D chains,
and present an overview of the different elements which
will be required to construct
h
(2)
(
η
) and
h
(1)
(
η
).
We start by presenting some background on Turing
machines and the Halting problem.
4
A. Turing machines
A (classical) Turing machine is a simple model of com-
putation consisting of an infinite “tape” divided into cells,
and a “head” which steps left or right along the tape. The
machine is always in one of a finite number of possible
“internal states”
{
q
i
}
Q
i
=1
. There is one special internal
state, denoted
q
f
, which tells the machine to halt when it
enters this state. Each cell can have one “symbol” written
in it, from a finite set of possible symbols
{
σ
Σ
i
=1
}
. A finite
table of “transition rules” determine how the machine
should behave for each possible combination of symbol
and internal state. At each time step, the machine reads
the symbol in the cell currently under the head and looks
up this symbol and the current internal state in the tran-
sition rule table. The transition rule specifies a symbol
to overwrite in the current cell, a new internal state to
transition to, and whether to move the head left or right
one step along the tape. The “input” to a Turing machine
is whatever symbols are initially written on the tape, and
the “output” is whatever is left written on the tape when
it halts.
Despite its apparent simplicity, Turing machines can
carry out any computation that it is possible to perform.
Indeed, Turing constructed a universal Turing machine
(UTM): a
single
set of transition rules that can perform
any desired computation, determined solely by the input.
Given an input
η
to a universal Turing machine
M
, the
Halting Problem asks whether
M
halts on input
η
.
B. Encoding of the Halting problem
We want to construct a Hamiltonian whose spectral gap
encodes the Halting Problem. More precisely, starting
from a fixed UTM
M
, we want to construct the interac-
tions
h
(2)
(
η
) and
h
(1)
(
η
) which define a 1D, translation-
ally invariant, nearest-neighbour, spin chain Hamiltonian
H
N
(
η
) =
H
N
(
M,
η
) on the Hilbert space
H
= (
C
d
)
⊗
N
,
such that
H
N
(
η
) is gapped in the limit
N
→ ∞
if
M
halts on input
η
, and gapless otherwise.
In the earlier 2D construction [
20
], this was accom-
plished by combining a trivial gapped Hamiltonian with
one that has a dense spectrum (and thus gapless). The
combined Hamiltonian has the property that the ground
state energy is the smallest of the two. The dense Hamilto-
nian is then modified such that, if
M
halts on input
η
, its
lowest eigenvalue is pushed up by a large enough constant,
revealing the gap present due to the trivial Hamiltonian.
In a non-Halting instance the dense spectrum Hamilto-
nian has the lowest ground state energy and therefore the
combined Hamiltonian remains gapless.
In order to modify the dense Hamiltonian in this fash-
ion, we have to construct a Hamiltonian whose ground
state energy is dependent on the outcome of a (quan-
tum) computation. This is possible thanks to Feynman
and Kitaev’s history state construction, used ubiquitously
throughout quantum complexity proofs [
6
–
9
,
55
–
59
]. In
brief, this construction allows one to take a circuit
C
with
gates
U
1
,...,
U
T
acting on
m
qubits, and embed it into
a Hamiltonian on
n
=
m
+
poly log
T
qubits, such that
the ground state is a superposition over histories of the
computation, i.e. a state of the form
|
Ψ
〉∝
∑
T
t
=0
|
t
〉|
ψ
t
〉
.
Every “snapshot” of the computation
|
ψ
t
〉
is entangled
with a so-called clock register
|
t
〉
. For
T
computational
steps, one can implement such a clock with a local Hamil-
tonian using
poly log
T
qubits. The state
|
ψ
0
〉
is thus
input to the circuit, and
|
ψ
t
〉
=
U
t
···
U
1
|
ψ
0
〉
is the state
of the circuit after
t
gates. A later construction due to
Gottesman and Irani
[8]
similarly encodes the evolution
of a quantum Turing machine, instead of a quantum cir-
cuit. As the transition rules of a Turing machine do not
depend on the head location, a benefit of encoding Tur-
ing machines rather than circuits is that the resulting
Hamiltonians are naturally translationally invariant.
By adding a projector to “penalize” a subset of the
possible outcomes of the computation, as encoded in
|
T
〉|
ψ
T
〉
, the ground state in these cases is pushed up in
energy by Θ(
T
−
2
). We denote this circuit Hamiltonian
with penalties with
H
C
=
H
C
(
M,
η
)—as it will be the
only term dependent on the free parameter
η
and our
chosen Turing machine
M
, set up such that
η
will serve
as input to
M
—and the Hilbert space it acts on with
H
C
.
The energy shift in
H
C
’s ground state can be exploited
by combining this circuit Hamiltonian with three more
Hamiltonians:
H
dense
with a non-negative and asymp-
totically dense spectrum on a Hilbert space
H
dense
, and
H
trivial
with a trivial zero energy ground state and gap
≥
1, on Hilbert space
H
trivial
. Then
H
N
(
M,
η
)
:
= (
H
C
(
M,
η
)+
H
dense
)
⊕
0+0
⊕
H
trivial
+
H
guard
is defined on the overall Hilbert space
H
:
= (
H
C
⊗H
dense
)
⊕H
trivial
.
In order to ensure that the low-energy spectrum of
H
N
is
determined
either
completely by
H
trivial
or
by the sum
H
C
+
H
dense
, we have added another local Hamiltonian
H
guard
acting on
H
with Ising-type couplings that penal-
ize states with “mixed” support (explicitly spelled out in
Theorem 25).
If the computation output in
H
C
is penalized, the dense
spectrum is pushed up, which in turn unveils the constant
spectral gap of some trivial Hamiltonian
H
trivial
, as shown
in Fig. 1.
Yet even though we can easily penalize an embedded
Turing machine reaching a halting state in this way (i.e.
by adding a penalty term for the head being in any termi-
nating state
q
f
), a history state Hamiltonian is insufficient
for the undecidability proof. i) The energy penalty de-
creases as the embedded computation becomes longer [
60
].
However, we require a constant energy penalty density
across the spin chain. ii) If we try to circumvent this
problem by subdividing the tape to spawn multiple copies
of the Turing machine, we need to know the space re-
quired beforehand in which the computation halts, if it
halts—which is also undecidable.
5
FIG. 2. 1D Robinson tiling analogue, the Marker Hamiltonian:
penalty between halting and not halting for the TM is
flipped
,
i.e. we penalize
not
halting (the TM head moves past the
available tape, or equivalently the clock driving the TM runs
out of space—see Remark 19). a) If the tape—delimited
by a black segment marker—is long enough for the TM to
terminate, there is no penalty. b) If the tape is too short, a
penalty will be inflicted due to the head running into the right
segment marker. c) Mixed-length segments, each delimited
with a segment marker. Those segments for which there is
insufficient tape space pick up a penalty due to halting. The
final construction introduces a small bonus for each segment,
which shrinks the longer the segment is, and which is always
smaller (in modulus) than the penalty that could be inflicted
on the TM running on the available tape. In the halting case,
this results in the lowest energy configuration being evenly-
spaced segments with just enough tape for the TM to halt. In
the non-halting case, a single segment is most favourable.
C. Amplifying the energy penalty
Cubitt
et al.
circumvent this problem by spawning
a fixed
density
of computations across an underlying
Robinson lattice. Like this, within every area
A
, the
halting case obtains an energy penalty
∝
A
—the ground
state energy density therefore differs by a constant for the
Halting and non-Halting cases, allowing the ground state
energy to diverge in the Halting case, which uncovers the
spectral gap. The fractal properties of the Robinson tiling
further ensure that that every possible tape length appears
with a non-zero density in the large system size limit, so
knowledge of the Turing machine’s required runtime space
is unnecessary.
We replace the fractal Robinson tiling with a 2-local
“marker” Hamiltonian
H
′
on (
C
c
)
⊗
N
, where the markers—
a special spin state
|
〉
—bound sections of tape used for
the Turing machine.
H
′
is diagonal with respect to bound-
ary markers—i.e.
H
′
commutes with
|
〉〈
|
. Thus any
eigenstate
|
ψ
〉
has a well-defined
signature
with respect to
these boundaries, where the signature
sig
|
ψ
〉
is defined as
the binary string with 1’s where boundaries are located,
and 0’s everywhere else. We construct
H
′
in such a way
that two consecutive markers bounding a segment will
introduce an energy bonus that falls off quickly as the
length of the segment increases: e.g. any eigenstate
|
ψ
〉
with a signature
sig
|
ψ
〉
= (
...,
0
,
1
,
0
,...,
0
,
1
︸
︷︷
︸
length
w
,
0
,...
)
will pick up a bonus of
exp
(
−
p
(
w
)) for some fixed polyno-
mial
p
. This bonus will be strictly smaller in magnitude
than any potential penalty obtained from a computation
running on the same segment of length
w
, i.e. when the
TM head runs out of tape (see Fig. 2).
D. Quantum phase estimation
To the marker Hamiltonian, we add a history state
Hamiltonian
H
prop
(
φ,M
). Here
φ
=
φ
(
η
) = 0
.
η
1
1
η
2
1
...
η
|
η
|
00
...
(4)
encodes an input parameter
η
∈
N
with
|
η
|
binary digits as
binary fraction, where the digits of
η
are interleaved by 1s.
The second parameter
M
is a classical universal Turing
machine. We construct
H
prop
to encode the following
computation:
1.
A Quantum Turing machine performs quantum
phase estimation (QPE) on a single-qubit unitary
that encodes the input
φ
.
2.
The classical universal TM
M
uses the binary ex-
pansion of
φ
as input and performs a computation
on it.
Up to a slight modification for 1. which we will explain
later, this is the same Turing machine construction as
in [
20
, sec. 6]. The Hamiltonian
H
prop
is set up to spawn
one instance of the computation per segment, and we
penalize the TM
M
running out of available tape up
to the next boundary marker with some local terms; as
before we denote the resulting local Hamiltonian with
H
C
. We finally add a trivial Hamiltonian
H
trivial
with
ground state energy
−
1 and constant spectral gap. The
overall Hamiltonian is then
H
N
=
β
(
μ
H
′
+
H
C
(
M,
η
) +
H
dense
)
⊕
0
+ 0
⊕
H
trivial
+
H
guard
,
where
μ
= 2
−|
φ
|
is a small constant, defined for
φ
(
η
) as
given in Eq. (4) with
|
φ
|
= 2
|
η
|
.
β >
0 can be chosen
arbitrarily small.
We will now explain how our construction differers dur-
ing the QPE step. QPE can be performed exactly when
there is sufficient tape [
61
]. In case there is insufficient
space for the full binary expansion of the input parameter
φ
, the output is truncated, and the resulting output state
is not necessarily a product state in the computational
basis anymore.
As in the 2D model, we have to allow for the possibil-
ity that the QPE truncates
φ
, possibly resulting in the
universal TM dovetailed to the QPE switching its behav-
ior to halting. In the 2D construction of [
20
], one could
circumvent this by simply subtracting off the energy con-
tribution from truncated phase-estimation outputs; yet
we cannot use this mechanism in our result, since it is not
possible in the 1D construction, since we cannot `a priori
6
−
.
1
−
.
01
−
.
001
0
.
001
.
01
.
1
1
∝
μ/T
3
∝
1
/T
3
∝−
μ/T
3+
δ
not halting:
̄
λ
min
(
T
)
w <
|
n
|
+ 5
w >
|
n
|
+ 5
−
.
1
−
.
01
−
.
001
0
.
001
.
01
.
1
1
∝
μ/T
3
∝
1
/T
3
→
0 (halted)
∝−
μ/T
3+
δ
T
halt
segment length
w
halting:
̄
λ
min
(
T
)
−
.
1
−
.
01
−
.
001
0
.
001
.
01
.
1
1
∝
μ/T
3
∝
1
/T
3
∝−
μ/T
3+
δ
not halting:
̄
λ
min
(
T
)
w <
|
n
|
+ 5
w >
|
n
|
+ 5
−
.
1
−
.
01
−
.
001
0
.
001
.
01
.
1
1
∝
μ/T
3
∝
1
/T
3
→
0 (halted)
∝−
μ/T
3+
δ
T
halt
segment length
w
halting:
̄
λ
min
(
T
)
<
0
FIG. 3. Energy contribution
̄
λ
min
(
T
) from a single segment of length
w
of the marker and TM Hamiltonian
μ
H
′
+
H
C
shown in
red, where
T
is the runtime of the encoded computation, bounded either by the segment length or by the halting time of the
TM. The prefactor
μ
= 2
−
2
|
η
|
is a small constant to compensate for the fact that on too short segments the phase estimation
truncates the output, which we can only penalize with strength Ω(
μ/T
3
). The dashed red line is the contribution of
H
C
, i.e. the
energy penalty inflicted in case of the Turing machine running out of space. The dashed blue line is the bonus from
μ
H
′
.
know the length of the segments on which the Turing
machine runs. Instead, we augment the QPE algorithm
by a short program which verifies that the expansion
has been performed in full, and otherwise inflicts a large
enough energy penalty to offset the case that the UTM
now potentially halts on the perturbed QPE output.
To this end, we make use of the specific encoding of
φ
:
the interleaved 1s are flags indicating how many digits
to expand. Like this, before the inverse quantum Fourier
transform, we know that the least-significant qubit is
exactly in state
|
+
〉
if the expansion was completed, and
has overlap at least
μ
= 2
−|
φ
|
with
|−〉
otherwise. By
adding a penalty term to the Hamiltonian for said digit in
state
|−〉
, we can penalize those segments with insufficient
tape for a full expansion of the input, independently of
whether the universal TM then halts or not on a faulty
input. This result manifests as a kink of the lower energy
bound for a too-short segment of length
w
in Fig. 3.
Yet since the marker Hamiltonian
H
′
is attenuated by
μ
as well, the energy remains nonnegative throughout for
these segments. Therefore, the only segments left to be
analyzed are those for which the input can be assumed
un-truncated.
E. Ground state energy analysis
When there is enough space for the QPE to be per-
mormed, there are two possibilities for the ground state
energy of
H
N
. In case
M
(
φ
) does
not
halt, any instance
of the TM running on any tape length will run out of tape
space, incurring the penalty explained in Fig. 2. This
halting penalty will always dominate the bonus coming
from the segment length, and we show the ground state
energy to be
λ
min
(
H
N
)
≥
0. In case the TM
does
halt,
there will be minimal segment length
w
halt
above which
7
segments will not pick up the penalty from exhausting the
tape. Since the bonus given by the Marker Hamiltonian
is decreasing with increasing segment length, the optimal
energy configuration will therefore be achieved by parti-
tioning the whole chain into segments of length
w
halt
, each
of which picks up a tiny—but finite—negative energy con-
tribution. We prove
λ
min
(
H
N
)
<
−b
N/w
halt
c
Ω(1
/T
3
halt
)
in that case, where
T
halt
is the number of computation
steps till halting. As the system size
N
increases, the
ground state energy will therefore diverge to
−∞
.
The the claims of Theorem 1 will then follow by com-
bining the construction outlined with a trivial, gapped
Hamiltonan and a dense spectrum, gapless Hamiltonian.
The dense spectrum Hamiltonian will be modified to have
ground state energy determined by the outcome of the
computation of the QTM running on the tape segments
defined by the Marker Hamitonian, so that the low-energy
part of the spectum of the combined Hamiltonian will be
gapped or gapless depending on whether the UTM halts
or not.
IV. MARKER TILING
In this section we will give an explicit construction of
the Marker Hamiltonian.
A. Concept
In order to spawn a fixed density of computations in 1D
without the aid of a fractal underlying structure, we need
to know an optimal segment length to subdivide the spin
chain into. In the halting case, this should be just enough
tape for the computation to terminate. However, if we
aim to construct a reduction from the Halting Problem,
we cannot know the space required beforehand—which,
in particular, could be uncomputably large, or infinite!
One way out is to spawn Turing machines on tapes of
all possible lengths,
and
do this with a fixed density. In
2D this can be achieved using an underlying fractal tiling
such as that due to Robinson [50], see Fig. 4.
The two-dimensional construction thus crucially de-
pends on one’s ability to create structures of all length
scales, in order to define “lines” of all sizes [
62
], which
are then used as a tape for running a Quantum Turing
machine: the key property of the fractal which makes the
construction work is that every possible tape length in-
deed appears with a non-zero density in the large system
size limit.
As already mentioned, constructing a fractal tiling with
a fixed density of structures of all length scales seems
impossible in one dimension. We therefore replace the
fractal Robinson tiling with a “marker” Hamiltonian,
where the markers bound sections of tape used for the
Turing machine (just like the lower boundaries of the
squares in Fig. 4). We will construct the Hamiltonian
in such a way that two consecutive markers bounding
a) non-halting
b) halting
c) non-halting
.
d) halting
.
FIG. 4. 2D Robinson tiling construction with instances of
a Turing machine running on the upper edges of the fractal
rectangles. Each edge represents the available tape for the
Turing machine. In the non-halting case a), there will never
be any halting penalty, no matter how much tape there is
available. In the halting case b), there is a threshold side
length after which each rectangle larger than the threshold
contributes a penalty (red)—which yields a small but nonzero
ground state energy density; the ground state energy diverges.
In the 1D case we show the segments emerging from the
Marker Hamiltonian from Section IV (cf. Fig. 2). In the non-
halting case c), no segment length is long enough to contain
the entire computation; all segments obtain a penalty (red).
In the halting case d), there is an ideal segment length (green)
with
just
enough tape tor the TM to halt; as per Fig. 3, this
segment has the maximum possible bonus. Segments too short
(red) contribute a net energy penalty, whereas segments too
long (magenta) do contribute a bonus, yet not one as large as
the optimal segment length.
8
a segment will introduce an energy bonus that falls off
quickly as the length of the segment increases. This
bonus will be weak enough to permit an executing QTM
to “extend” the tape as needed, in the sense that the
bonus due to the marker boundaries is strictly smaller in
magnitude than the potential penalty introduced when
the QTM head runs out of tape (see Fig. 2).
B. The Marker Hamiltonian
We now construct the Marker Hamiltonian. It will be
a local Hamiltonian
H
on a chain of qudits with a special
spin state
|
〉
, which we call a
boundary
, and which will
separate the different tape segments. For a product state
|
ψ
〉
, we define a
signature
with respect to these boundaries
as the binary string with 1’s where boundaries are located,
and 0’s everywhere else, which we will denote by
sig
|
ψ
〉
.
The Hamiltonian we construct will leave the signature
invariant, i.e.
sig
|
ψ
〉
=
sig
H
|
ψ
〉
for all
|
ψ
〉
. This property
allows us to block-diagonalize
H
with respect to states
of the same signature. For a given block signature, say
(1
,
0
,
0
,
0
,
1
,
0
,
0
,
1), the Hamiltonian gives an energy bonus
(i.e. a negative energy contribution) to each 1-bounded
segment, which is large when the boundary markers are
close, and becomes smaller the longer the segment. This
introduces a notion of boundaries that are “attracted” to
each other, and our goal is to have a falloff as
∼−
1
/g
(
l
) in
the segment’s length
l
, where
g
is a function we can choose.
In brief, “attraction”, in this context, simply means that
the energy bonus given by
H
to pairs of boundary symbols
grows the closer they are to each other.
For reasons of clarity, we start by constructing a Hamil-
tonian where the falloff is a fixed function
g
that is asymp-
totically bounded as Ω(2
l
)
≤
g
≤
O
(4
l
). In a second step,
we allow the falloff to be tuned, replacing
l
by an arbitrary
exponential in
l
, such that the falloff is
doubly
exponential
in the segment length.
C. Construction
We start with the following lemma.
Lemma 2.
Let
H
:
=
(
C
3
)
⊗
N
be a chain of
qutrits of length
N
with local computational basis
{|
〉
,
|
B
〉
,
|
I
〉}
, and for a product state
|
ψ
〉 ∈ H
,
|
ψ
〉
=
|
ψ
1
〉···|
ψ
N
〉
, we define a “boundary signature”
sig
|
ψ
〉
=
(
〈
|
ψ
1
〉
,...,
〈
|
ψ
N
〉
)
, extended linearly to
H
. Define two
local Hamiltonian terms
h
1
:
=
|
I
〉〈
I
|⊗
(
|
BB
〉−|
IB
〉
)(
〈
BB
|−〈
IB
|
)
h
2
:
=
(
|
IB
〉−|
II
〉
)(
〈
IB
|−〈
II
|
)
⊗|
〉〈
|
and set
h
walk
:
=
h
1
+
h
2
. Let
p
:
= 2
|
〉〈
|
+ 2
|
BI
〉〈
BI
|
+ 2
|
B
〉〈
B
|
Then
H
walk
+
P
:
=
N
−
2
∑
i
=1
1
{
1
,...,i
−
1
}
⊗
h
walk
⊗
1
{
i
+3
,...,N
}
+
N
−
1
∑
i
=1
1
{
1
,...,i
−
1
}
⊗
p
⊗
1
{
i
+2
,...,N
}
is a 3-local Hamiltonian which is positive semi-definite,
and block-diagonal with respect to the subspaces spanned
by states with identical signature
sig
.
Proof.
The first two claims are true by construction. The
Hamiltonian
H
walk
+
P
is further block-diagonal with
respect to
sig
because
sig
(
H
walk
+
P
)
|
ψ
〉
=
sig
|
ψ
〉 ∀|
ψ
〉∈
H
, as none of the local terms ever affect the subspaces
spanned by the boundary symbol
|
〉
.
As a second step, we employ a boundary trick by Gottes-
man and Irani
[8]
to ensure that blocks not terminated by
a boundary marker have a ground state energy at least 2
higher than
-terminated blocks. It is worth emphasizing
that this is not achieved by a term that
only
acts on the
boundary, but in a translationally-invariant way, i.e. by
adding the same one- and two-local terms throughout the
chain. In brief, it exploits the fact that while there are
N
spins in the chain, there is only
N
−
1 edges between
them. We state this rigorously in the following remark.
Remark 3
(Gottesman and Irani
[8]
)
.
Give an energy
bonus
of strength 4 to
|
〉
, and an energy
penalty
of
2
to
|
〉
appearing next to any symbol (including
itself. I.e.
if
|
〉
appears at the end of the chain there will be a net
bonus of
2
, otherwise a net penalty of zero). Collect these
terms in a Hamiltonian
P
′
. Then, apart from positive
semi-definiteness,
H
:
=
H
walk
+
P
+
P
′
(5)
where
H
walk
and
P
are defined in Lemma 2, has the
same properties claimed in Lemma 2, but any block not
terminated by a boundary will have energy
≥−
2
, while all
properly-terminated blocks will have a ground state energy
−
4
.
Proof.
The first claim is straightforward, as
P
′
does not
change the interaction structure of
H
. The last claim
follows from the fact that the only way of obtaining a
net bonus is to place a boundary symbol at the end of
the spin chain, where it picks up a net bonus of 2. The
maximum possible bonus of any state is thus 4, which
will be achieved by signatures that are properly bounded
on either side.
From now on, when we talk of “properly bounded”,
we always mean a signature with boundary blocks
at
each end. Individual cases where only one side carries a
boundary will be mentioned as such explicitly then.
9
D. Spectral Analysis
In the following, the “good” blocks will therefore be
those that have ground space energy
−
4, all of which aFre
properly bounded. Remark 3 allows us to analyze the
blocks more closely, which we do in the following lemma.
Lemma 4.
Let
H
=
H
walk
+
P
+
P
′
be as in Eq.
(5)
. If
we write
H
=
⊕
s
∈{
0
,
1
}
N
H
s
as the block-decomposition
of
H
, where
s
denotes an arbitrary length
N
binary string,
then every properly bounded block will either
1.
have two consecutive boundaries, and thus a ground
state energy
≥−
2
, or
2.
have signature of consecutive
1
-bounded segments
of
0
s. In this case,
H
s
further block-diagonalizes
into
H
s
=
G
s
⊕
R
s
, where
R
s
is within the span
of states penalized by
P
in Lemma 2, and
G
s
in its
kernel.
3. The ground state energy of
R
s
is
≥−
2
.
4.
The ground state energy of
G
s
equals
−
4
, and
G
s
will be a sum of terms of the form
1
{
1
,...,l
}
⊗
∆
w
⊗
1
{
l
+
w
+1
,...,N
}
, where
∆
w
is the Laplacian of
a path graph of length
w
(i.e. a graph with vertices
{
1
,...,w
}
and edges
{
(
i,i
+ 1) :
i
= 1
,...,w
−
1
}
).
Here
l
and
w
depend on the signature
s
—more pre-
cisely, for every contiguous section of
0
s in
s
sur-
rounded by a pair of
1
s,
l
marks the left
1
and
w
is
the length of the section of
0
s.
Proof.
If there are two neighbouring 1s in the signature
s
, the penalty term
|
〉〈
|
picks up an energy con-
tribution of 2. Since
H
prop
is already positive semi-
definite and block-diagonal with respect to signatures,
any state
|
ψ
〉
with support fully contained in the block
corresponding to signature
s
must thus necessarily satisfy
〈
ψ
|
H
|
ψ
〉≥〈
ψ
|
P
|
ψ
〉≥
2. The first claim follows.
So let us assume that all 1s are spaced away from each
other with at least one 0. Within the 2-dimensional 0
subspace spanned by the local basis states
|
I
〉
and
|
B
〉
.
We note that the penalized substring
|
BI
〉
is also an
invariant, meaning that no transition rule can create or
destroy this configuration. Any state that, when expanded
in the computational basis, has at least one expansion
term with said substring will thus necessarily have
all
terms with this specific substring. The same arguments
holds for the invariant substring
|
B
〉
, and the second
claim follows.
Since any eigenstate of
R
s
picks up the full penalty
contribution of 2, the third claim follows.
If neither of the invariant substrings
|
BI
〉
and
|
B
〉
occur, we can assume that all 1-bounded segments of 0s
lie within the span of the states
|
IBB
···
BB
〉
,
|
IIB
···
BB
〉
,...
...,
|
III
···
IB
〉
,
|
III
···
II
〉
.
(6)
Since there is no penalty acting on any of those states,
the ground state energy of
G
s
equals
−
4.
Each such segment of contiguous 0s thus defines a sep-
arate path graph, where the vertices are precisely these
states, linked by the transition rules given in
H
walk
in
Lemma 2. Denote the path graphs corresponding to these
segments with
G
1
,...,G
n
, where we assume that there
are
n
1-bounded segments of 0s in signature
s
. As each
segment is independent of the others, the overall graph
spanned by these individual paths is the Cartesian prod-
uct of the individual paths, i.e.
G
=
G
1
G
2
...
G
n
.
This is precisely a hyperlattice with side lengths uniquely
determined by the lengths of the individual segments.
The transition rules in
h
walk
therefore result in a block
G
s
= ∆
G
, i.e. the Hamiltonian is precisely the Laplacian
of the graph of determined by the transition rules (for an
extensive analysis see e.g. [
9
]). We further know that the
Laplacian of a Cartesian product of graphs decomposes
as
∆(
G
) = ∆(
G
1
)
⊗
1
⊗
...
⊗
1
+
1
⊗
∆(
G
2
)
⊗
1
⊗
...
⊗
1
+
...
...
+
1
⊗
...
⊗
1
⊗
∆(
G
n
)
,
(7)
and the last claim follows.
A more direct route to Eq. (7) is to note that
H
walk
is by definition the Laplacian of a graph with vertices
given by strings of the alphabet
{
,
B
,
I
}
, and edges by
the transition rules in Lemma 2. Those connected graph
components that do not carry a penalty due to an invalid
configuration (which either holds for
all
vertices, or
none
)
are lattices in
n
dimensions—where
n
is the number of
1-bounded segments—and side lengths determined by the
segments’ lengths. Eq. (7) is precisely the Laplacian of
this grid graph.
For the sake of clarity, we will keep calling the segments
of consecutive zeros bounded by
on either side “1-
bounded segments”, and when talking about the entire
string we use the term “properly bounded”. We will
henceforth re-label the states in Eq. (6) as
|
1
〉
,...,
|
w
〉
,
where
w
denotes the length of the segment. Our next
step will be to add a 2-local bonus term which gives an
energy bonus to the arrow appearing to the left of the
boundary, i.e. to
|
I
〉
.
Lemma 5.
Define
H
′
:
=
H
+
P
′′
+
B
, where
•
H
is taken from Eq.
(5)
,
•
P
′′
= 1
/
2
∑
N
i
=1
|
〉〈
|
i
gives a penalty of
1
/
2
to
any boundary term, and
•
B
=
−
∑
N
−
1
i
=1
|
I
〉〈
I
|
i,i
+1
gives a bonus of 1 to
states where the arrow has reached the right bound-
ary.
Then
10
1.
H
′
is still 3-local and block-diagonal in signatures,
i.e.
H
′
:
=
∑
s
H
′
s
. If
s
is properly bounded and has
no double
11
s, the corresponding block decomposes
as
H
′
s
=
G
′
s
⊕
R
′
s
similar to Lemma 4, but such
that the primed versions carry the extra penalties
and bonus terms.
2. For any such
s
,
R
′
s
≥
G
′
s
+ 2
.
3.
G
′
s
breaks up into sum of terms of the form
1
⊗
∆
′
w
⊗
1
, where
∆
′
w
is a perturbed path graph Laplacian
∆
′
w
:
= ∆
w
−|
w
〉〈
w
|
(where
|
w
〉
labels the last of the
basis states given in Eq.
(6)
, as mentioned).
Proof.
The first two claims follow immediately from
Lemma 4, since all of the newly-introduced terms leave
signatures and penalized substrings invariant, and are at
most 2-local.
Since the Cartesian graph product is associative and
commutative, it is enough to show the decomposition for
the case of two graphs
G
1
and
G
2
, and a single vertex
v
∈
G
1
which we want to give a bonus of
−
1 to. Denote
the bonus matrix for
G
1
with
B
1
. We have that the
adjacency matrix
A
G
1
G
2
=
A
G
1
⊗
1
+
1
⊗
A
G
2
. Vertex
v
is thus mapped to a family of product vertices (
v,v
′
)
v
′
∈
G
2
,
which are precisely the corresponding bonus’ed vertices
in
G
=
G
1
G
2
that have to receive a bonus of
−
1. The
bonus term for
G
is thus
B
=
B
1
⊗
1
, and the claim
follows.
We know that any Laplacian eigenvalues
μ,ν
of two
graphs
G
1
,G
2
combine to a Laplacian eigenvalue
μ
+
ν
of
G
1
G
2
(see e.g. [
63
, Ch. 1.4.6]). It is straightforward
to extend this fact to the case of bonus’ed graphs, which
will allow us to analyse the spectrum of each signature
block
H
′
s
.
The reader will have noticed that in contrast to
Lemma 4, Lemma 5 does not make any claims about
the ground state energy of the individual blocks. Na ̈ıvely,
one could assume that the ground state energy of each
block will diverge to +
∞
with the number of boundaries
present, as each of them carries a penalty of +1
/
2—but
how does this balance with the bonus of
−
1, which we
apply to only a
single
basis state in the graph Laplacian’s
ground space, and not on each vertex?
In order to answer this question, let us step back for a
moment and develop a bound for the lowest eigenvalue of
a modified path graph Laplacian ∆
′
w
. We will do this in
a series of technical lemmas.
Lemma 6.
∆
′
w
has precisely one negative eigenvalue.
Proof.
Assume this is not the case. Then there exist
at least two eigenvectors
|
u
〉
,
|
v
〉
with negative eigenval-
ues, and any
|
x
〉∈
span
{|
u
〉
,
|
v
〉}
satisfies
〈
x
|
∆
′
w
|
x
〉
<
0.
Since
dim ker
|
w
〉〈
w
|
=
w
−
1, there exists a nonzero
|
x
〉 ∈
span
{|
u
〉
,
|
v
〉}
such that
|
w
〉〈
w
||
x
〉
= 0. There-
fore 0
>
〈
x
|
∆
′
w
|
x
〉
=
〈
x
|
∆
w
|
x
〉
, contradiction, since ∆
w
is positive semi-definite.
As a next step, we will lower-bound the minimum
eigenvalue of ∆
′
w
.
Lemma 7.
The minimum eigenvalue of
∆
′
w
satisfies
λ
≥−
1
/
2
−
2
−
w
.
Proof.
We first observe that ∆
′
w
is tridiagonal, e.g.
∆
′
5
=
1
−
1 0
0
0
−
1 2
−
1 0
0
0
−
1 2
−
1 0
0
0
−
1 2
−
1
0
0
0
−
1 0
.
We can thus expand the determinant
p
w
(
λ
)
:
=
det
(∆
′
w
−
λ
1
) using the continuant recurrence relation (see [
64
,
Ch. III])
f
0
:
= 1
f
1
:
=
λ
−
1
f
i
:
= (
λ
−
2)
f
i
−
1
−
f
i
−
2
p
w
(
λ
)
:
=
λf
w
−
1
−
f
w
−
2
As can be easily verified, a solution to this relation is
given by the expression
p
w
(
λ
) =
−
2
−
w
−
1
√
λ
−
4
(
3
√
λz
−
w
(
λ
) +
√
λ
−
4
z
+
w
(
λ
)
)
(8)
where
z
+
w
(
λ
)
:
=
x
w
(
λ
) +
y
w
(
λ
),
z
−
w
(
λ
)
:
=
x
w
(
λ
)
−
y
w
(
λ
),
and
x
w
(
λ
) =
(
λ
−
√
λ
−
4
√
λ
−
2
)
w
y
w
(
λ
) =
(
λ
+
√
λ
−
4
√
λ
−
2
)
w
.
There is of course no hope to resolve
p
w
(
λ
) = 0 for
λ
directly, so we go a different route. First note that
p
w
(
λ
)
is necessarily analytic, since it is the characteristic polyno-
mial of ∆
′
w
. We can calculate
p
w
(
−
1
/
2) = (
−
1)
1+
w
2
−
w
,
and thus know that
sign
p
w
(
−
1
/
2) = 1 for
w
odd, and
−
1 for
w
even. If we can show that
p
w
(
−
1
/
2
−
1
/
2
w
)
has the opposite sign, then by the intermediate value
theorem we know there has to exist a root on the interval
[
−
1
/
2
−
1
/
2
w
,
−
1
/
2], and the claim follows.
First substitute
p
w
(
−
1
/
2
−
1
/
2
w
) =:
A
w
/B
w
, where
B
w
= 2
w
+1
√
2
−
w
+
9
2
,
A
w
=
−
a
1
,w
(
x
′
w
−
y
′
w
)
−
a
2
,w
(
x
′
w
+
y
′
w
)
,
a
1
,w
= 3
√
2
−
w
+
1
2
,
a
2
,w
=
√
2
−
w
+
9
2
,
x
′
w
=
(
√
2
−
w
+
9
2
√
2
−
w
+
1
2
−
2
−
w
−
5
2
)
w
,
y
′
w
=
(
−
√
2
−
w
+
9
2
√
2
−
w
+
1
2
−
2
−
w
−
5
2
)
w
.