have resulted in QMA-complete local Hamiltonian problems with restricted properties such as 2-local
interactions , 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
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 . 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  and cast into its current form by
Kitaev , 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
modiﬁcations in depth , and revisit the spectral properties of Kitaev’s original construction .
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
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
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
) 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