Analysis and limitations of modiﬁed
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 modiﬁed 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
)
terms of numbers of qubits.
Furthermore, we establish limits on the increase in the ground energy due to input and
output penalty terms for modiﬁed 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 Modiﬁed 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
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
suﬃce 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 eﬀorts
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 classiﬁcation 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, 1015]. Only recently steps have been undertaken to analyse
modiﬁcations 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 satisﬁed 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 satisﬁable 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 speciﬁc 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-deﬁned relation between runtime T and the corresponding
Hamiltonian’s system size n for any speciﬁc 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 deﬁned 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 speciﬁc 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 modiﬁcations 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 modiﬁed 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
prop
to validate speciﬁc inputs and the
outputs of the computation. We deﬁne the sum of all these terms to be the modiﬁed 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 speciﬁcally, 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 speciﬁc 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 deﬁnition 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 veriﬁer circuit for e.g.
QMA
or
QMA
EXP
veriﬁcation
purposes.
For a speciﬁc set of ﬁxed in- and output constraints and ﬁxed 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 deﬁne 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 deﬁned
it here. This makes sense: we want to completely decouple the notion of how well a modiﬁed circuit
Hamiltonian can penalize in- and output from what the circuit itself does.
This leads to our deﬁnition of the quantum UNSAT penalty of a circuit-to-Hamiltonian construction,
which quantiﬁes the extent to which a Hamiltonian as in eq. (2) can enforce the input and output
penalties described above for an arbitrary circuit.
Deﬁnition 1.
Let the
E
(
H
FK
) and
E
(
H
prop
) be the ground state energies of
H
FK
and
H
prop
, respec-
tively, and deﬁne 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 deﬁned 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 ﬁrst step in analyzing the UNSAT penalty of modiﬁed Feynman Hamiltonians is to apply a
modiﬁed 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 modiﬁed 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
eE
hψ| h
e
|ψi /|E|
quantity that was previously deﬁned
and analyzed using the detectability lemma [18]. We use the term UNSAT penalty to emphasize that it is the energy
diﬀerence 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 coeﬃcients
{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 modiﬁed 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 ﬁrst main result;
in order to prove it, we use the geometrical lemma for modiﬁed 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 modiﬁed 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.
The modiﬁed 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 ﬁnal Hamiltonian H
ﬁnal
:= H
in
+ H
prop
,
H(s) = (1 s)H
init
+ sH
ﬁnal
. (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 suﬃciently 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 eﬃciently produce the state at the ﬁnal adiabatic time s
= 1
,
one needs to measure the clock register and condition success on ﬁnding the computation in its ﬁnal
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
increases the length of the clock (and hence the number of qubits needed to represent it) by a constant
factor. This is where the modiﬁed 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 ﬁnding the system in the ﬁnal conﬁguration 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 modiﬁed construction, resulting in the
following theorem.
Theorem 6.
For any probability
p >
0 there is a frustration-free modiﬁed circuit Hamiltonian as
in eq. (2) with
π
T
=
p
such that the minimum spectral gap of the linear interpolation
(6)
satisﬁes
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 ﬁrst 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 ﬁnd 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 modiﬁed 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 deﬁne circuits which evolve
according to unitary gates along their edges, see ﬁg. 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 ﬁve 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 ﬁrst 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
iV
in
|iihi|
Π
in,i
and
H
in
:=
P
iV
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 satisﬁes
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 deﬁne the notion of diameter with respect to particular basis B, which is
deﬁned 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 deﬁnes a probability distribution π
(
x
) :=
|hx|ψi|
2
for x B. Let π
min
:=
min
x∈B
π
(
x
)
and deﬁne 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 deﬁned 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 modiﬁed 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 modiﬁed
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 eﬃciently. Caha, Landau, and Nagaj show that the overlap with the ﬁnal 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 Modiﬁed 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-deﬁnite 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-deﬁnite, but this will not present a problem
in applying the geometrical lemma above because
H
prop
itself is positive semi-deﬁnite). 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 ﬁrst 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 ﬁrst 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 coeﬃcients
{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 deﬁned on S,
P
t,t+1
=
1
4
min
1,
π
t+1
π
t
, P
t,t1
=
1
4
min
1,
π
t1
π
t
P
t,t
= 1 P
t,t+1
P
t,t1
(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 coeﬃcient 1
/
4 implies
P
t,t
1
/
2 for all
t
and so
P
is positive semi-deﬁnite.
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
satisﬁes
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 eﬀort has been devoted to characterizing spectral gaps
of Markov chains. A particularly fruitful characterization proceeds by deﬁning a quantity called the
conductance,
Φ := min
S
Q(S, S
c
)
min{π(S), π(S
c
)}
, Q(S, S
c
) :=
X
xS,yS
c
π(x)P (x, y)
which determines the spectral gap within a quadratic factor,
Φ
2
2
P
. (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 ﬁrst of our main theorems, which we re-state.
Theorem 5.
There is a frustration-free modiﬁed 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 ﬁg. 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 diﬀerent 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.
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 modiﬁed 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 modiﬁed 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 ﬁducial 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
. Deﬁning 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
= Θ(
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 speciﬁcally
= Ω(
T
2
)
and k
˙
Hk
=
O
(1)
so that t