Analysis and limitations of modified
circuit-to-Hamiltonian constructions
Johannes Bausch
1
and Elizabeth Crosson
2
1
DAMTP, CQIF, University of Cambridge
2
IQIM, California Institute of Technology
September 19, 2018
Feynman’s circuit-to-Hamiltonian construction connects quantum computation and ground
states of many-body quantum systems. Kitaev applied this construction to demonstrate
QMA
-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show
the equivalence of adiabatic computation and the quantum circuit model. In this work, we
analyze the low energy properties of a class of modified circuit Hamiltonians, which include
features like complex weights and branching transitions.
For history states with linear clocks and complex weights, we develop a method for
modifying the circuit propagation Hamiltonian to implement any desired distribution over
the time steps of the circuit in a frustration-free ground state, and show that this can be
used to obtain a constant output probability for universal adiabatic computation while
retaining the
Ω(
T
−2
)
scaling of the spectral gap, and without any additional overhead in
terms of numbers of qubits.
Furthermore, we establish limits on the increase in the ground energy due to input and
output penalty terms for modified tridiagonal clocks with non-uniform distributions on the
time steps by proving a tight O
(
T
−2
)
upper bound on the product of the spectral gap and
ground state overlap with the endpoints of the computation. Using variational techniques
which go beyond the
Ω(
T
−3
)
scaling that follows from the usual geometrical lemma, we
prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound.
We review the formalism of unitary labeled graphs which replace the usual linear clock
by graphs that allow branching and loops, and we extend the O
(
T
−2
)
bound from linear
clocks to this more general setting. In order to achieve this, we apply Chebyshev polyno-
mials to generalize an upper bound on the spectral gap in terms of the graph diameter to
the context of arbitrary Hermitian matrices.
Johannes Bausch: jkrb2@cam.ac.uk
Elizabeth Crosson: crosson@caltech.edu
Accepted in Quantum 2018-08-03, click title to verify 1
arXiv:1609.08571v3 [quant-ph] 18 Sep 2018
Contents
1 Introduction 2
2 Results and Overview 4
2.1 Background and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Non-Uniform Circuit Histories . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.2 Universal Adiabatic Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.3 Tightness of the Geometrical Lemma . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.4 Limitations on Further Improvements . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Non-Uniform Circuit Histories for Improving the UNSAT Penalty 10
3.1 Analysis of Modified Feynman Hamiltonians . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Metropolis Hamiltonians with Target Ground State Distributions . . . . . . . . . . . . . 11
3.3 Explicit Construction of an Ω(T
−2
) UNSAT Penalty Circuit Hamiltonian . . . . . . . . 12
4 Universal Adiabatic Computation 13
5 Tightness of the Geometrical Lemma for the UNSAT Penalty 17
5.1 A Tight Bound for the Clock Hamiltonian . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 A Tight Bound for the Full Circuit Hamiltonian . . . . . . . . . . . . . . . . . . . . . . 18
5.2.1 Block-Decomposition of the Full Circuit Hamiltonian . . . . . . . . . . . . . . . . 18
5.2.2 An Ω(T
−2
) Promise Gap for Kitaev’s Hamiltonian . . . . . . . . . . . . . . . . . 19
6 Limitations on Further Improvement 22
6.1 Linear Clock Registers with Endpoint Penalties . . . . . . . . . . . . . . . . . . . . . . . 22
6.2 Diameter Bounds for simple generalized ULGs . . . . . . . . . . . . . . . . . . . . . . . 25
6.3 A Clock Diameter Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.4 Frustrated ULGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
7 Outlook 29
8 Acknowledgements 30
References 31
A Appendix 33
1 Introduction
The initial demonstration of QMA-completeness of the local Hamiltonian problem [1] was followed by a
period of development during which the main goal was to broaden the class of interaction terms which
suffice to make the local Hamiltonian problem QMA-complete [2, 3]. These results were motivated in
part by a desire to understand the hardness of approximating physical systems that resemble those
found in nature, and also by the goal of making the closely related universal adiabatic computation
construction [4] more suitable for eventual physical implementation [5]. The success of these efforts
Accepted in Quantum 2018-08-03, click title to verify 2
have resulted in QMA-complete local Hamiltonian problems with restricted properties such as 2-local
interactions [2], low dimensional geometric lattices [3, 6], and translational invariance, as well as a
complete classification of the complexity of the 2-local Hamiltonian problem for any set of interaction
couplings [7].
This great success in classifying the hardness of physically realistic interactions stands in contrast
with the relative lack of progress in resolving questions related to the robustness of quantum ground
state computation, such as whether fault-tolerant universal adiabatic computing is possible, or to prove
or disprove the quantum PCP conjecture [8]. Such questions motivate us to seek (or to limit the possi-
bility of) improvements to the circuit-to-Hamiltonian construction itself, which serves a foundational
role in all of the results listed above. Based on ideas by Feynman [9] and cast into its current form by
Kitaev [1], the construction remains relatively little changed, having undergone only some gradual evo-
lutions since its modern introduction [6, 10–15]. Only recently steps have been undertaken to analyse
modifications in depth [16], and revisit the spectral properties of Kitaev’s original construction [17].
To encode computation robustly the circuit-to-Hamiltonian construction should not only have a
ground space representing valid computations, but intuitively it should penalize invalid computations
with as high of an energy as possible. One way of formalizing this condition is to add constraints
on the input and the output of the circuit that cannot be simultaneously satisfied under the valid
operation of the circuit. If the Hamiltonian enforces the correct operation of the circuit gates, then the
input and output constraints that contradict each other should not be satisfiable by any state, and so
the ground state energy should increase. This explains why the higher ground state energy associated
with non-accepting circuits can be regarded as an energy penalty against invalid computations, which
we call the “quantum UNSAT penalty”.
The specific role of the
Ω(
T
−3
)
scaling of the quantum UNSAT penalty in Kitaev’s proof is to show
that the local Hamiltonian problem is QMA-hard with a promise gap that scales inverse polynomially
in the system size. While there exists a well-defined relation between runtime T and the corresponding
Hamiltonian’s system size n for any specific set of constructions—e.g. Kitaev’s 5-local one—the explicit
scaling of this gap with T is not meaningful to the local Hamiltonian problem beyond the fact that
it is polynomial, since the local Hamiltonian problem promise gap is parameterized by the number of
qubits n, i.e. 1/ poly n.
Nevertheless, the scaling of the quantum UNSAT penalty with T is a well defined feature of any
particular circuit-to-Hamiltonian construction, and therefore we take the view that it is a reasonable
metric for exploring the space of possible improvements to this construction. The goal of this paper is
to answer a series of specific questions revolving around the UNSAT penalty.
1. Is the geometrical lemma tight for Kitaev’s original construction?
2. Can the circuit-to-Hamiltonian construction be improved with regard to universal adiabatic
computation?
3. Can we modify the Feynman-Kitaev construction—by introducing clock transitions with varying
weights, or by adding branching or loops as analysed in the context of unitary labeled graphs—in
order to improve on the known Ω(T
−3
) bound on the UNSAT penalty?
In the next section, we motivate each of these questions and formally state our results.
Accepted in Quantum 2018-08-03, click title to verify 3
2 Results and Overview
2.1 Background and Notation
We analyze history state Hamiltonians on a bipartite Hilbert space H
=
T +1
⊗H
q
, which are called
clock and quantum register, respectively. In the bulk of this paper, we consider history states consisting
of an arbitrary complex superposition of the time steps of a computation,
|ψi =
T
X
t=0
ψ
t
|ti ⊗ (U
t
···U
1
) |ξi, (1)
where as usual U
T
, . . . , U
1
are (local) quantum gates, |ξi is an arbitrary input to the computation, and
|ψi is a normalized state, so that in particular π
t
:=
ψ
∗
t
ψ
t
is a probability distribution over {
0
, . . . , T }.
Hamiltonians with ground states of the form as in eq. (1) arise from modifications to the usual terms
of the Feynman circuit Hamiltonian,
H
prop
:=
T
X
t=0
a
t
|tiht| ⊗ +
T −1
X
t=0
b
t
|t + 1iht| ⊗ U
t
+ b
∗
t
|tiht + 1| ⊗ U
†
t
, (2)
where we restrict |a
t
|, |b
t
| ≤
1
for t
= 0
, . . . , T . Note that most if not all of the constructions that
break down the O
(
log n
)
-local time register interactions to a k-local Hamiltonian— such as the domain
wall clock which leads to a 5-local circuit Hamiltonian—can be directly applied to the modified form
eq. (2), up to a constant prefactor (see eq. (7)). In lemma 2, we show that H
prop
in eq. (2) is unitarily
equivalent to a Hamiltonian H
clock
⊗
q
—i.e. acting trivially on the quantum register—where
H
clock
=
T
X
t=0
a
t
|tiht| ⊗ +
T −1
X
t=0
(b
t
|t + 1iht| + b
∗
t
|tiht + 1|). (3)
In addition to the part of the Hamiltonian which checks the propagation of the circuit, projectors
H
in
:=
|0ih0|⊗
Π
in
and H
out
:=
|T ihT |⊗
Π
out
can be added to H
prop
to validate specific inputs and the
outputs of the computation. We define the sum of all these terms to be the modified Feynman-Kitaev
Hamiltonian,
H
FK
:= H
prop
+ H
in
+ H
out
, (4)
as opposed to the Feynman circuit Hamiltonian in eq. (2), which is just the propagation part H
prop
without the penalties.
More specifically, the ground space of H
prop
+
H
in
will be spanned by computations starting from a
valid input computation (i.e. those for which |ξi ∈ ker
Π
in
in eq. (1)), and H
out
will raise the energy of
the state |ψi in eq. (1) when U
T
···U
1
|ξi 6∈ ker
Π
out
. The magnitude of this frustration between the
incompatible ground spaces of H
in
+
H
prop
and H
out
will depend on the circuit encoded by H
FK
and
the specific in- and output energy penalties, i.e. the maximum acceptance probability of the circuit
:= max
|ξi∈ker Π
in
|ηi∈ker Π
out
= hη|U
T
···U
1
|ξi.
In the following definition we take the
Π
in
and
Π
out
that are used in the standard construction:
Π
out
:=
|0ih0| measures a single qubit and penalizes it in state |0i (i.e. “not accepted”), and
Π
in
constrains a fraction of the input qubits to the |0i state as ancillas, some to an encoded string describing
the problem instance, and leaves the rest of the input qubits unconstrained to act as a witness, which
Accepted in Quantum 2018-08-03, click title to verify 4
allows the embedded computation to act as a verifier circuit for e.g.
QMA
or
QMA
EXP
verification
purposes.
For a specific set of fixed in- and output constraints and fixed runtime length T , we want to
identify the circuit Hamiltonian best suitable to discriminate accepting and rejecting circuit paths,
independent of the particular circuits used. Let >
0
be some acceptance probability. We define the
quantity C
(
, T
)
to be the set of those circuits of size T , for which the maximum acceptance probability
amongst any states obeying the in- and output constraints Π
in
and Π
out
is precisely :
C(, T ) := {U
1
, . . . , U
T
: max
|ξi∈ker Π
in
|ηi∈ker Π
out
|hξ|U
1
···U
T
|ηi|
2
= }.
Note that we allow the U
i
to be completely arbitrary—the precise action of the circuit, whether it
performs Grover search or is just a random set of gates, is irrelevant for C
(
, T
)
as we have defined
it here. This makes sense: we want to completely decouple the notion of how well a modified circuit
Hamiltonian can penalize in- and output from what the circuit itself does.
This leads to our definition of the quantum UNSAT penalty of a circuit-to-Hamiltonian construction,
which quantifies the extent to which a Hamiltonian as in eq. (2) can enforce the input and output
penalties described above for an arbitrary circuit.
Definition 1.
Let the
E
(
H
FK
) and
E
(
H
prop
) be the ground state energies of
H
FK
and
H
prop
, respec-
tively, and define the quantum UNSAT penalty E
p
(, T )
E
p
(, T ) := min
U
1
,...,U
T
∈C(,T )
E(H
FK
) − E(H
prop
).
The reason for explicitly subtracting the energy term E
(
H
prop
)
is that this quantity is not necessar-
ily zero for propagation Hamiltonians of the form (2), and so in these cases of frustrated propagation
terms the UNSAT penalty is defined to be the additional energy due to the rejection probability of
the circuit.
1
2.2 Results
2.2.1 Non-Uniform Circuit Histories
Our first step in analyzing the UNSAT penalty of modified Feynman Hamiltonians is to apply a
modified version of the argument used in the standard construction (see [1, sec. 14.4]) to “undo” the
computation and show that H
prop
is unitarily equivalent to a clock Hamiltonian which acts trivially
on the computational register.
Lemma 2.
If
W
:=
P
T
t=0
|tiht|⊗
(
U
t
···U
1
), then
W
is unitary and
W
†
H
prop
W
=
H
clock
⊗
, where
the clock Hamiltonian H
clock
is given by eq. (3).
Next we apply the same geometrical lemma used in Kitaev’s proof to lower bound the UNSAT
penalty of modified Feynman Hamiltonians.
Lemma 3.
If the spectral gap of the corresponding clock Hamiltonian
H
clock
(
T
)—denoted ∆
H
(
T
)—is
less than the (constant) spectral gap of H
in
+ H
out
, then
∆
H
(T )
4
(1 −
√
) × min{π
0
, π
T
} ≤ E
p
(, T ) ≤ E (H
clock
(T ) + |0ih0| + |T ihT |) . (5)
1
The term “UNSAT” derives from the related QUNSAT
ψ
=
P
e∈E
hψ| h
e
|ψi /|E|
quantity that was previously defined
and analyzed using the detectability lemma [18]. We use the term UNSAT penalty to emphasize that it is the energy
difference between accepting and non-accepting computations.
Accepted in Quantum 2018-08-03, click title to verify 5
The upper bound follows from the operator inequalities
Π
in
and
Π
out
, and it says that the
increase in the ground state energy due to the penalty terms is bounded by the case when all of the
frustration is in the system’s time register. The lower bound states that the UNSAT penalty can be
increased either by boosting the spectral gap of the clock Hamiltonian, or by amplifying the overlap
of the ground state with the beginning and ending time steps of the computation (i.e. modifying the
ground state |ψ
0
i of H
prop
such that hψ
0
|
Π
in
|ψ
0
i is maximized, and analogously for
Π
out
). To see
that the overlap with the endpoints of the computation can be made arbitrarily close to one, we prove
that it is in fact possible to construct a clock Hamiltonian with an arbitrary distribution as its ground
state.
Lemma 4.
For any probability distribution
µ
with support everywhere on its domain
{
0
, . . . , T }
, there
is a choice of coefficients
{a
t
, b
t
}
T
t=0
in eq. (3) such that
H
clock
is stoquastic and frustration-free and
has a ground space spanned by states of the form eq. (1) with weights ψ
t
=
√
µ
t
.
Using lemma 4 we exhibit a modified Hamiltonian for a target ground state distribution with
π
0
, π
T
≥
1
/
4
, and show that it has a spectral gap that is
Ω(
T
−2
)
to establish our first main result;
in order to prove it, we use the geometrical lemma for modified Feynman Hamiltonians, a by now
standard but central proof technique that is used ubiquitously in hardness constructions of the local
Hamiltonian problem.
Theorem 5.
There is a frustration-free modified circuit Hamiltonian as in eq. (2) with an UNSAT
penalty E
p
(, T ) that is Ω((1 −
√
)T
−2
).
In appendix A.1 we use the geometrical lemma to show that padding the standard circuit-to-
Hamiltonian construction with T input and output penalties also achieves an
Ω(
T
−2
)
scaling of the
UNSAT penalty.
2.2.2 Universal Adiabatic Computation
The modified circuit Hamiltonian used in theorem 5 also has a potential advantage for universal adi-
abatic computation (AQC). The original construction of universal AQC linearly interpolates between
the initial H
init
:= H
in
constraint and the final Hamiltonian H
final
:= H
in
+ H
prop
,
H(s) = (1 − s)H
init
+ sH
final
. (6)
By initializing the system in the ground state of H
init
at s = 0, and increasing s to 1 in a continuous
fashion and sufficiently slowly, the system will remain near its instantaneous ground state. This requires
the total time for s to rise from 0 to 1 to scale as poly
(
n,
∆
−1
min
)
, where
∆
min
:=
min
s
∆
H(s)
and n the
system’s size. In [4] it is proven that
∆
min
= Ω(
T
−2
)
for the linear interpolation (6) and the standard
H
prop
from Kitaev’s construction.
Since the goal of universal AQC is to efficiently produce the state at the final adiabatic time s
= 1
,
one needs to measure the clock register and condition success on finding the computation in its final
clock state, i.e. t
=
T . It would appear that this happens with probability only
1
/T for the standard
construction, but this can be improved to any
Ω(1)
probability by the “padding with the identity”
trick, e.g. by dovetailing the computation by a series of identity gates for t
=
T, . . . ,
4
T . This padding
increases the length of the clock (and hence the number of qubits needed to represent it) by a constant
factor. This is where the modified circuit Hamiltonian from theorem 5 leads to an improvement: by
tuning the couplings of the clock Hamiltonian, it is possible to create an arbitrarily high probability
of finding the system in the final configuration at t
=
T , without any increase in the size of the clock.
Accepted in Quantum 2018-08-03, click title to verify 6
To show that this works we need to lower bound
∆
min
for this modified construction, resulting in the
following theorem.
Theorem 6.
For any probability
p >
0 there is a frustration-free modified circuit Hamiltonian as
in eq. (2) with
π
T
=
p
such that the minimum spectral gap of the linear interpolation
(6)
satisfies
∆
min
= Ω(T
−2
).
2.2.3 Tightness of the Geometrical Lemma
A natural question is whether the lower bound given by the geometrical lemma is asymptotically tight—
Ω(
T
−3
)
, as stated e.g. in Kitaev’s original paper [1]—for (uniform weight) Feynman Hamiltonians. We
show that this is not the case. As a first step we apply an improved analysis to Kitaev’s original
construction with uniform weights,
H
prop
=
T −1
X
t=0
|tiht| ⊗ + |t + 1iht + 1| ⊗ − |t + 1iht| ⊗ U
t
− |tiht + 1| ⊗ U
†
t
, (7)
|ψi =
1
√
T + 1
T
X
t=0
|ti ⊗ (U
t
. . . U
1
) |ξi (8)
and we find that E
(
H
FK
) = Ω(
T
−2
)
for H
prop
as in eq. (7). We capture this in the following theorem.
Theorem 7. The UNSAT penalty in Kitaev’s local Hamiltonian construction is Ω(T
−2
).
Note that this result has been independently proven using Jordan’s lemma type techniques by Caha,
Landau, and Nagaj [17] and us [19]. In this work, we include a direct proof not based on Jordan’s
lemma, which can be found in appendix A.2.
2.2.4 Limitations on Further Improvements
Finally, by applying the lower bound in lemma 3 to modified Feynman Hamiltonians of the form in
eq. (2), we show that the scaling of the UNSAT penalty obtained in theorem 5 is the optimal scaling
that can be achieved.
Theorem 8.
Let
|ψi
be the ground state of a Hamiltonian
H
with eigenvalues
E
0
≤ E
1
≤ . . . ≤ E
T
.
If H is tridiagonal in the basis {|0i, . . . , |T i},
H :=
T
X
t=0
a
t
|tiht| +
T −1
X
t=0
(b
t
|t + 1iht| + b
∗
t
|tiht + 1|) ,
with
|a
t
|, |b
t
| ≤
1 for
t
= 0
, . . . , T
, then the product ∆
H
·min{|ψ|
2
0
, |ψ
T
|
2
}
of the spectral gap ∆
H
=
E
1
−E
0
and the minimum endpoint overlap is O(T
−2
).
Can this limitation for tridiagonal clock Hamiltonians be overcome using a clock that contains
branches and loops? In [15] it was shown that the circuit-to-Hamiltonian construction can in principle
be considered on arbitrary graphs, with the spectral properties of these circuit Hamiltonians reducing
to the analysis of the underlying graph. These unitary labeled graphs define circuits which evolve
according to unitary gates along their edges, see fig. 1. In this work we also consider generalized ULGs
Accepted in Quantum 2018-08-03, click title to verify 7
5 4
1
3
2
U
1
U
2
U
3
d
d
Figure 1: A graph
G
with five vertices
{
1
,
2
,
3
,
4
,
5
}
; if the assign unitaries to the edges—in this case three non-trivial
ones
U
1
, U
2
, U
3
∈ SU
(
d
), and
d
everywhere else—we call the graph a unitary labeled graph (ULG). Every edge
(
a, b
) with unitary
U
ab
is translated into a transition term
h
ab
:=
P
i
(
|ai |ii − |bi ⊗ U
ab
|ii
)(
h.c.
), where the
a
and
b take the role of the time register. If the product of unitaries along any loop—in this case only U
3
U
2
U
1
—equals
the identity
d
, the circuit Hamiltonian built from these transition terms
H
G
:=
P
(a,b)∈G
h
ab
is unitarily equivalent
to ∆ ⊗
d
, where ∆ is the graph Laplacian of the underlying graph G, as in lemma 2.
with weights along the vertices and edges, i.e. general Hermitian matrices, extending the graph Lapla-
cian case that was analyzed in [15]. Given a Hamiltonian with the decomposition H
=
P
i,j∈B
H
ij
|iihj|
in a particular basis, the generalized ULGs based on H will have the form
H
prop
=
X
i,j∈B
H
ij
|iihj|⊗ U
ij
.
A ULG is called simple if the product of unitaries around any loop is the identity, and otherwise
it is said to be frustrated. For a simple ULG H
prop
based on a Hamiltonian H, a generalization of
the standard argument shows that there will be a unitary transformation W such that W
†
H
prop
W
=
H ⊗ .
In order to analyze the UNSAT penalty for a large class of generalized ULGs, we first make an
observation that relates the low energy spectrum to the UNSAT penalty.
Remark 9.
Suppose
H
prop
=
P
i,j∈B
H
ij
|iihj| ⊗ U
ij
describes a generalized ULG, and
H
in
:=
P
i∈V
in
|iihi| ⊗
Π
in,i
and
H
in
:=
P
i∈V
out
|iihi| ⊗
Π
out,i
are input and output projectors. If
H
prop
has
k ≥ min {|V
in
|, |V
out
|}
+ 1 excited eigenvalues of energy at most
R
, then the UNSAT penalty satisfies
E (H
in
+ H
prop
+ H
prop
) ≤ R.
This follows because the k excited states can be used to form a superposition |φiwith zero amplitude
on k −
1
sites. This superposition will have hφ|H
prop
|φi ≤ R, and if the amplitudes are zero on all
the input (output) penalties, then hφ|(H
in
+ H
prop
+ H
prop
) |φi
=
hφ|H
prop
|φi ≤ R. In the case of
an output penalty at a single vertex in the graph (as in the standard tridiagonal case), this shows that
the spectral gap will always upper bound the UNSAT penalty.
To apply this spectral upper bound on the UNSAT penalty, we make the hypothesis that any
generalized ULG which describes computations of size T must contain a path of length at least length
T . In other words, we start from an assumption that we are given circuits of size T that are “optimally
compiled”, i.e. ones that and cannot be computed using local gates by a shorter path. For a given
Hamiltonian H, we further define the notion of diameter with respect to particular basis B, which is
defined to be the smallest power of H needed to connect any two basis elements:
diam
B
H := max
u,v∈B
min
k ∈ : hu|H
k
|vi 6= 0
.
The ground state |ψi of H defines a probability distribution π
(
x
) :=
|hx|ψi|
2
for x ∈ B. Let π
min
:=
min
x∈B
π
(
x
)
and define the spectral gap to be
∆
H
=
λ
1
− λ
min
. This allows us to derive a bound for
Hermitian matrices which relates the ground state probability distribution π and the matrix diameter
to the spectral gap, generalizing a known bound for graph Laplacians [20].
Accepted in Quantum 2018-08-03, click title to verify 8
Theorem 10. Let H, B, π and ∆
H
be as defined above. Then
∆
H
≤
kHk
2
log(2/π
min
)
diam
B
H
2
.
Since the diameter is at least T under the optimal compilation assumption, obtaining a spectral gap
that scales like T
−2+
for some >
0
requires a generalized ULG Hamiltonian with either a growing
operator norm, or the presence of exponentially small ground state amplitudes. The latter case is
typically ruled out by the fact that exponentially small amplitudes comprise points at which it is easy
to deform the computation and obtain a small UNSAT penalty.
2.3 Related Work
The notion of modifying the weights in Feynman’s circuit Hamiltonian goes back to at least 1985, when
Peres [21] considered modified weights for improving the probability of measuring the output of the
computation in the ballistic Hamiltonian model. In the context of universal adiabatic computation
Ganti and Somma [22] derived a limitation on improving the spectral gap of circuit Hamiltonians by
applying the lower bound on the Gover search problem. In [16], the authors go beyond unitary circuit
include certain projective measurements {
Π
, −
Π
} (ones whose outcome probabilities are independent
of all valid input state at that computational step).
More recently, Caha, Landau, and Nagaj have presented a compilation of several results on modified
circuit Hamiltonians [17]. Most of these results are distinct from results in this work, with the exception
of theorem 7 which was discovered by us independently around the same time [19]. Another aspect of
[17] and the present work that can be compared are that both works make an improvement to idling
the computation efficiently. Caha, Landau, and Nagaj show that the overlap with the final state of
the quantum circuit can be increased arbitrarily close to 1 in the Hamiltonian computation model by
using logarithmic overhead in space. We show a similar result for universal adiabatic computation,
with no space overhead but at the expense of requiring higher precision in the Hamiltonian couplings.
Accepted in Quantum 2018-08-03, click title to verify 9
3 Non-Uniform Circuit Histories for Improving the UNSAT Penalty
3.1 Analysis of Modified Feynman Hamiltonians
Proof of
Lemma 2
The lemma, in summary, claims that H
prop
is unitarily equivalent to copies of H
clock
; we re-state it
here for convenience.
Lemma 2.
If
W
:=
P
T
t=0
|tiht|⊗
(
U
t
···U
1
), then
W
is unitary and
W
†
H
prop
W
=
H
clock
⊗
, where
the clock Hamiltonian H
clock
is given by eq. (3).
Proof.
Since
W
is a linear operator the calculations we need to check for lemma 2 are the same as in
the standard unweighted case [1, ch. 14.4]. As a reminder,
W
†
W =
T
X
t,t
0
=0
|tiht| ⊗ (U
†
1
···U
†
t
)
|t
0
iht
0
| ⊗ (U
1
···U
t
0
)
=
T
X
t=0
|tiht| ⊗ = ,
W
†
(|t + 1iht| ⊗ U
t+1
)W = |t + 1iht| ⊗ (U
†
1
···U
†
t+1
)U
t+1
(U
t
···U
1
) = |t + 1iht| ⊗ ,
and so the claim of lemma 2 follows by linearity.
Proof of
Lemma 3
Kitaev’s geometrical lemma provides the starting point for the lower bound on the UNSAT penalty
given in eq. (5).
Lemma 11
(Kitaev’s geometrical lemma)
.
Let
A, B ≥
0 be positive semi-definite operators, both
with a zero eigenspace, and such that
ker A ∩ ker B
=
{
0
}
. Denote with
λ
6=0
(
A
)
, λ
6=0
(
B
) the minimal
non-zero eigenvalue of A and B, respectively. Then
A + B ≥ min{λ
6=0
(A), λ
6=0
(B)} × 2 sin
2
θ
2
, (9)
where θ is the angle between the kernels of A and B.
This allows us to proof the lower bound, re-stated here for convenience:
Lemma 3.
If the spectral gap of the corresponding clock Hamiltonian
H
clock
(
T
)—denoted ∆
H
(
T
)—is
less than the (constant) spectral gap of H
in
+ H
out
, then
∆
H
(T )
4
(1 −
√
) × min{π
0
, π
T
} ≤ E
p
(, T ) ≤ E (H
clock
(T ) + |0ih0| + |T ihT |) . (5)
Proof.
We use the notation from lemma 11. For us,
A
=
H
in
+
H
out
, and
B
=
H
prop
, and in this section
we use the freedom to shift the energy in eq. (2) to set
E
(
H
prop
) = 0 (since the system can be frustrated,
this means the local terms may no longer be positive semi-definite, but this will not present a problem
in applying the geometrical lemma above because
H
prop
itself is positive semi-definite). Denote the
projector onto the kernel of the penalty terms
A
with Π
pen
:=
|0ih0|⊗
Π
⊥
in
+
|T ihT |⊗
Π
⊥
out
+
P
T −1
t=2
|tiht|⊗
.
Denote with
U
=
U
T
···U
1
the entire encoded quantum circuit. We first want to bound the angle
θ
between the kernels of the propagation and penalty Hamiltonians[1, 23].
Accepted in Quantum 2018-08-03, click title to verify 10
cos
2
θ = max
|ξi∈ker A
|ηi∈ker B
|hξ|ηi|
2
= max
|ξi
|ηi∈ker B
|hη|Π
pen
|ξi|
2
∗
= max
|ηi∈ker B
hη|Π
pen
|ηi
= max
|ηi∈ker B
hη|W
†
(WΠ
pen
U
†
)W |ηi
= max
|η
0
i∈ker WBW
†
hη
0
|
|0ih0| ⊗ Π
⊥
in
+ |T ihT | ⊗ UΠ
⊥
out
U
†
+
T −1
X
t=2
|tiht| ⊗
!
|η
0
i
= max
|φi
T
X
s=1
ψ
∗
s
ψ
s
hs|hφ|
|0ih0| ⊗ Π
⊥
in
+ |T ihT | ⊗ UΠ
⊥
out
U
†
+
T −1
X
t=2
|tiht| ⊗
!
|ti|φi
= max
|φi
hφ|(|ψ
2
0
|Π
⊥
in
+ |ψ
2
T
|UΠ
⊥
out
U
†
) |φi + 1 − |ψ
2
0
| − |ψ
2
T
|,
where we have saturated Cauchy-Schwartz in the third line (
∗
). To bound the first inner product, we
observe that if ψ
2
0
≥ ψ
2
T
, picking |φi ∈ ker Π
in
gives the bound
max
|φi
hφ|(π
0
Π
⊥
in
+ π
T
UΠ
⊥
out
U
†
) |φi ≤ π
0
+ π
T
cos ϑ,
where
ϑ
is the angle between
supp
Π
in
and
supp U
Π
out
U
†
. This angle can be lower-bounded by the
acceptance probability of the circuit:
cos
2
ϑ = max
|ηi∈supp Π
in
|ξi∈supp UΠ
out
U
†
|hη|ξi|
2
≤ max
|ηi∈supp Π
in
|ξi∈supp Π
out
|hη|U |ξi|
2
≤ .
Similarly, if
ψ
2
0
< ψ
2
T
, one can show an upper bound of
π
0
cos ϑ
+
π
T
. We thus obtain an overall upper
bound
cos
2
θ ≤ max{π
0
, π
T
} + min{π
0
, π
T
}
√
+ 1 − π
0
− π
T
≤ 1 − min{π
0
, π
T
}(1 −
√
).
In Kitaev’s lemma, we thus obtain a lower bound
2 sin
2
θ
2
≥ 2 ×
1 − cos
2
θ
8 cos
2
θ
≥
1
4
min{π
0
, π
T
}(1 −
√
),
and the claim follows.
3.2 Metropolis Hamiltonians with Target Ground State Distributions
Proof of
Lemma 4
We assume the reader has some familiarity with Markov chain transition matrices; an introduction
can e.g. be found in [24]. We re-state the lemma as follows:
Accepted in Quantum 2018-08-03, click title to verify 11
Lemma 4.
For any probability distribution
µ
with support everywhere on its domain
{
0
, . . . , T }
, there
is a choice of coefficients
{a
t
, b
t
}
T
t=0
in eq. (3) such that
H
clock
is stoquastic and frustration-free and
has a ground space spanned by states of the form eq. (1) with weights ψ
t
=
√
µ
t
.
Proof. Given a probability distribution π with support everywhere on its domain S = {0, . . . , T }, let
P be the Markov chain with Metropolis transition probabilities defined on S,
P
t,t+1
=
1
4
min
1,
π
t+1
π
t
, P
t,t−1
=
1
4
min
1,
π
t−1
π
t
P
t,t
= 1 − P
t,t+1
− P
t,t−1
(10)
for all
i ∈ S
(setting the expressions
P
0,−1
and
P
T,T +1
to zero) and
P
t,t
0
= 0 for all
t, t
0
∈ S
with
|t − t
0
| >
1. The choice of coefficient 1
/
4 implies
P
t,t
≥
1
/
2 for all
t
and so
P
is positive semi-definite.
The principal left eigenvector of this transition matrix
P
:=
P
t,t
0
∈S
P
t,t
0
|tiht
0
|
is
hπ|
=
P
t
π
t
ht|
, and
while
P
is not a symmetric matrix, there is a well known similarity transformation that relates
P
to a
symmetric matrix, given by
A :=
X
t,t
0
∈S
π
1/2
t
π
−1/2
t
0
P
t,t
0
|tiht
0
|.
The two matrices are related by the fact that if
hv
0
|, ··· , hv
T
|
are the left eigenvectors of
P
with
eigenvalues
λ
0
= 1
≥ λ
1
≥, . . . , ≥ λ
T
≥
0, then
|w
i
i
:=
P
t∈S
hv
i
|tiht|v
0
i
−1/2
|ti
satisfies
A |w
i
i
=
λ
i
|w
i
i
. Therefore
A
has the same eigenvalues as
P
, and in particular it has largest eigenvalue 1
corresponding to the eigenvector
|w
0
i
with components satisfying
ht|w
0
i
=
ht|v
0
i
1/2
=
√
π
t
. Therefore
H
=
−A
is a nonnegative Hermitian matrix with ground state that has energy zero and components
√
π
t
in the time register basis, as claimed.
Markov chain spectral gaps. Substantial effort has been devoted to characterizing spectral gaps
of Markov chains. A particularly fruitful characterization proceeds by defining a quantity called the
conductance,
Φ := min
S⊆Ω
Q(S, S
c
)
min{π(S), π(S
c
)}
, Q(S, S
c
) :=
X
x∈S,y∈S
c
π(x)P (x, y)
which determines the spectral gap within a quadratic factor,
Φ
2
2
≤ ∆
P
≤ 2Φ. (11)
The lower bound in eq. (11) is known as Cheeger’s inequality, and it was initially discovered in the
analysis of manifolds [25] before being adapted to the setting of Markov chains [26]. In the next section
we will use this method to lower bound the spectral gap of the Metropolis Hamiltonian corresponding
to a particular non-uniform stationary distribution.
3.3 Explicit Construction of an Ω(T
−2
) UNSAT Penalty Circuit Hamiltonian
Proof of
Theorem 5
Using techniques developed in lemma 4, we can proof the first of our main theorems, which we re-state.
Theorem 5.
There is a frustration-free modified circuit Hamiltonian as in eq. (2) with an UNSAT
penalty E
p
(, T ) that is Ω((1 −
√
)T
−2
).
Accepted in Quantum 2018-08-03, click title to verify 12
Proof.
Let
H
prop
be the Metropolis Hamiltonian from section 3.2 corresponding to the probability
distribution
π
0
= π
T
=
1
4
and π
t
=
1
2(T − 1)
for t = 1, . . . , T −1.
A few low energy eigenstates of
H
prop
are illustrated in fig. 2. Keeping with tradition [4, 6, 27], we
exhibit H
prop
as a T + 1 by T + 1 matrix in the clock register basis,
H
prop
=
1
2
0
.
.
.
0
−
1
√
2T − 2
1
T − 1
0
−
1
2
1
−
1
√
2T − 2
···
.
.
.
.
.
.
1
−
1
2
0
0
.
.
.
.
.
.
.
.
.
0
0
−
1
2
1
.
.
.
.
.
.
···
−
1
√
2T − 2
1
−
1
2
0
1
T − 1
−
1
√
2T − 2
0
.
.
.
0
. (12)
Since
π
0
and
π
T
are Ω(1) it only remains to be checked that the spectral gap ∆
H
prop
of the clock
Hamiltonian is Ω(
T
−2
). The spectral gap between the lowest two eigenvalues of
H
prop
is equal to the
spectral gap between 1 and the second largest eigenvalue of the Metropolis transition matrix
P
, so we
can apply Cheeger’s inequality eq. (11) to π and P.
The goal is to show that every subset
S
of
{
0
, . . . , T }
has large conductance, so we divide the proof
into cases corresponding to the different possibilities for the subset
S
. First if
S
=
{
0
}
then since
P
0,1
= (8
T −
8)
−1
so Φ(
S
) is Ω(
T
−1
), with similar statements holding for
S
=
{T }
and
S
=
{
0
, T }
.
Now if
S ⊆ {
1
, . . . , T −
1
}
is non-empty there must be at least one
t ∈ {
1
, . . . , T −
1
}
such that there
is a
t ∈ S
c
with
P
t,t
0
≥
1
/
4, and since
π
t
= (2
T −
2)
−1
, this shows that Φ(
S
) is Ω(
T
−1
) in this case as
well.
Therefore ∆
P
is Ω(
T
−2
) by eq. (11), and so ∆
H
prop
= Ω(
T
−2
) as well. Using lemma 3 this concludes
the proof.
4 Universal Adiabatic Computation
The circuit-to-Hamiltonian construction used in the proof of QMA-completeness also plays a crucial
role in the proof that adiabatic quantum computation (AQC) can simulate the quantum circuit model
with polynomial overhead. In this section we will review the relevant aspects of the standard universal
AQC construction in order to explain how our results on modified Feynman Hamiltonians allow for a
useful practical improvement in universal AQC. Furthermore, we show that theorem 8 yields a lower
bound on the time needed for universal AQC using modified Feynman Hamiltonians to simulate the
circuit model. The standard version of universal AQC is based on H
prop
as given in eq. (7), together
Accepted in Quantum 2018-08-03, click title to verify 13
0 5 10 15 20
−0.5
0
0.5
computation step t
weight of |λi = a
t
|ti
a)
0 5 10 15 20
computation step t
b)
|ψ
0
i |ψ
1
i |ψ
2
i |ψ
3
i
Figure 2: Low energy eigenstates of
(a)
the standard circuit-to-Hamiltonian construction and
(b)
the Metropolis
Hamiltonian corresponding to the distribution with π
0
, π
T
= 1/4 that is used in this section.
with
H
init
:= |0ih0| ⊗ =
0 0 ··· 0
0 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1 0
0 ··· 0 1
⊗ .
The goal in universal AQC is to prepare the ground state of H
prop
by continuously varying a Hamil-
tonian H
(
s
)
that depends on an adiabatic parameter
0
≤ s ≤
1
. First, when s
= 0
, the system is
initialized in the ground state of H
(0) :=
H
init
, which is a fiducial state that can be prepared easily.
Then the parameter s is slowly increased until it reaches s
= 1
, at which point the system Hamiltonian
is H
(1) :=
H
prop
. Defining k
˙
Hk
=
max
s
k
d
H/
d
sk and
∆ =
min
s
∆
H
(
s
)
, an often used condition for
preparing the ground state of H
prop
is for the total evolution time to satisfy t
adiabatic
= Θ(
k
˙
Hk
∆
−2
)
(see [28] for a review of rigorous adiabatic theorems).
This time scale was shown [4] to be bounded by poly(n) for the linear interpolation schedule, i.e.
H(s) = (1 − s)H
init
+ sH
prop
, (13)
where specifically
∆ = Ω(
T
−2
)
and k
˙
Hk
=
O
(1)
so that t
adiabatic
= Θ(
T
4
)
. The lower bound on the
spectral gap was proven using a quantum-to-classical mapping, a monotonicity property of the ground
state wave function as a function of s, and Cheeger’s inequality.
One may notice that measuring the time register of the uniform history state in eq. (8) results
in collapsing the computational register to its final time step t
=
T with probability O
(
T
−1
)
. To
avoid repeating the adiabatic evolution many times, it is desirable to boost this probability to
Ω(1)
.
The standard trick for doing this is to pad the end of the computation with identity gates, meaning
after performing the desired computational gates U
1
, . . . , U
T
one adds r additional identity gates
U
r
=
U
r+1
=
. . .
=
U
r+T
=
, so that measuring t ∈
[
T, r
+
T
]
suffices to project the computational
register to be in the end of the computation.
We want to point out that modified Feynman Hamiltonians, together with the Metropolis Hamil-
tonian construction of section 3.2, open up a new set of trade-offs in universal adiabatic computation
Accepted in Quantum 2018-08-03, click title to verify 14
Standard
Modified
0.0 0.2 0.4 0.6 0.8 1.0
0.0
0.2
0.4
0.6
0.8
1.0
s
Δ(s)
Figure 3: Comparison of the spectral gap as a function of the adiabatic parameter
s
for the standard version of
universal AQC with a 1
/T
probability of measuring the history state to be in the final time step of the computation
and for the modified construction corresponding to a history state with probability 1
/
4 of measuring the final time
step of the computation. Here
T
= 100 for both constructions, and they both follow the same adiabatic schedule
with local terms of the same norm.
that may be relevant for practical implementations. Specifically, let H
∗
prop
be the Hamiltonian used
in section 3.3. The
Ω(1)
probability on the endpoints can be used to increase the probability that
measuring the time register will collapse the computational register of the system into the final time
step of the computation. This provides an alternative to the “padding the end of the computation
with identity gates” technique that is normally used to raise the probability of sampling from the final
time step of the computation. Padding the length of the computation with identity gates is relatively
expensive in practical terms when the time register is encoded using local interactions (such as the
domain wall clock) because the clock must be represented in unary, meaning the number of clock
qubits scales linearly with the total length of the (padded) computation.
Achieving an overlap of δ ≈
1
with the final step of the computation by padding the system with
identity gates requires a total of O
(
T/
(1
− δ
))
clock qubits, however one can instead prepare the
weighted history state with π
T
=
δ using only T clock qubits. The price that one has to pay for this
improvement is in an increase in the precision of the couplings needed to implement eq. (2) now must
scale like O
(
T
−1
)
, as seen in eq. (12). This is a reasonable trade off, however, since the total number
of qubits is generally the limiting factor in most experiments.
Proof of
Theorem 6
Having seen that it can be advantageous to prepare the non-uniform history state ground state of
H
∗
prop
, it remains to be shown that this can be done efficiently, which is what the second of our
theorems claims:
Theorem 6.
For any probability
p >
0 there is a frustration-free modified circuit Hamiltonian as
in eq. (2) with
π
T
=
p
such that the minimum spectral gap of the linear interpolation
(6)
satisfies
∆
min
= Ω(T
−2
).
Proof.
In section 3.3 we proved that ∆
H
∗
prop
= Θ(
T
−2
), just as the minimum gap for the standard
construction is ∆
H(s=1)
= Θ(
T
−2
). A numerical comparison of the spectral gaps of
H
(
s
) in eq. (13) and
Accepted in Quantum 2018-08-03, click title to verify 15
of (1
−s
)
H
init
+
sH
∗
prop
(
s
) can be found in fig. 3, which reveals that both of these linear interpolations
encounter their asymptotic minimum gap at s = 1.
However, it is of course desirable to bound the adiabatic run time for
H
∗
(
s
) without any recourse
to numerics. In this case the monotonicity of the ground state wave function used in the proof for
the standard construction does not hold, and so we offer a different proof based on a modified linear
interpolation schedule,
H
∗
(s) = H
0
+ sAH
∗
prop
. (14)
Choosing
A
=
T
4
and an Ω(1) spectral gap for 0
≤ s ≤
1, the standard estimate of the adiabatic run
time Ω(
k
˙
Hk
∆
−2
H
) is then Ω(
T
4
)—just as it will be for the usual version of universal AQC. At
s
= 1,
the system will be in the ground state of the Hamiltonian
˜
H
final
=
H
∗
prop
+
A
−1
H
0
. To bound the
distance from this state to the target ground state of
H
∗
prop
we apply the following general result from
Weyl perturbation theory.
Proposition 12.
Let
H
=
H
0
+
λV
be a perturbed system, with
V
0 and the unperturbed Hamiltonian
H
0
having a spectral gap ∆
0
between its ground space and the rest of the spectrum. For any ground
state |ψi of H there is a ground state |ψ
0
i of H
0
with fidelity
|hψ|ψ
0
i|
2
≥ 1 −
2λkVk
∆
0
.
In order to show the proposition, we start with Weyl’s inequality. The ground state and first excited
energies of the perturbed system satisfy
E
0
≥ E
0
0
− λkVk, , E
1
≥ E
1
0
− λkVk.
Meanwhile, any original ground state
|ψ
0
0
i
has
hψ
0
0
|H|ψ
0
0
i ≤ E
0
0
+
λkVk
. We can express
|ψ
0
0
i
as a
combination of a ground state |ψi of H and an orthogonal state |ψ
⊥
i,
|ψ
0
0
i =
√
1 − |ψi +
√
|ψ
⊥
i.
The energy of this state satisfies hψ
0
0
|H|ψ
0
0
i ≤ E
0
0
+ λkVk, and so
E
0
0
+ λkVk ≥ hψ
0
0
|H|ψ
0
0
i
≥ (1 − )E
0
+ E
1
≥ (1 − )(E
0
0
− λkVk) + (E
1
0
− λkVk)
= (E
0
0
− λkVk) + (E
0
0
− E
1
0
).
Rearranging yields
≤
2λkVk
E
0
0
− E
1
1
.
Since A = T
4
we have
˜
ψ
ψ
∗
0
2
= 1 − O(T
−2
), as claimed.
To see that
H
∗
(
s
) in eq. (14) has ∆
H
∗
(s)
= Ω(1) for all
s
, first note that ∆
H
∗
(0)
= 1. We want to show
that the first excited energy is non-decreasing as a function of
s
. In order to achieve this, we let
L
be a
large integer and discretize the adiabatic path into steps
s
0
= 0
, s
1
, . . . , s
L
= 1, with a uniform step size
s
i+1
=
s
i
+
L
−1
. Since
H
∗
(
s
i+1
) =
H
∗
(
s
i
)+
(H
∗
(s
i+1
) − H
∗
(s
i
))
and since
H
∗
(
s
i+1
)
−H
∗
(
s
i
) =
H
∗
prop
is positive semi-definite, we can apply Weyl’s inequality to see that the first excited state energy
is indeed non-decreasing with
s
; because this holds for any
L
this statement is independent of the
discretisation of the path: we conclude that
E
∗
1
(
s
)
≥
1. Next we apply the variational method with a
trial state
|φi
equal to the ground state of
H
∗
prop
, to see that
hφ|H
∗
(
s
)
|φi
=
hφ|H
0
|φi
= 3
/
4, and so
∆
H
∗
(s)
≥ 1/4 for all s.
Accepted in Quantum 2018-08-03, click title to verify 16
5 Tightness of the Geometrical Lemma for the UNSAT Penalty
5.1 A Tight Bound for the Clock Hamiltonian
In this section we prove that the UNSAT penalty of Kitaev’s original construction is actually
Ω(
T
−2
)
,
rather than the
Ω(
T
−3
)
which can be shown using the geometrical lemma. As noted in the introduction,
this result was proven independently by Caha, Landau, and Nagaj [17], and appears to have been known
for a while [14]. We present a variant not reliant on Jordan’s lemma in appendix A.2.
The Hamiltonian in Kitaev’s original proof is H
Kitaev
:=
H
prop
+
|0ih0|⊗
Π
in
+
|T ihT |⊗
Π
out
, where
H
prop
is given by eq. (16) with a
0
=
a
T
= 1
and a
t
= 2
else, and b
t
=
−
1
for all t. We denote the
encoded circuit with U
=
U
T
···U
1
. The corresponding clock- and computation registers then live on
the Hilbert space H := (
T +1
) ⊗ (
2
)
⊗d
for some local dimension d.
As a first step, and to establish some background machinery, we focus on only the clock part of
the Hamiltonian, i.e. we disregard the encoded computation completely; the Hamiltonian we analyse
has the form H
=
|0ih0|
+
H
clock
+
|T ihT |. Since H is stoquastic, we can lower bound the ground state
energy of H by combining a suitable ansatz for the ground state with the following lemma.
Lemma 13
(Farhi et al., [29])
.
Let
H
be a Hermitian operator which is stoquastic in the
|ti
basis
(meaning ht|H |t
0
i ≤ 0 for all t 6= t
0
). Let E be its lowest eigenvalue. Then
E ≥ min
t
ht|H |φi
ht|φi
(15)
for any state |φi such that ht|φi > 0 for all t.
Noting that the state |φi in Lemma lemma 13 does not need to be normalized, define
|φi :=
T
X
t=0
sin
π(t + 1)
T + 2
|ti.
The bound eq. (15) can be evaluated using three cases. The first case is t = 0, which yields
h0|H |φi
h0|φi
=
sin
π
T + 2
−1
2 sin
π
T + 2
− sin
2π
T + 2
= 2
1 − cos
π
T + 2
=
π
2
T
2
− O(T
−3
).
The next case is 1 ≤ t ≤ T − 1,
ht|H |φi
ht|φi
=
sin
π(t + 1)
T + 2
−1
2 sin
π(t + 1)
T + 2
− sin
πt
T + 2
− sin
π(t + 2)
T + 2
= 2
1 − cos
π
T + 2
=
π
2
T
2
− O(T
−3
).
Accepted in Quantum 2018-08-03, click title to verify 17
The final case is t = T ,
hT |H |φi
hT |φi
=
sin
π(T + 1)
T + 2
−1
2 sin
π(T + 1)
T + 2
− sin
πT
T + 2
= 2 − sin
πT
T + 2
csc
π(T + 1)
T + 2
=
π
2
T
2
− O(T
−3
)
We have thus shown that ht|H |φi/ ht|φi is
Ω(
T
−2
)
for all t, and so applying lemma 13 we can conclude
that E(H) is Ω(T
−2
).
5.2 A Tight Bound for the Full Circuit Hamiltonian
5.2.1 Block-Decomposition of the Full Circuit Hamiltonian
For the purpose of this discussion, we will assume that rank
Π
in
, rank
Π
out
≥ d/
2
; this is a natural
assumption e.g. if
Π
in
=
|1ih1|
(1)
⊗
(2)
⊗ ··· ⊗
(d)
just penalizes the first qubit in a state |1i. Note
that more penalized qubits generally increase the rank of
Π
in
if we demand the penalties to be local
operators (i.e. not something like |1ih1| ⊗ |0ih0| ⊗ ···, but |1ih1| ⊗
+
⊗ |0ih0| ⊗
+
. . .), so this
assumption is justified.
We know that there exists a global unitary W on H such that spec
(
H
prop
) =
spec
(
W
†
H
prop
W
) =
spec(∆) up to multiplicities, where ∆ is the Laplacian of a path graph of T + 1 vertices:
∆ =
1 −1 0 ··· 0
−1 2 −1
.
.
.
0 −1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
−1 0
−1 2 −1
0 ··· 0 −1 1
Then
W
†
H
Kitaev
W = ∆ ⊗ + |0ih0| ⊗ Π
in
| {z }
:=A
+ |T ihT | ⊗ U
†
Π
out
U
| {z }
:=B
. (16)
We choose to work in a basis where A takes the form
A = diag( ∆
0
, . . . , ∆
0
| {z }
rank Π
in
times
, ∆, . . . , ∆), (17)
and where
∆
0
= ∆ +
|0ih0|. Note that this is always possible: we simply re-order the computational
register such that
Π
in
penalizes the first rank
Π
in
states. Also note that B
=
|T ihT | ⊗ U
†
Π
out
U does
not have a simple form in this basis (apart from having only a single entry within each block in the
time register basis, i.e. at the diagonal entry |T ihT |).
If we na¨ıvely try to diagonalize B, we will again mix up the nice block-diagonal form in eq. (17); our
goal is thus to find a unitary V
=
d
⊗
(
V
0
⊕V
00
)
which respects the block-diagonal structure of A, i.e. in
particular leaves the upper left block invariant (which is automatically the case if dim V
0
≤ rank
Π
in
).
While Jordan’s original paper addresses the case of orthogonal transformations between subspaces,
we can phrase it more suitable to our needs:
Accepted in Quantum 2018-08-03, click title to verify 18
Lemma 14
(Jordan [30], Th. 1)
.
Let Π
0
and Π
1
be two Hermitian projectors in some Hilbert space
H
.
Then there exists a decomposition of
H
into one- and two-dimensional subspaces
H
=
L
i
H
i
, such that
H
i
is invariant under both Π
0
and Π
1
, and such that rank Π
j
|
H
i
≤ 1 for all j and i.
The proof is standard. Lemma 14 allows us to state the following corollary.
Corollary 15.
Let Π
0
and Π
1
be projectors with
rank
Π
0
=
rank
Π
1
=
d/
2, and
rank
(Π
0
+ Π
1
) =
d
is
full rank. Then there exists a unitary V such that V
†
Π
0
Vr =
d/2
⊕ 0. Furthermore,
V
†
Π
1
V =
M
aa
M
ab
M
ba
M
bb
!
,
where each d/2 × d/2 block M
ij
is diagonal and full rank, and M
ab
= M
ba
< 0.
Proof.
Applying lemma 14 to Π
0
and Π
1
, we know that there exists a basis in which Π
0
is diagonal,
and Π
1
=
L
i
M
i
, where the
M
i
are 2
×
2 or 1
×
1 Hermitian matrices. Re-order the basis again such
that Π
0
=
r
⊕
0 with
r
=
d/
2; we denote the unitary transformation from Jordan’s lemma with this
reordering as V.
Under the same re-ordering, the matrix V
†
Π
1
V then necessarily has the form
V
†
Π
1
V =
M
aa
M
ab
M
ba
M
bb
!
=
λ
1
0 ··· 0 ξ
1
0 ··· 0
0 λ
2
.
.
.
.
.
. 0 ξ
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
.
.
.
.
.
.
.
.
.
0
0 ··· 0 λ
r
0 ··· 0 ξ
r
ξ
∗
1
0 ··· 0 µ
1
0 ··· 0
0 ξ
∗
2
.
.
.
.
.
. 0 µ
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
.
.
.
.
.
.
.
.
.
0
0 ··· 0 ξ
∗
r
0 ··· 0 µ
r
(18)
A further global phase transformation (adjoining with a diagonal unitary, which leaves Π
0
invariant)
allows us to assume that the ξ
i
= −|ξ
i
|, and the claim follows.
We still need to show that the resulting Hamiltonian is in particular a graph Laplacian connecting
the T
th
entry in every block of
∆
in eq. (17) with the T
th
entry in at least one block of
∆
0
, which is
where the input penalty terms are located. Naturally, this will depend on the encoded circuit, and—
using notation from the last proof—on the respective ranks of M
aa
and M
bb
. For this, we state the
following lemma.
Lemma 16. Let U encode a NO instance. Then Π
in
+ U
†
Π
out
U has full rank.
Proof.
It is easy to see that if
ker
(Π
in
+
U
†
Π
out
U
)
6
= 0, there would be a state that can be accepted
with perfect probability—contradicting the assumption that U encodes a NO instance.
This technical machinery allows us to prove theorem 7 in the next section.
5.2.2 An Ω(T
−2
) Promise Gap for Kitaev’s Hamiltonian
Remember that we have to show that whenever the encoded circuit U encodes a
NO
instance, then
λ
min
(H
Kitaev
) = Ω(T
−2
).
Accepted in Quantum 2018-08-03, click title to verify 19
∆
∆
∆
∆
∆
∆
∆
∆
1
λ
1
µ
1
−|ξ
1
|
−|ξ
1
|
1
λ
2
µ
2
−|ξ
2
|
−|ξ
2
|
1
λ
3
µ
3
−|ξ
3
|
−|ξ
3
|
1
λ
4
µ
4
−|ξ
4
|
−|ξ
4
|
T
d blocks
rank Π
in
blocks
Figure 4: Sketch of matrix ( ⊗ V)
†
(∆ ⊗ + |1ih1| ⊗ Π
in
+ |T ihT | ⊗ M)( ⊗ V).
Proof of
Theorem 7
We remind the reader of the precise claim:
Theorem 7. The UNSAT penalty in Kitaev’s local Hamiltonian construction is Ω(T
−2
).
Proof.
Since the circuit is a NO-instance, there exists a minimal acceptance probability for any (valid)
input
|xi ∈ ker
Π
in
, which we denote with
. By lemma 16, we know that we can apply corollary 15 to
Π
in
and
U
†
Π
out
U
; the unitary transformation bringing the latter into a form eq. (18) while leaving
Π
in
= ⊕ 0 we will denote with V.
Now perform this similarity transform on eq. (16), i.e.
( ⊗V
†
)W
†
H
Kitaev
W( ⊗V) = ∆ ⊗ 1 + |0ih0| ⊗ ( ⊕0) + |T ihT | ⊗ (V
†
U
†
Π
out
UV).
The resulting matrix is depicted in fig. 4. Since
U
encodes a quantum circuit, we can immediately
calculate the magnitudes of the λ
i
, µ
i
and ξ
i
’s (see eq. (18) and fig. 4 as a reference).
1.
If
|xi ∈
d
, then
hx|U
†
Π
out
U |xi
=
k
Π
out
U |xik
2
is the probability that the circuit
U
rejects
input |xi.
2.
If
|xi ∈ ker
Π
in
—i.e. for the
M
bb
block—
hx|U
†
Π
out
U |xi ≥
1
−
. Otherwise we have no
non-trivial lower bound.
Accepted in Quantum 2018-08-03, click title to verify 20
3.
Assuming
dim supp
Π
out
=
d/
2 (discard the rest), we can thus immediately conclude that each
matrix block
P
i
=
λ
i
−|ξ
i
|
−|ξ
i
| µ
i
!
is of rank P
i
= 1 with 1 ≥ µ
i
≥ 1 − .
4.
Since the set of eigenvalues of a matrix is unique, we could continue diagonalizing
V
†
Π
out
V
by
further diagonalizing each block
P
i
separately; the result would be the same overall matrix as if
we had diagonalized Π
out
in one step. Since Π
out
is a psd projector, we thus know that each of
the P
i
has to be a psd projector, and we can conclude
P
i
=
η
2
i
µ
i
−η
i
µ
i
−η
i
µ
i
µ
i
!
for some η
i
:= λ
i
/µ
i
≥ 0. Then 1 = tr P
i
= µ
i
(1 + η
2
i
) ≥ (1 − )(1 + η
2
i
), and thus
η
i
≤
r
1
1 −
− 1 =
r
1 −
≤
r
2
,
and therefore λ
i
= η
2
i
µ
i
≤ µ
i
/2 ≤ /2, and |ξ
i
| = η
i
µ
i
≤
p
/2.
5. From µ
i
≤ 1, one can obtain a trivial bound 1 ≤ 1 + η
2
i
, and thus obviously λ
i
≥ 0.
What remains to be analyzed is the spectrum of each of the pairs of blocks in fig. 4, i.e. blocks of the
form ∆ + ∆
0
+ matrix
P
i
spread to the submatrix indexed by
T,
2
T
; more precisely, each block will
have twice the size of ∆, and we can write it as a stoquastic matrix on
2
⊗
T +1
:
S = (|0ih0| + |1ih1|) ⊗ ∆ + |0ih0| ⊗ |0ih0| + µ
|1ih1| + η
2
|0ih0| − η(|0ih1| + |1ih0|)
| {z }
=:L
⊗|T ihT |, (19)
where
µ ≥
1
−
and
η ≤
p
/2
. For e.g.
dim S
= 8 and reversing the second half of the time register
(i.e. reversing the basis from T to 2T ), this matrix looks like
S
8
=
2 −1 0 0 0 0 0 0
−1 2 −1 0 0 0 0 0
0 −1 2 −1 0 0 0 0
0 0 −1 µη
2
+ 1 −µη 0 0 0
0 0 0 −µη 1 + µ −1 0 0
0 0 0 0 −1 2 −1 0
0 0 0 0 0 −1 2 −1
0 0 0 0 0 0 −1 1
.
Using a variational argument with the state
|φi :=
T
X
i=1
sin
πi
2T
(|ii + |i + T i)
and lemma 13, we can explicitly show that
S
= Ω(
T
−2
), independent of
µ
and
η
. The bound can be
evaluated using five cases, which we summarize below.
Accepted in Quantum 2018-08-03, click title to verify 21
t = 1:
2 sin
π
2T
− sin
π
T
csc
π
2T
=
π
2
4T
2
+ O(T
−3
)
1 < t ≤ T − 1 and T + 1 < t < T :
4 sin
2
π
4T
=
π
2
4T
2
+ O(T
−3
)
t = T :
η
2
µ − ηµ sin
π
2T
− cos
π
2T
+ 1 = η
2
µ −
πηµ
2T
+
π
2
8T
2
+ O(T
−3
)
t = T + 1:
µ − ηµ csc
π
2T
− 2 cos
π
2T
+ 1 = −
2T (ηµ)
π
+ (µ − 1) −
πηµ
12T
+
π
2
4T
2
+ O(T
−3
)
t = 2T :
1 − sin
π(T − 1)
2T
=
π
2
8T
2
+ O(T
−3
)
The claim of theorem 7 follows.
For convenience, we further collect the findings regarding the block matrix decomposition of the
full circuit Hamiltonian given in the proof of theorem 7 in the following lemma.
Lemma 17.
Kitaev’s construction can be block-decomposed as
H
Kitaev
=
L
S
i
, where each block
S
i
has the form given in eq. (19). The ground state energy of each of these blocks is Ω(
T
−2
), and thus
E
p
(H
Kitaev
) = Ω(T
−2
).
6 Limitations on Further Improvement
6.1 Linear Clock Registers with Endpoint Penalties
The proof of theorem 8 is based on applying a sharp spectral gap bound for birth-and-death Markov
chains to a quantum-to-classical mapping that has been studied previously in the closely related context
of universal adiabatic computation [4] and the complexity of stoquastic Hamiltonians [31, 32]. A
new feature of our application is the realization that this quantum-to-classical mapping defines a
Markov chain even for tridiagonal Hamiltonian matrices with arbitrary complex entries, while previous
applications have been restricted to cases for which H has all non-positive off-diagonal matrix entries
in the time register basis.
Proof of
Theorem 8
In this section we continue with the notation of eq. (2), but now we use the freedom to shift the
overall energy to set a
t
≥
0
for all t, such that the ground state energy E satisfies
0
≤ E <
1
; this
allows us to show optimality for tri-diagonal clock constructions, re-stated in the following theorem.
Accepted in Quantum 2018-08-03, click title to verify 22
Theorem 8.
Let
|ψi
be the ground state of a Hamiltonian
H
with eigenvalues
E
0
≤ E
1
≤ . . . ≤ E
T
.
If H is tridiagonal in the basis {|0i, . . . , |T i},
H :=
T
X
t=0
a
t
|tiht| +
T −1
X
t=0
(b
t
|t + 1iht| + b
∗
t
|tiht + 1|) ,
with
|a
t
|, |b
t
| ≤
1 for
t
= 0
, . . . , T
, then the product ∆
H
· min{|ψ|
2
0
, |ψ
T
|
2
}
of the spectral gap ∆
H
=
E
1
− E
0
and the minimum endpoint overlap is O(T
−2
).
Proof.
Define
G
:= (
− H
)
/
(1
− E
) to be a shifted and rescaled version of
H
which is designed to
satisfy G |ψi = |ψi, where |ψi labels the ground state of H. For all t, t
0
∈ {0, . . . , T }, define
P
t,t
0
:=
(
ψ
t
0
G
t,t
0
ψ
−1
t
if ψ
t
6= 0 and ψ
t
0
6= 0,
0 otherwise.
In the following lemma we will show that the
P
t,t
0
are transition probabilities for an irreducible
Markov chain on
{
0
, . . . , T }
, i.e. in particular that they are all nonnegative. First, observe that if
H
is
stoquastic as in previous applications, then
G
is a nonnegative matrix in the time register basis,
ψ
has nonnegative amplitudes in this basis by the Perron-Frobenius theorem, and so
P
t,t
0
is explicitly
nonnegative. Here we show that even when
G
contains arbitrary complex matrix entries (while being
tridiagonal) we still have
P
t,t
0
≥
0, because of cancellations that occur between the matrix elements of
G
and the amplitudes of the ground state wave function in the time register basis. Continuing with
the same notation used in eq. (3), we state the following lemma.
Lemma 18.
If
ψ
0
6
= 0,
ψ
T
6
= 0, and
b
t
6
= 0 for
t
= 0
, . . . , T
, then
ψ
t
6
= 0 for
t
= 1
, . . . , T −
1 and
P
t,t+1
= ψ
t+1
G
t,t+1
ψ
−1
t
≥ 0 for all t ∈ {0, . . . , T − 1}.
Before proving the lemma, note that the conditions may be taken to hold without loss of generality,
since
ψ
0
= 0 or
ψ
T
= 0 immediately implies theorem 8l. Similarly, if
b
t
0
= 0 for some
t
0
, then
ψ
⊥
:=
P
T
t=0
ψ
⊥
t
|ti defined by
ψ
⊥
t
:=
ψ
t
ψ
2
([0, t
0
])
0 ≤ t ≤ t
0
−
ψ
t
ψ
2
([t
0
+ 1, T ])
t
0
< t ≤ T − 1
(20)
satisfies
ψ
⊥
ψ
= 0 and
H
ψ
⊥
=
E
ψ
⊥
, which implies ∆
H
= 0—so again theorem 8 holds in this
case—note that the same idea behind eq. (20) can be used to upper bound the spectral gap by the
minimum of π
t
π
t+1
over all t ∈ {0, . . . , T − 1}, such that ψ
2
([0, t
0
]) and ψ
2
([t
0
+ 1, T ]) are both Ω(1).
Now turning to the proof of lemma 18. From H |ψi = E |ψi we have that
a
0
ψ
0
+ b
0
ψ
1
= Eψ
0
, (21)
b
∗
i−1
ψ
i−1
+ a
i
ψ
i
+ b
i
ψ
i+1
= Eψ
i
for i = 1, . . . , T − 1, and (22)
a
T
ψ
T
+ b
∗
T −1
ψ
T −1
= Eψ
T
. (23)
Since
P
t,t
0
= 0 when
|t − t
0
| >
1, our goal is to show
P
t,t+1
>
0 for
t ∈ {
0
, . . . , T −
1
}
, and
P
t,t−1
>
0
for
t ∈ {
1
, . . . , T }
. The first claim
P
t,t+1
>
0 will follow by showing that
E
is minimized when
ψ
t
6
= 0
and
ψ
t+1
b
t
ψ
−1
t
<
0 for all
t
= 0
, . . . , T −
1. The second claim
P
t−1,t
>
0 is then implied immediately,
since
ψ
t
b
∗
t
ψ
−1
t+1
=
|ψ
t
|
|ψ
t+1
|
2
ψ
∗
t+1
ψ
∗
t
b
∗
t
=
|ψ
t
|
|ψ
t+1
|
2
ψ
t+1
b
t
ψ
−1
t
∗
.
Accepted in Quantum 2018-08-03, click title to verify 23
Rearranging eq. (21) yields
ψ
1
b
0
ψ
−1
0
=
E −a
0
, and since
E −a
0
is real the value of
E
implied by this
equation alone is minimized when the LHS is negative. This observation will be taken as the base case
for an inductive argument over the finite set {1, . . . , T −1}.
The inductive hypothesis is that the value of E implied by considering only equations 0 through t in
the list eq. (22) is minimized when
ψ
t
b
t−1
ψ
−1
t−1
is negative for 1
, . . . , t
, and this will be used to show
that the minimum value of
E
that satisfies equations 0 through
t
+ 1 in eq. (22) will be achieved
when
ψ
t+1
b
t
ψ
−1
t
is negative as well. Using the fact that
ψ
t
6
= 0 from the inductive hypothesis, we may
express eq. (22) as
b
∗
t−1
ψ
t−1
ψ
t
+ b
t
ψ
t+1
ψ
i
= E − a
t
for t = 1, . . . , t.
Since
E − a
t
is real and
ψ
t−1
b
∗
t−1
ψ
−1
t
= (
|ψ
t−1
|/|ψ
t
|
)
2
(
ψ
t
b
t−1
ψ
−1
t−1
)
∗
is negative by the inductive
hypothesis, the value of
E
implied by equations 0 through
t
+ 1 in the list eq. (22) will indeed be
minimized by taking
ψ
t+1
b
t
ψ
−1
t
to be negative. This establishes the inductive claim; a simple argument
shows the same for eq. (23), which completes the proof of lemma 18.
Having established that
P
t,t
0
≥
0 we now list several standard facts which have been previously applied
to P when G is nonnegative, which can also be seen in the present case by direct computation:
1. P
is a stochastic matrix, i.e.
P
T
t
0
=0
P
t,t
0
= 1 for all
t ∈ {
0
, . . . , T }
, and therefore it can be
regarded as the transition matrix of a discrete time Markov chain.
2.
The largest eigenvalue of
P
is equal to 1 and it corresponds to the unique principal eigenvector
|πi
=
P
T
t=0
|ψ
t
|
2
|ti
. The probability distribution
π
t
:=
ht|πi
is the stationary distribution of the
corresponding Markov chain.
3. The Markov chain defined by P is reversible with respect to its stationary distribution,
π
t
P
t,t
0
= ht
0
|ψihψ|tiG
t,t
0
=
ht|ψihψ|t
0
iG
∗
t,t
0
∗
= π
0
t
P
t
0
,t
.
4.
If
|ψ
0
i, |ψ
1
i, . . . , |ψ
T
i
are the eigenvectors of
H
with eigenvalues
E
0
< E
1
≤ . . . ≤ E
T
, then
|φ
k
i
:=
P
x∈Ω
hψ
0
|xihx|ψ
k
i|xi
is an eigenvector of
P
with eigenvalue (1
− E
k
)
/
(1
− E
0
). Since
this is the complete list of eigenvectors of
P
, we have shown that the spectral gaps of
H
and
P
satisfy
∆
P
= (1 − E)∆
H
. (24)
The relation eq. (24) means that we can apply techniques developed for upper bounding the spectral
gap of Markov chains to the problem of upper bounding the spectral gap of
H
. A non-trivial example
of such an upper bound is eq. (11): if the overlap of the stationary distribution with the end points
|0i
and
|T i
is constant, we can immediately conclude that the conductance Φ is
O
(
T
−1
), by the fact that
the stationary distribution is normalized; this implies ∆
H
= O(T
−1
).
It turns out we can obtain an even tighter bound by using a characterization of spectral gaps that
applies specifically to birth-and-death chains [33], which we state here as a lemma.
Lemma 19.
If
P
is a birth and death chain with stationary distribution
π
, then the spectral gap ∆
P
satisfies
1
2`
≤ ∆
P
≤
4
`
(25)
where
` := max
max
j:j≤i
0
i
0
−1
X
k=j
π([0, j]
π(k)P
k,k+1
, max
j:j>i
0
j
X
k=i
0
+1
π([j, T ])
π(k)P
k,k−1
(26)
Accepted in Quantum 2018-08-03, click title to verify 24
where i
0
satisfies π([0, i
0
]) ≥ 1/2 and π([i
0
, n]) ≥ 1/2.
In the present case we are seeking a lower bound on
`
in order to have an upper bound on the gap.
To simplify the formulas we assume that the stationary distribution of the weighted history state is
symmetric around
t
=
T/
2 (otherwise the problem divides into two similar cases). Since we are seeking
a lower bound on
`
, we can ignore the factor of
P
k,k+1
≤
1 in the denominator, and we are also free to
replace the maximization over
j
with any fixed choice of
j
. With these simplifications and the choice
of j = 1, eq. (26) becomes
` ≥ ψ
2
0
T/2−1
X
t=1
1
ψ
2
t
.
Applying the inequality of the arithmetic and geometric means yields
T/2−1
X
t=1
1
ψ
2
t
≥
T
2
− 1
ψ
2
1
···ψ
2
T/2−1
−1/k
≥
T
2
− 1
2
T/2−1
X
t=1
ψ
t
−1
,
and so
`
= Ω(
ψ
2
0
T
2
). Together with eq. (25) we have that the spectral gap ∆
P
is
O
(
`
−1
), and it follows
that ∆
H
· ψ
2
0
= O(T
−2
), as claimed.
Finally, we note that theorem 8 can be interpreted as proving that the standard universal adiabatic
construction plus the weighted endpoint modification made above is in a sense optimal for Hamiltonians
of the form eq. (2). First, the problem of upper bounding the spectral gap of universal adiabatic
constructions was addressed before [22] by combining the quantum lower bound for unstructured
search with the technique of spectral gap amplification. This previous work found a general
˜
O
(
T
−1
)
bound (where the tilde hides logarithmic factors) on the spectral gap of any adiabatic Hamiltonian,
an
˜
O
(
T
−2
)
gap for any frustration-free adiabatic Hamiltonian, and finally an
˜
O
(
T
−2
)
bound on the
spectral gap of modified Feynman Hamiltonians of the form eq. (2) when the weights near the endpoints
satisfy a reasonable assumption for any adiabatic computation. Our theorem 8 corroborates this last
result by showing a tight O
(
T
−2
)
upper bound on the spectral gap and the minimum overlap of the
weighted history state with either endpoint of the computation.
6.2 Diameter Bounds for simple generalized ULGs
Following theorem 8, an immediate question is whether we can overcome the upper bound on the
product of penalty overlap and spectral gap, e.g. by deviating from the tridiagonal “path” evolution.
For instance, one might hope that increasing the connectivity of the ULG underlying the circuit
Hamiltonian would yield a larger gap, or would allow us to circumvent theorem 8 altogether. In this
section, we will argue for a lower bound on the diameter of any such graph designed to increase the
connectivity.
Assume we have a circuit Hamiltonian consisting of a family of simple ULGs [15] (as described in
section 2.2.4) and a family of circuits
(
C
i
)
i∈
, e.g. a uniform verifier circuit family. Further suppose
that each of these circuits is “optimally compiled”, in the sense that the product of local unitaries
along any length k path through the ULG cannot be compiled into fewer than k local gates.
Accepted in Quantum 2018-08-03, click title to verify 25
This family of circuits can be implemented by a family of standard circuit Hamiltonians {H
i
}
i∈N
,
each of which has a linear clock ranging from t = 1, . . . , T
i
, where T
i
:= |C
i
| is the number of gates in
the circuit C
i
. This corresponds to a path-like clock:
1 2 3 4 5 T
i
− 1 T
i
Now assume there exists another Hamiltonian H
0
with at least one path between t
= 1
and t
=
T
i
, but
of shorter length T
0
< T
i
, e.g.
1 2 3 4 5 T
i
− 1 T
i
2
0
3
0
T
0
− 1
Since
(1
, . . . , T
i
, T
0
−
1
, . . . ,
2
0
,
1)
forms a loop, the assumption that the ULG is simple implies
(
U
1,2
. . . U
T
i
−1,T
i
)(
U
T
0
−1,T
0
−2
. . . U
2
0
,1
) =
. But demanding this condition for all the circuits in
the family is inconsistent with the hypothesis that the circuit was compiled optimally in first place.
This demonstrates that if we want to increase the UNSAT penalty with more general clock graphs,
we better use frustration, i.e. go beyond simple ULGs; we discuss this case in section 6.4.
6.3 A Clock Diameter Bound
In section 6.2, we saw how in a generalized ULG, we need paths of a minimum length to encode
computation; anything shorter will necessarily conflict with the computational output and introduce
an additional error in a
YES
case; this, however, is a problem, since e.g. for
QMA
-hardness proofs it
is crucial to be able to amplify the YES error to = O(promise gap).
But if we know that there have to be straight sections of length T within any graph, how does this
graph diameter correspond to the spectral gap of the clock Hamiltonian? And can we combine this with
the case of non-simple ULGs (section 6.4)? By lemma 3, we know that E
p
(
, T
)
≤ E
(
H
clock
(
T
) +
P
)
,
even for more general positive semi-definite penalties on an arbitrary number of vertices, all of which
we collect in the term P. In particular, this tells us that we can obtain an upper bound on the UNSAT
penalty solely by looking at the clock part of the Hamiltonian.
Proof of
Theorem 10
The most general such clock is an arbitrary Hermitian matrix, and we develop a diameter bound on
it following [20]. This proves the last of our theorems, i.e.
Theorem 10. Let H, B, π and ∆
H
be as defined above. Then
∆
H
≤
kHk
2
log(2/π
min
)
diam
B
H
2
.
Proof. Let H be Hermitian on
T
, and—as in section 6.1—define
G := (H − λ
min
)/(kHk − λ
min
). (27)
Then spec(G) ⊂ [0, 1]. For two states |ui, |vi ∈
T
, we define their distance under G as
dist
G
(|ui, |vi) := min{k : hu|G
k
|vi 6= 0}
if it exists, and we set
dist
G
(
|ui, |vi
) =
∞
otherwise; this is the case e.g. if
G
is block-diagonal, and
|ui and |vi are vectors with support completely contained in disjoint blocks.
Accepted in Quantum 2018-08-03, click title to verify 26
The reason for calling it a distance is obvious from the equality
dist
G
(|ui, |vi) = min
d : hu|
d
Y
i=1
X
jk
|jihj|G |kihk|
|vi 6= 0
,
i.e. it catches the minimum number of nonzero jumps under
G
necessary to reach some overlap between
|ui and |vi. The diameter of G is then defined as
diam G := max
u
min
v
{dist
G
(|ui, |vi)}.
It is clear that diam G = diam H.
If we use the spectral decomposition
G
=
P
i
λ
i
|ψ
i
ihψ
i
|
and some polynomial
p
, then for any states
|ui and |vi, we have
|hu|p(G) |vi| =
X
i
p(λ
i
) hu|ψ
i
ihψ
i
|vi
≥ p(1)|π
u,v
| +
X
i≥2
p(λ
i
)u
i
¯v
i
≥ p(1)|π
u,v
| − max
i≥2
p(λ
i
)
X
i≥2
|u
i
||v
i
|
≥ p(1)|π
u,v
| − max
i≥2
p(λ
i
),
where π
u,v
:= u
1
¯v
1
, and u
i
:= hu|ψ
i
i, ¯v
i
:= hψ
i
|vi.
One can show that there exists a family of polynomials
p
k
with
deg p
k
=
k
,
p
k
(1) = 1 and
|p
k
(
x
)
| ≤
2(1 +
√
2∆
)
−k
∀x ∈
[∆
,
1]. Assume for now that
π
u,v
>
0. We want to find a condition under which
p(λ
i
) < π
u,v
, so we resolve
2(1 +
√
2∆)
−k
< π
u,v
⇔ −k ln(1 +
√
2∆) < ln
π
u,v
2
⇔ k >
ln(2/π
u,v
)
ln(1 +
√
2∆
.
For
x ∈
(0
,
1) we further have a uniform bound
a
of
ln
(1 +
√
2x
)
≤
(1 + 1
/
√
x
), which yields a diameter
bound of
diam G ≤
1 +
1
√
2∆
ln(2/π
u,v
).
This inequality still depends on our choice of states
|ui
and
|vi
. Assuming that
π
min
=
min
i
|hi|ψ
1
i|
2
denotes the minimum ground state overlap with any basis state
|ii
, we know that
|π
u,v
|
2
≥ π
min
. If
we further assume π
min
> 0, then the diameter bound reads
diam G ≤
1 +
1
√
2∆
ln(2/π
min
).
What about the case where
π
min
= 0? This would mean that there is at least one state
|xi
for which
hx|ψ
1
i
= 0. Since we are interested in encoding computation in the ground state of a Hamiltonian,
and
G
serves as clock, we can dismiss those parts of the Hilbert space in which the ground states
shows zero connectivity; this is the case if
π
min
>
0, and otherwise we restrict
|ui, |vi ∈ supp |ψ
1
ihψ
1
|
.
For the degenerate case we block-diagonalize G and regard each such block separately.
Accepted in Quantum 2018-08-03, click title to verify 27
To formalize this, we define a variant of the diameter which captures the ground space connectivity:
diam
0
G := max
u∈supp|ψ
1
ihψ
1
|
min
v∈supp|ψ
1
ihψ
1
|
{dist
G
(|ui, |vi)}.
The diameter bound then reads
diam
0
G ≤
1 +
1
√
2∆
ln(2/π
0
min
), (28)
where
π
0
min
=
min
i∈supp|ψ
1
ihψ
1
|
|hi|ψ
1
i|
2
. Using the fact from section 6.2 that the diameter for a given
circuit of
T
gates is at least
T
, and applying the definition of
G
in terms of the Hamiltonian
H
,
eq. (27), we obtain theorem 10.
a
This bound is tight up to a factor of 2 ln 2, which is reached at x = 1.
6.4 Frustrated ULGs
In section 6.2 we have seen that if we hope to increase the UNSAT penalty by going beyond a linear
clock evolution, we will also have to go beyond simple ULGs. The case left to be analyzed is therefore
when we allow the quantum register to be frustrated, in the sense that there are two clock labels a and
b with two distinct paths connecting them, and such that the product of unitaries along both paths is
not identical.
As a simple example, consider the following ULG.
G =
a
b
1
U
In case that U = σ
x
, we can immediately write down the ULG Hamiltonian as
H
G
=
2 0 −1 −1
0 2 −1 −1
−1 −1 2 0
−1 −1 0 2
.
As we can see, this Hamiltonian by itself is already a graph Laplacian for the following graph:
a
0
a
1
b
0
b
1
However, our goal is to reduce the number of edges; if we instead work in the |±i-eigenbasis of the
off-diagonal blocks of H
G
, + σ
x
, then
H
G
∼
2 0 −2 0
0 2 0 0
2 0 2 0
0 0 0 2
,
Accepted in Quantum 2018-08-03, click title to verify 28
which in turn corresponds to the graph
a
+
a
−
b
+
b
−
but such that the vertices a
−
and b
−
carry an extra penalty of 2.
This argument also works for more general U: labelling the eigenvalues of
+
U with λ
1
, . . . , λ
n
,
we have
H
G
∼
2 diag(λ
1
, . . . , λ
n
)
diag(
¯
λ
1
, . . . ,
¯
λ
n
) 2
!
. (29)
The eigenvalues thus determine the strength of the edge connection; for λ
i
= 0
(as in the case of
U
=
σ
x
), the graph becomes completely disconnected; the adjoining vertices of the edge hence carry
an extra penalty of
P =
n
X
i=1
(2 − |λ
i
|) |λ
i
ihλ
i
|,
where as in eq. (29) the |λ
i
| ≤ kU
+
k ≤
2
. Similar arguments can be derived for more complicated
graphs; as disconnected graph components introduce degeneracies, each component would need its
own set of in- and output constraints in order to allow a distinction between YES and NO case.
However, if that is the case, then one can analyse the UNSAT penalty of each component separately.
As can be seen in definition 1, the
NO
-
YES
energy difference stems from H
FK
—the Hamiltonian that
includes in- and output penalties; E
(
H
prop
)
is static. The UNSAT penalty would thus arise from the
best such disconnected block, which we could have written down directly in first place. It is thus highly
doubtful that an explicitly-constructed non-simple ULGs will feature an amplified UNSAT penalty over
the simple case.
7 Outlook
One of the main aims of the present work is to motivate new ideas in quantum ground state computation
by focusing on the quantum UNSAT penalty as a metric for the improvement of circuit Hamiltonians.
We discuss a range of open problems related to the UNSAT penalty, some of which either appear
more tractable, or lead to a different perspective on some of the open challenges facing this field; in
particular, we are implicitly discussing relative energy penalties that are not simply made larger by
e.g. increasing the overall norm of the Hamiltonian.
The Classical Baseline. The classical Cook-Levin theorem encodes the history of a classical circuit
into the satisfying assignment of a 3-SAT formula. If the computation has T time steps, then the
associated constraint satisfaction problem has O
(
T
)
local terms. If each f those has a constant norm,
then the classical UNSAT penalty is
Ω(1)
. Therefore we ask: is it possible for a circuit Hamiltonian
containing O
(
T
)
local terms of bounded norm—which may be of a form more general than eq. (2)—to
achieve an UNSAT penalty that is independent of the length of the computation?
Macroscopic UNSAT penalty. Building on the previous question which asks whether the UNSAT
penalty can be made independent of the length of the computation, we further ask whether the UNSAT
Accepted in Quantum 2018-08-03, click title to verify 29
penalty can be made to scale macroscopically with the number of qubits n in the underlying many-
body quantum system. Specifically, is there a circuit Hamiltonian with O
(
poly
(
n
)
T
)
local terms that
achieves a poly
(
n
)
UNSAT penalty that is independent of T? Such a construction could be a useful
step towards fault-tolerant adiabatic computation.
An intuition for this connection can be gained by considering a construction for energetically en-
coded fault-tolerant classical computation, whereby each logical bit could be encoded as an arrangement
of spins in a self-correcting model (e.g. the 2D Ising model). The UNSAT penalty could then have
a macroscopic scaling—i.e. with the number of physical spins representing each logical bit—that is
independent of T .
Constant relative UNSAT penalty. A circuit Hamiltonian with O
(
m
)
local terms of bounded
norm, where m
=
poly
(
T
)
, with constant relative UNSAT penalty E
p
/m would yield a proof of the
quantum PCP conjecture by spectral gap amplification. The reduction consists of applying the circuit
Hamiltonian with constant relative UNSAT penalty to the circuit verifier that decides the ground state
energy of the arbitrary input local Hamiltonian.
It is a testament to Feynman’s great legacy that an idea first introduced in 1985 has had such a
profound impact on a remarkably wide scope of research, from condensed matter physics to quantum
computation, and that despite the growth of the field of Hamiltonian complexity his original construc-
tion continues to remain essentially unchanged to date. We do not know whether or where limitations
of improving the circuit-to-Hamiltonian construction will be reached, but hope that our contribution
marks some of its limits, and helps to push other boundaries a little further.
8 Acknowledgements
J. B. acknowledges support from the German National Academic Foundation, the EPSRC (grant
1600123), and the Draper’s Research Fellowship at Pembroke College. E. C. acknowledges support pro-
vided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF
Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).
J. B. would also like to thank Thomas Vidick and the IQIM for hospitality during spring 2016 and
summer 2017. We thank Toby Cubitt for useful discussions regarding section 5.2.1 and appendix A.2.
Accepted in Quantum 2018-08-03, click title to verify 30
References
[1]
Alexei Yu. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. “Classical and quantum computing”.
In: Quantum Information. New York, NY: Springer New York, 2002, pp. 203–217.
[2]
Julia Kempe, Alexei Kitaev, and Oded Regev. “The Complexity of the Local Hamiltonian
Problem”. In: SIAM Journal on Computing 35.5 (2006), pp. 1070–1097. issn: 0097-5397. arXiv:
quant-ph/0406180.
[3]
Roberto Oliveira and Barbara M. Terhal. “The complexity of quantum spin systems on a two-
dimensional square lattice”. In: Quantum Information & Computation (2005), pp. 1–23. arXiv:
quant-ph/0504050.
[4]
Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev.
“Adiabatic quantum computation is equivalent to standard quantum computation”. In: SIAM
review 50.4 (2008), pp. 755–787. arXiv: quant-ph/0405098.
[5]
Jacob Biamonte and Peter Love. “Realizable Hamiltonians for universal adiabatic quantum
computers”. In: Physical Review A 78.1 (2008), p. 012352. arXiv: 1311.3161.
[6]
Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. “The power of quantum
systems on a line”. In: Communications in Mathematical Physics 287.1 (2009), pp. 41–65. arXiv:
0705.4077.
[7] Toby Cubitt and Ashley Montanaro. “Complexity classification of local Hamiltonian problems”.
In: SIAM Journal on Computing 45.2 (2016), pp. 268–316. arXiv: 0704.1287.
[8]
Dorit Aharonov, Itai Arad, and Thomas Vidick. “Guest column: the quantum PCP conjecture”.
In: Acm SIGACT news 44.2 (2013), pp. 47–79.
[9]
Richard P. Feynman. “Quantum Mechanical Computers”. In: Optics News 11.2 (1985), p. 11.
issn: 0098-907X.
[10]
David Gosset and Daniel Nagaj. “Quantum 3-SAT Is QMA1-Complete”. In: 2013 IEEE 54th
Annual Symposium on Foundations of Computer Science. IEEE, 2013, pp. 756–765. isbn : 978-0-
7695-5135-7.
[11]
Daniel Gottesman and Sandy Irani. “The Quantum and Classical Complexity of Translationally
Invariant Tiling and Hamiltonian Problems”. In: Theory of Computing 9.1 (2013), pp. 31–116.
issn: 1557-2862. arXiv: 0905.2419.
[12]
Nikolas P. Breuckmann and Barbara M. Terhal. “Space-time circuit-to-Hamiltonian construction
and its applications”. In: Journal of Physics A: Mathematical and Theoretical 47.19 (2014),
p. 195304. issn: 1751-8113. arXiv: 1311.6101.
[13]
Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami. “The Local Hamiltonian problem on
a line with eight states is QMA-complete”. In: Quantum Information and Computation 13.9&10
(2013), p. 28. arXiv: 1312.1469.
[14] Daniel Nagaj. Tick-tock Goes the Clock. Lecture at the Simons Institute. 2014.
[15]
Johannes Bausch, Toby Cubitt, and Maris Ozols. “The Complexity of Translationally-Invariant
Spin Chains with Low Local Dimension”. In: Annales Henri Poincar´e (2017), p. 52. arXiv:
1605.01718.
[16]
Na¨ıri Usher, Matty J. Hoban, and Dan E. Browne. “Nonunitary quantum computation in the
ground space of local Hamiltonians”. In: Physical Review A 96.3 (2017), p. 032321. issn: 2469-9926.
arXiv: 1703.08118.
Accepted in Quantum 2018-08-03, click title to verify 31
[17]
Libor Caha, Zeph Landau, and Daniel Nagaj. “The Feynman-Kitaev computer’s clock: bias, gaps,
idling and pulse tuning”. In: 2017. arXiv: 1712.07395.
[18]
Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. “The detectability lemma and
quantum gap amplification”. In: Proceedings of the 41st annual ACM symposium on Symposium
on theory of computing - STOC ’09. New York, New York, USA: ACM Press, 2009, p. 417. isbn:
9781605585062.
[19]
Johannes Bausch. “Quantum Stochastic Processes and Quantum Many-Body Physics”. PhD thesis.
University of Cambridge, Oct. 2017.
[20]
Jonathan Kelner. 18.409, Topics in Theoretical Computer Science: An Algorithmist’s Toolkit. Fall
2009, Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu.
[21]
Asher Peres. “Reversible logic and quantum computers”. In: Physical Review A 32.6 (1985),
pp. 3266–3276. issn: 0556-2791.
[22]
Anand Ganti and Rolando Somma. “On the gap of Hamiltonians for the adiabatic simulation of
quantum circuits”. In: International Journal of Quantum Information 11.07 (2013), p. 1350063.
arXiv: 1307.4993.
[23] Toby Cubitt. Lecture notes in Advanced Quantum Information Theory. 2015.
[24]
David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. Markov chains and mixing times.
American Mathematical Soc., 2009. isbn: 0821847392.
[25]
J. Cheeger. “A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis”.
In: Papers dedicated to Salomon Bochner (1969). Princeton Univ. Press, Princeton, N. J., 1970,
195–199.
[26]
Alistair Sinclair and Mark Jerrum. “Approximate counting, uniform generation and rapidly
mixing Markov chains”. In: Information and Computation 82.1 (1989), pp. 93–133.
[27] Dorit Aharonov and Tomer Naveh. Quantum NP-a survey. 2002. arXiv: quant-ph/0210077.
[28]
Tameem Albash and Daniel A. Lidar. “Adiabatic quantum computation”. In: Rev. Mod. Phys. 90
(1 2018), p. 015002. arXiv: 1611.04471.
[29]
Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, and Peter Shor. “Unstructured
Randomness, Small Gaps and Localization”. In: Quantum Information & Computation 11.9–10
(2011). arXiv: 1010.0009.
[30]
Camille Jordan. “Essai sur la g´eom´etrie `a n dimensions”. In: Bulletin de la Soci´et´e math´ematique
de France 3 (1875), pp. 103–174. issn: 0037-9484.
[31]
Sergey Bravyi, Arvid Bessen, and Barbara Terhal. “Merlin-Arthur games and stoquastic complex-
ity”. In: 2006. arXiv: quant-ph/0611021.
[32]
Sergey Bravyi and Barbara Terhal. “Complexity of stoquastic frustration-free Hamiltonians”. In:
Siam journal on computing 39.4 (2009), pp. 1462–1485. arXiv: 0806.1746.
[33]
Guan-Yu Chen and Laurent Saloff-Coste. “On the mixing time and spectral gap for birth and
death chains”. In: ALEA Lat. Am. J. Probab. Math. Stat. 10.1 (2013), pp. 293–321. arXiv:
1304.4346.
Accepted in Quantum 2018-08-03, click title to verify 32
A Appendix
A.1 An Ω(T
−2
) Scaling from Padding with Identities
In this appendix we show that a modified version of Kitaev’s circuit-to-Hamiltonian construction that
pads the input and output clock states with an
Ω(
T
)
-sized identity circuit and spreading out the
input and output penalty yields an
Ω(
T
−2
)
UNSAT penalty that can be proven by the geometrical
lemma. Let U
1
, . . . , U
T
be a quantum circuit on some space H. Define a padded circuit Hamiltonian
on
2T
⊗ H as
H =
0
X
t=−T/2
(|tiht| + |t + 1iht + 1| − |t + 1iht| − |tiht + 1|) ⊗ (30)
+
T
X
t=0
(|tiht| + |t + 1iht + 1|) ⊗ − |t + 1iht| ⊗ U
t
− |tiht + 1| ⊗ U
†
t
(31)
+
3T/2
X
t=T
(|tiht| + |t + 1iht + 1| − |t + 1iht| − |tiht + 1|) ⊗ . (32)
The overall encoded circuit of this Hamiltonian is thus
···
| {z }
T/2 times
U
T
···U
1
···
| {z }
T/2 times
=: U
0
3T/2
···U
0
−T/2
.
The ground state of this unbiased clock construction is a uniform superposition over the history of the
computation, i.e. |Ψi =
1
√
2T
P
3T/2
t=−T/2
|ti ⊗ U
0
t
···U
0
−T/2
|φi.
For some input and output penalty
Π
in
,
Π
out
acting on the circuit qubits, we define the padded
penalty Hamiltonian as
P =
0
X
t=−T/2
|tiht| ⊗ Π
in
+
3T/2
X
t=T
|tiht| ⊗ Π
out
. (33)
Denote the projector onto the kernel of this penalty term with
Π
pen
:=
0
X
t=−T/2
|tiht| ⊗ Π
⊥
in
+
3T/2
X
t=T
|tiht| ⊗ Π
⊥
out
+
T −1
X
t=1
|tiht| ⊗ .
Let W be the usual diagonalizing operator for H. We first bound the angle θ between ker P and ker H:
cos
2
θ = max
|η
0
i∈ker WHW
†
hη
0
|
0
X
t=−T/2
|tiht| ⊗ Π
⊥
in
+
3T/2
X
t=T
|tiht| ⊗ Π
⊥
out
+
T −1
X
t=1
|tiht| ⊗
|η
0
i
= max
|φi
1
2T
hφ|
0
X
t=−T/2
|tiht| ⊗ Π
⊥
in
+
3T/2
X
t=T
|tiht| ⊗ Π
⊥
out
+
T −1
X
t=1
|tiht| ⊗
|φi
= max
|φi
1
4
hφ|Π
in
+ UΠ
out
U
†
|φi +
1
2
.
The inner product is then bounded by the acceptance probability of the circuit, i.e.
max
|φi
hφ|Π
in
+ UΠ
out
U
†
|φi ≤ + cos ϑ ≤ 1 + .
Accepted in Quantum 2018-08-03, click title to verify 33
Overall, this gives a bound
cos
2
θ ≤
1
4
(3 + ), (34)
which gives precisely the same UNSAT penalty as the un-padded version used in section 3.3.
A.2 Proof of Ω(T
−2
) Scaling without Jordan’s Lemma
We start in section 5.2.1, after eq. (17). If our goal is to avoid using Jordan’s lemma, we need the
following technical result.
Lemma 20.
Let Π
∈
d×d
be a projector, and two sets of vectors
{|e
i
i}, {|f
i
i}
which span
d
such
that
he
i
|e
j
i = hf
i
|f
j
i = δ
ij
(i)
he
i
|f
j
i = 0 (ii)
he
i
|Π |e
j
i ∝ δ
ij
(iii)
hf
i
|Π |f
j
i ∝ δ
ij
(iv)
Then either:
1. For all i, he
i
|Π |f
j
i 6= 0 for at most one j.
2. If he
i
|Π |f
j
i 6= 0 and he
i
|Π |f
j
0
i 6= 0 for some j
0
6= j, then necessarily hf
j
|Π |f
j
i = hf
j
0
|Π |f
j
0
i.
Proof.
First observe that (
i
) and (
ii
) imply that the set
{|e
i
i} ∪ {|f
i
i}
forms an orthonormal basis of
d
. For any j for which
he
i
|Π |f
j
i 6= 0, (35)
we can thus show
0 6= he
i
|Π |f
j
i
= he
i
|ΠΠ |f
j
i since Π is a projector
= he
i
|Π
X
k
|e
k
ihe
k
| +
X
l
|f
l
ihf
l
|
!
Π |f
j
i as the |e
i
i and |f
i
i form an ONB
= he
i
|Π |e
i
ihe
i
|Π |f
j
i + he
i
|Π |f
j
ihf
j
|Π |f
j
i by (iii) and (iv)
= he
i
|Π |f
j
i(he
i
|Π |e
i
i + hf
j
|Π |f
j
i),
and thus
he
i
|
Π
|e
i
i
+
hf
j
|
Π
|f
j
i
= 1. If there exist two
j 6
=
j
0
for which eq. (35) holds, then necessarily
hf
j
|Π |f
j
i = hf
j
0
|Π |f
j
0
i.
The following lemma now gives an explicit construction of the block-diagonalizing unitary V. We
will use the resulting block-diagonalizing unitary V to bring H
Kitaev
into a shape similar to A, but
where V
†
BV connects the separate blocks with some off-diagonal entries. By bounding the magnitude
of the latter, we can finally lower-bound the overall spectrum of H
Kitaev
by Ω(T
−2
).
Lemma 21.
Let
M ∈
d×d
be a projector. Then for any 1
≤ s < d
, there exists a block-diagonal
unitary
V
=
V
0
⊕ V
00
with
dim V
0
=
s
such that
D
=
V
†
MV
is stoquastic. Furthermore,
V
can be
Accepted in Quantum 2018-08-03, click title to verify 34
chosen such that—if we denote the rank of the upper-left
s × s
block with
r
a
and the complementary
lower-right block rank with r
b
—D
ij
6= 0 if and only if
i = j ∧j ≤ r
a
(i)
or s ≤ i = j ≤ s + r
b
(ii)
or s ≤ j = s + i ≤ min{r
a
, r
b
} (iii)
or s ≤ i = s + j ≤ min{r
a
, r
b
}. (iv)
Proof.
Let
r
=
rank M
, and write
M
=
P
r
i=1
|m
i
ihm
i
|
as eigendecomposition with orthonormal vectors
|m
i
i
. Split each of the eigenvectors
|m
i
i
=:
|a
i
i ⊕ |b
i
i
, where
dim |a
i
i
=
s
(we abuse the direct sum
notation here to mean simply dovetailing two vectors). Then M can be expressed as block-matrix:
M =
r
X
i=1
|m
i
ihm
i
| =:
X
i
|a
i
iha
i
| |a
i
ihb
i
|
|b
i
iha
i
| |b
i
ihb
i
|
!
=:
M
aa
M
ab
M
†
ab
M
bb
!
.
The matrix
M
aa
is Hermitian since
M
is. We can thus find a diagonalizing unitary
A
:=
P
s
i=1
|α
i
ihi|
,
such that
A
†
M
aa
A
is diagonal, and similarly
B
for
M
bb
; here the
|ii
just label the standard basis, and
the
|α
i
i
an orthonormal eigenbasis of
A
. We further pick
A
and
B
such that the nonzero eigenvalues of
each block are sorted to the top left, which we can always achieve. If we now were to set
V
=
A ⊕ B
,
we would immediately verify claims (i) and (ii).
It is, however, not obvious what
A
†
M
ab
B
looks like, so we need to do some more work. We calculate
the matrix entries:
hx|A
†
M
ab
B |yi =
s
X
j=1
hx|jihα
j
|
X
i
|a
i
ihb
i
|
d−s
X
k=1
|β
k
ihk|yi =
X
i
hα
x
|a
i
ihb
i
|β
y
i. (36)
We expand
|α
0
i
i
:=
|α
i
i ⊕ |0i
, and
|β
0
i
i
:=
|0i ⊕ |β
i
i
, which allows us to apply lemma 20 to
M
,
{|α
0
i
i}
and
{|β
0
i
i}
. Take some row
x
; if there is only one column index
y
for which eq. (36)
6
= 0 we are done. If,
on the other hand, there are at least two
y 6
=
y
0
for which eq. (36)
6
= 0, we can define a unitary
R
via
β
0
y
7−→
1
p
1 + γ
2
β
0
y
+ γ
β
0
y
0
β
0
y
0
7−→
1
p
1 + γ
2
β
0
y
− γ
β
0
y
0
,
where
γ
=
hα
x
|
Π
|β
0
y
i/ hα
x
|
Π
|β
0
y
0
i
. It is then easy to verify that
hx|
(
A ⊕ BR
)
†
M
(
A ⊕ BR
)
|y
0
i
= 0,
and because of the degeneracy hy|B
†
M
bb
B |yi = hy
0
|B
†
M
bb
B |y
0
i, R
†
B
†
MBR is still diagonal.
Iterate this process; once in every row there is at most one off-diagonal entry. As each resulting
matrix remains Hermitian, the same process immediately proves that there is at most one off-diagonal
entry in every column. It is now clear that we can conjugate this
V
†
MV
with a diagonal matrix where
each entry is of modulus 1, thus eliminating the different phases in the
ξ
i
, and such that the resulting
sign is negative on all off-diagonal entries. Such a matrix is necessarily unitary and renders the resulting
matrix stoquastic by definition, and we absorb this phase elimination unitary into V.
Accepted in Quantum 2018-08-03, click title to verify 35
After some reordering, the resulting matrix V
†
MV has the form
λ
1
0 0 · · · · · · 0 0 −|ξ
1
| 0 0 · · · · · · 0 0
0 λ
2
.
.
.
0 0 −|ξ
2
|
.
.
.
0
0
.
.
.
.
.
.
.
.
.
.
.
. 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
λ
r
a
0
.
.
.
.
.
.
.
.
.
−|ξ
r
o
| 0
.
.
.
.
.
. 0 0
.
.
.
.
.
.
.
.
. 0 0
.
.
.
.
.
.
0
.
.
.
.
.
.
0 0
.
.
.
.
.
.
0
0 0 · · · · · · · · · 0 0 0 0 · · · · · · · · · 0 0
−|ξ
1
| 0 0 · · · · · · 0 0 µ
1
0 0 · · · · · · 0 0
0 −|ξ
2
|
.
.
.
0 0 µ
2
.
.
.
0
0
.
.
.
.
.
.
.
.
.
0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
−|ξ
r
o
| 0
.
.
.
.
.
.
µ
r
b
0
.
.
.
.
.
. 0 0
.
.
.
.
.
. 0 0
.
.
.
.
.
.
0
.
.
.
.
.
.
0 0
.
.
.
.
.
.
0
0 0 · · · · · · · · · 0 0 0 0 · · · · · · · · · 0 0
(37)
where r
o
:= min{r
a
, r
b
}, which finally satisfies claims (i) − (iv). The claim of the lemma follows.
One can then show by an application of lemma 16 that for a NO-instance, r
o
= r = d/2.
The remaining argument follows as in section 5.2.1.
Accepted in Quantum 2018-08-03, click title to verify 36