Analysis and limitations of modified
circuit-to-Hamiltonian constructions
Johannes Bausch
DAMTP, CQIF, University of Cambridge
Elizabeth Crosson
IQIM, California Institute of Technology

Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems.  Kitaev applied this construction to demonstrate -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 $\Omega(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 $\BigO(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 $\Omega(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 $\BigO(T^{-2})$ bound from linear clocks to this more general setting.
In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.

§ INTRODUCTION

The initial demonstration of QMA-completeness of the local Hamiltonian problem <cit.> 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 <cit.>.
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 <cit.> more suitable for eventual physical implementation <cit.>.
The success of these efforts have resulted in QMA-complete local Hamiltonian problems with restricted properties such as 2-local interactions <cit.>, low dimensional geometric lattices <cit.>, and translational invariance, as well as a complete classification of the complexity of the 2-local Hamiltonian problem for any set of interaction couplings <cit.>.

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 <cit.>.
Such questions motivate us to seek (or to limit the possibility 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 <cit.> and cast into its current form by Kitaev <cit.>, the construction remains relatively little changed, having undergone only some gradual evolutions since its modern introduction <cit.>.
Only recently steps have been undertaken to analyse modifications in depth <cit.>, and revisit the spectral properties of Kitaev's original construction <cit.>.

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 $\Omega(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.

* Can we modify the Feynman-Kitaev construction—by introducing clock transitions with varying weights, or by adding branching as analysed in the context of unitary labeled graphs—in order to improve on the known $\Omega(T^{-3})$ bound on the UNSAT penalty?  Is the geometrical lemma tight for Kitaev's original construction?

* Can the circuit-to-Hamiltonian construction be improved with regard to universal adiabatic computation?

* Can deviations from the linear circuit embedding improve the UNSAT penalty, e.g. by introducing more general clock transitions such as branching and loops, and by allowing arbitrary weight transitions for those?

In the next section, we motivate each of these questions and formally state our results.

§ RESULTS AND OVERVIEW

§.§ Background and Notation

We analyze history state Hamiltonians on a bipartite Hilbert space $\H=\field C^{T+1}\otimes \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,

\begin{equation}
\ket\psi = \sum_{t = 0}^T \psi_t \ket t \otimes \left (\op U_t \cdots \op U_1\right) \ket\xi, \label{eq:weighted}
\end{equation}

where as usual $\op U_T,\ldots,\op U_1$ are (local) quantum gates, $\ket\xi$ is an arbitrary input to the computation, and $\ket\psi$ is a normalized state, so that in particular $\pi_t := \psi^*_t \psi_t$ is a probability distribution over $\{0,\ldots,T\}$.
Hamiltonians with ground states of the form as in <ref> arise from modifications to the usual terms of the Feynman circuit Hamiltonian,

\begin{equation}\label{eq:ham}
\Hprop := \sum_{t = 0}^T a_t \ketbra t \otimes \1 + \sum_{t =0}^{T-1} \left( b_t\ketbra{t+1}{t}\otimes \op U_t + b^*_t \ketbra{t}{t+1}\otimes \op U^\dagger_t \right),
\end{equation}

where we restrict $|a_t|,|b_t|\leq 1$ for $t = 0,\ldots,T$.
Note that most if not all of the constructions that break down the $\BigO(\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 <ref>, up to a constant prefactor (see <ref>).

We denote the clock part of <ref>—i.e. the part of the Hamiltonian only acting on the clock register—with

\begin{equation}\label{eq:clockham}
\op H_\textnormal{clock} = \sum_{t=0}^T a_t \ketbra t\otimes\1 + \sum_{t=0}^{T-1}(b_t\ketbra{t+1}{t} + b_t^*\ketbra{t}{t+1}).
\end{equation}

In addition to the part of the Hamiltonian which checks the propagation of the circuit, projectors $\Hin:= \ketbra 0\otimes \Pin$ and $\Hout := \ketbra T\otimes \Pout$ can be added to $\Hprop$ 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,

\begin{equation}\label{eq:mFK}
\HFK:=\Hprop + \Hin + \Hout,
\end{equation}

as opposed to the Feynman circuit Hamiltonian in <ref>, which is just the propagation part $\Hprop$ without the penalties.

More specifically, the ground space of $\Hprop + \Hin$ will be spanned by computations starting from a valid input computation (i.e. those for which $\ket\xi\in\ker\Pin$ in <ref>), and $\Hout$ will raise the energy of the state $\ket\psi$ in <ref> when $\op U_T\cdots \op U_1\ket\xi\not\in\ker\Pout$.
The magnitude of this frustration between the incompatible ground spaces of $\Hin + \Hprop$ and $\Hout$ will depend on the circuit encoded by $\HFK$ and the specific in- and output energy penalties, i.e. the maximum acceptance probability of the circuit

\begin{equation*}
\epsilon:=\max_{\subalign{\ket\xi &\in \ker \Pin\\\ket\eta &\in \ker \Pout} }=\bra\eta \op U_T\cdots \op U_1\ket\xi.
\end{equation*}

In the following definition we take the $\Pin$ and $\Pout$ that are used in the standard construction: $\Pout :=\proj 0$ measures a single qubit and penalizes it in state $\ket 0$ (i.e. “not accepted”), and $\Pin$ constrains a fraction of the input qubits to the $\ket 0$ 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 allows the embedded computation to act as a verifier circuit for e.g. or verification purposes.

For a specific set of in- and output constraints and 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.
Therefore, we let $C(\epsilon,T)$ be the set of circuits of size $T$ for which the maximum acceptance probability is $\epsilon$ for any state obeying the in- and output constraints $\Pin$ and $\Pout$,

\begin{equation*}
C(\epsilon,T) := \{\op U_1,\ldots,\op U_T :  \max_{\subalign{\ket\xi &\in \ker \Pin\\\ket\eta &\in \ker \Pout} } |\bra\xi \op U_1 \cdots \op U_T \ket\eta|^2 = \epsilon\}.
\end{equation*}

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 <ref> can enforce the input and output penalties described above for an arbitrary circuit.

Let the $E(\HFK)$ and $E(\Hprop)$ be the ground state energies of $\HFK$ and $\Hprop$, respectively, and define the quantum UNSAT penalty $E_p(\epsilon,T)$

\[
E_p(\epsilon, T) := \min_{\op U_1,\ldots,\op U_T \in C(\epsilon,T) } E(\HFK) - E(\Hprop).
\]

The reason for explicitly subtracting the energy term $E(\Hprop)$ is that this quantity is not necessarily zero for propagation Hamiltonians of the form (<ref>), 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.[The term “UNSAT” derives from the related QUNSAT$_\psi=\sum_{e\in E}\bra\psi \op h_e \ket\psi / |E|$ quantity that was previously defined and analyzed using the detectability lemma <cit.>.
We use the term UNSAT penalty to emphasize that it is the energy difference between accepting and non-accepting computations.]

§.§ Results

§.§.§ 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 <cit.>) to “undo” the computation and show that $\Hprop$ is unitarily equivalent to a clock Hamiltonian which acts trivially on the computational register.

If $\op W := \sum_{t=0}^T \proj t \otimes (\op U_t \cdots \op U_1)$, then $\op W$ is unitary and $\op W^\dagger \Hprop \op W = \op H_\textnormal{clock} \otimes \1$, where the clock Hamiltonian $\Hclock$ is given by <ref>.

Next we apply the same geometrical lemma used in Kitaev's proof to lower bound the UNSAT penalty of modified Feynman Hamiltonians.

If the spectral gap of the corresponding clock Hamiltonian $\Hclock(T)$—denoted  $\Delta_{\op H}(T)$—is less than the (constant) spectral gap of $\Hin + \Hout$, then

\begin{equation}
\label{eq:geo} \frac{\Delta_{\op H}(T)}{4} (1 - \sqrt{\epsilon}) \times \min\{\pi_0, \pi_T\} \le E_p(\epsilon,T) \le E\left(\Hclock(T) + \ketbra0 + \ketbra T\right ) .
\end{equation}

The upper bound follows from the operator inequalities $\Pi_\textrm{in} \preceq \mathbbm{1}$ and $\Pi_\textrm{out} \preceq \mathbbm{1}$, 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 $\ket{\psi_0}$ of $\Hprop$ such that $\bra{\psi_0}\Pin\ket{\psi_0}$ is maximized, and analogously for $\Pout$).
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.

For any probability distribution $\mu$ with support everywhere on its domain $\{0,\ldots,T\}$, there is a choice of coefficients $\{a_t,b_t\}_{t=0}^T$ in <ref> such that $\Hclock$ is stoquastic and frustration-free  and has a ground space spanned by states of the form <ref> with weights $\psi_t = \sqrt{\mu_t}$.

Using <ref> we exhibit a modified Hamiltonian for a target ground state distribution with $\pi_0,\pi_T\ge1/4$, and show that it has a spectral gap that is $\Omega(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.

There is a frustration-free modified circuit Hamiltonian as in <ref> with an UNSAT penalty $E_p(\epsilon, T)$ that is $\Omega((1 - \sqrt{\epsilon})T^{-2})$.

In <ref> we use the geometrical lemma to show that padding the standard circuit-to-Hamiltonian construction with $T$ input and output penalties also achieves an $\Omega(T^{-2})$ scaling of the UNSAT penalty.

§.§.§ Universal Adiabatic Computation

The modified circuit Hamiltonian used in <ref> also has a potential advantage for universal adiabatic computation (AQC).  The original construction of universal AQC linearly interpolates between the initial $\op H_{\textrm{init}}:= \op H_{\textrm{in}}$ constraint and the final Hamiltonian $\op H_{\textrm{final}} := \op H_{\textrm{in}} + \op H_{\textrm{prop}}$,

\begin{equation}
\op H(s) = (1-s) \op H_{\textrm{init}} + s \op H_{\textrm{final}}.\label{eq:adiabaticLinear}
\end{equation}

By initializing the system in the ground state of $\op H_{\textrm{init}}$ at s = 0, and increasing $s$ to 1 in a continuous fashion and sufficiently slowly, the system will remain in its instantaneous ground state.  This requires the total time for $s$ to rise from 0 to 1 to scale as $\textrm{poly}(n,\Delta_{\min}^{-1})$, where $\Delta_{\min} := \min_s \Delta_{\op H(s)}$ and $n$ the system's size.  In <cit.> it is proven that $\Delta_{\min} = \Omega(T^{-2})$ for the linear interpolation (<ref>) and the standard $\op H_{\textrm{prop}}$ from Kitaev's construction.

Since the goal of universal AQC is to efficiently produce the state at the final time $t = T$, one needs to measure the clock register and condition success on finding the computation in its final 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 $\Omega(1)$ probability by the “padding with the identity” trick, e.g. by dovetailing the computation by a series of identity gates for $t=T,\ldots,4T$.  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 <ref> 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.  To show that this works we need to lower bound $\Delta_{\min}$ for this modified construction, resulting in the following theorem.

For any probability $p > 0$ there is a frustration-free modified circuit Hamiltonian as in <ref> with $\pi_T = p$ such that the minimum spectral gap of the linear interpolation (<ref>) satisfies $\Delta_{\min} = \Omega(T^{-2})$.

§.§.§ Tightness of the Geometrical Lemma

A natural question is whether the lower bound given by the geometrical lemma is asymptotically tight—$\Omega(T^{-3})$, as stated e.g. in Kitaev's original paper <cit.>—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,

\begin{align}
\Hprop & = \sum_{t =0}^{T-1} \left (\ketbra{t}\otimes\1 + \ketbra{t+1}\otimes\1 - \ketbra{t+1}{t}\otimes \op U_t - \ketbra{t}{t+1}\otimes \op U^\dagger_t \right),\label{eq:standardHam} \\
\ket\psi          & = \frac{1}{\sqrt{T+1}}\sum_{t = 0}^T \ket t \otimes \left(\op U_t \ldots \op U_1 \right) \ket\xi \label{eq:standardHistoryState}
\end{align}

and we find that $E(\HFK) = \Omega(T^{-2})$ for $\Hprop$ as in <ref>.
We capture this in the following theorem.

The UNSAT penalty in Kitaev's local Hamiltonian construction is $\Omega(T^{-2})$.

Note that this result has been independently proven using Jordan's lemma type techniques by  <cit.> and us <cit.>.
In this work, we include a direct proof not based on Jordan's lemma, which can be found in <ref>.

§.§.§ Limitations on Further Improvements

Finally, by applying the lower bound in <ref> to modified Feynman Hamiltonians of the form in <ref>, we show that the scaling of the UNSAT penalty obtained in <ref> is the optimal scaling that can be achieved.

Let $\ket\psi$ be the ground state of a Hamiltonian $\op H$ with eigenvalues $E_0 \leq E_1 \leq \ldots \leq E_T$.
If $\op H$ is tridiagonal in the basis $\{\ket0,\ldots,\ket T\}$,

\begin{equation*}
\op H := \sum_{t = 0}^T a_t \ketbra t + \sum_{t =0}^{T-1} \left ( b_t\ketbra{t+1}{t} + b^*_t\ketbra{t}{t+1} \right),
\end{equation*}

with $|a_t|, |b_t| \leq 1$ for $t = 0,\ldots,T$, then the product $\Delta_{\op H} \cdot \min \{ |\psi|^2_0,  |\psi_T|^2\} $ of the spectral gap $\Delta_{\op H} = E_1 - E_0$ and the minimum endpoint overlap is $\BigO(T^{-2})$.

[node distance = 14mm, text height = 1.5ex, text depth = .25ex]
(5) at (0,0) 5;
(4) at (2,0) 4;
(1) at (4,1) 1;
(3) at (4,-1) 3;
(2) at (6,0) 2;
[->] (1) to[in=135,out=0] node[above] $\op U_1$ (2);
[->] (2) to[in=0,out=-135] node[below,xshift=8] $\op U_2$ (3);
[->] (3) to[in=-45,out=180] node[below,xshift=-3] $\op U_3$ (4);
[->] (4) to[in=180,out=45] node[above,xshift=-3] $\1_d$ (1);
[->] (4) – node[above] $\1_d$ (5);

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 $\op U_1, \op U_2,\op U_3\in\mathrm{SU}(\field C^d)$, and $\1_d$ everywhere else—we call the graph a unitary labeled graph (ULG). Every edge $(a,b)$ with unitary $\op U_{ab}$ is translated into a transition term $\op h_{ab}:=\sum_i(\ket a\ket i-\ket b\otimes \op U_{ab}\ket i)(\mathrm{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 $\op U_3\op U_2\op U_1$—equals the identity $\1_d$, the circuit Hamiltonian built from these transition terms $\op H_G:=\sum_{(a,b)\in G}\op h_{ab}$ is unitarily equivalent to $\Delta\otimes\1_d$, where $\Delta$ is the graph Laplacian of the underlying graph $G$, as in <ref>.

Can this limitation for tridiagonal clock Hamiltonians be overcome using a clock that contains branches and loops?  In <cit.> 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 <ref>.   In this work we also consider generalized ULGs with weights along the vertices and edges, i.e. general Hermitian matrices, extending the graph Laplacian case that was analyzed in <cit.>. Given a Hamiltonian with the decomposition $\op H = \sum_{i,j \in \mathcal{B}} H_{ij} \ketbra{i}{j}$ in a particular basis, the generalized ULGs based on $\op H$ will have the form

\Hprop = \sum_{i,j\in \mathcal{B}} H_{ij} \ketbra{i}{j} \otimes \op 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 $\op H_{\textrm{prop}}$ based on a Hamiltonian $\op H$, a generalization of the standard argument shows that there will be a unitary transformation $\op W$ such that $\op W^\dagger \Hprop \op W = \op H \otimes \1$.

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.

Suppose $\op H_{\textrm{prop}} = \sum_{i,j \in \mathcal{B}} H_{ij} \ketbra{i}{j} \otimes \op U_{ij}$ describes a generalized ULG, and $\op H_{\textrm{in}}:= \sum_{i\in V_{\textrm{in}}} \ketbra i\otimes \Pi_{\textrm{in},i}$ and $\op H_{\textrm{in}}:= \sum_{i\in V_{\textrm{out}}} \ketbra i\otimes \Pi_{\textrm{out},i}$ are input and output projectors.  If $\op H_{\textrm{prop}}$ has $k\geq \min \left \{|V_{\textrm{in}}|,|V_{\textrm{out}}| \right\}  + 1$ excited eigenvalues of energy at most $R$, then the UNSAT penalty satisfies $E\left(\op H_{\textrm{in}} + \op H_{\textrm{prop}} + \op H_{\textrm{prop}} \right)  \leq R$.

This follows because the $k$ excited states can be used to form a superposition $\ket\phi$ with zero amplitude on $k-1$ sites.  This superposition will have $\bra \phi \op H_{\textrm{prop}}\ket\phi \leq R$, and if the amplitudes are zero on all the input (output) penalties, then $ \bra{\phi}\left(\op H_{\textrm{in}} + \op H_{\textrm{prop}} + \op H_{\textrm{prop}} \right) \ket{\phi} = \bra\phi \op H_{\textrm{prop}}\ket\phi \leq 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 $\op H$, we further define the notion of diameter with respect to particular basis $\mathcal{B}$, which is defined to be the smallest power of $\op H$ needed to connect any two basis elements:

\diam_{\mathcal{B}} \op H :=\max_{u,v \in \mathcal{B}} \min \left \{k \in \field N : \bra u \op H^k \ket v \neq 0\right \}.

The ground state $\ket\psi$ of $\op H$ defines a probability distribution $\pi(x) := |\braket{x}{\psi}|^2$ for $x \in \mathcal{B}$.  Let $\pi_\mathrm{min} := \min_{x \in \mathcal{B}} \pi(x)$ and define the spectral gap to be $\Delta_{\op H} = \lambda_1 - \lambda_{\min}$.
This allows us to derive a bound for Hermitian matrices which relates the ground state probability distribution $\pi$ and the matrix diameter to the spectral gap, generalizing a known bound for graph Laplacians <cit.>.

Let $\op H$, $\mathcal{B}$, $\pi$ and $\Delta_{\op H}$ be as defined above. Then

\[
\Delta_{\op H} \leq \frac{\|\op H\|}{2} \left( \frac{\log(2/\pi_{\min})} {\diam_{\mathcal{B}}\op H}\right)^2.
\]

Since the diameter is at least $T$ under the optimal compilation assumption, obtaining a spectral gap that scales like $T^{-2 + \epsilon}$ for some $\epsilon > 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.

§.§ Related Work

The notion of modifying the weights in Feynman's circuit Hamiltonian goes back to at least 1985, when Peres <cit.> 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 <cit.> derived a limitation on improving the spectral gap of circuit Hamiltonians by applying the lower bound on the Gover search problem.  In <cit.>, the authors go beyond unitary circuit include certain projective measurements $\{\Pi,\1-\Pi\}$ (ones whose outcome probabilities are independent of all valid input state at that computational step).

More recently,  have presented a compilation of several results on modified circuit Hamiltonians <cit.>.  Most of these results are distinct from results in this work, with the exception of <ref> which was discovered by us independently
around the same time <cit.>.

Another aspect of <cit.> and the present work that can be compared are that both works make an improvement to idling the computation efficiently.   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.

§ NON-UNIFORM CIRCUIT HISTORIES FOR IMPROVING THE UNSAT PENALTY

§.§ Analysis of Modified Feynman Hamiltonians

Proof of <ref>.
Since $\op W$ is a linear operator the calculations we need to check for <ref> are the same as in the standard unweighted case <cit.>.
As a reminder,

\[
\op W^\dagger \op W  = \sum_{t,t'=0}^T \Big(\proj t \otimes (\op U_1^\dagger \cdots \op U_t^\dagger)\Big)\Big(\proj{t'} \otimes (\op U_1\cdots \op U_{t'}) \Big) = \sum_{t=0}^T \proj t \otimes \1  = \1,
\]

\[
\op W^\dagger(\ketbra{t+1}{t}\otimes  \op U_{t+1})\op W  = \ketbra{t+1}{t} \otimes (\op U_1^\dagger \cdots \op U_{t+1}^\dagger) \op U_{t+1} (\op U_t\cdots \op U_1)  = \ketbra{t+1}{t} \otimes \1,
\]

and so the claim of <ref> follows by linearity.

Proof of <ref>.
Kitaev's geometrical lemma provides the starting point for the lower bound on the UNSAT penalty given in  <ref>.

Let $\op A,\op B\ge0$ be positive semi-definite operators, both with a zero eigenspace, and such that $\ker \op A\cap\ker \op B=\{0\}$.
Denote with $\lnz(\op A),\lnz(\op B)$ the minimal non-zero eigenvalue of $\op A$ and $\op B$, respectively.

\begin{equation}
\op A+\op B \ge \min\{\lnz(\op A),\lnz(\op B)\}\times 2\sin^2\frac\theta2,\label{eq:kit}
\end{equation}

where $\theta$ is the angle between the kernels of $\op A$ and $\op B$.

For us, $\op A=\Hin + \Hout$, and $\op B=\Hprop$,  and in this section we use the freedom to shift the energy in <ref> to set $E(\Hprop) = 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 $\Hprop$ itself is positive semi-definite).
Denote the projector onto the kernel of the penalty terms $\op A$ with  $\Pi_\mathrm{pen}:=\ketbra 0\otimes\Pin^\perp+\ketbra T\otimes\Pout^\perp+\sum_{t=2}^{T-1}\ketbra t\otimes\1$.
Denote with $\op U=\op U_T\cdots \op U_1$ the entire encoded quantum circuit.
We first want to bound the angle $\theta$ between the kernels of the propagation and penalty Hamiltonians<cit.>.

\begin{align*}
\cos^2\theta                                                 & =\max_{\substack{\ket{\xi}\in\ker \op A                                                                                \\
\ket{\eta}\in\ker \op B}}|\braket{\xi}{\eta}|^2              &  \\
& =\max_{\substack{\ket{\xi}                                                                                \\
\ket{\eta}\in\ker \op B}}|\bra\eta\Pi_\text{pen}\ket{\xi}|^2 &  \\
& \overset*=\max_{\ket{\eta}\in\ker \op B}\bra\eta\Pi_\text{pen}\ket{\eta}                                                                                \\
& =\max_{\ket\eta\in\ker \op B}\bra\eta \op W^\dagger( \op W\Pi_\text{pen}
\op U^\dagger) \op W\ket{\eta}                                                                                \\
& =\max_{\ket{\eta'}\in\ker \op W\op B \op W^\dagger}\bra{\eta'}\left(\ketbra 0\otimes\Pin^\perp+\ketbra T\otimes \op U\Pout^\perp \op U^\dagger+\sum_{t=2}^{T-1}\ketbra t\otimes\1\right)\ket{\eta'} \\
& =\max_{\ket{\phi}}\sum_{s=1}^T\psi_s^*\psi_s\bra s\bra\phi\left(\ketbra 0\otimes\Pin^\perp+\ketbra T\otimes \op U\Pout^\perp \op U^\dagger+\sum_{t=2}^{T-1}\ketbra t\otimes\1\right)\ket t\ket\phi  \\
& =\max_{\ket{\phi}}\bra\phi(\abs{\psi_0^2}\Pin^\perp+\abs{\psi_T^2} \op U\Pout^\perp \op U^\dagger)\ket\phi + 1-\abs{\psi_0^2}-\abs{\psi_T^2},
\end{align*}

where we have saturated Cauchy-Schwartz in the third line $(*)$.
To bound the first inner product, we observe that if $\psi_0^2\ge\psi_T^2$, picking $\ket{\phi}\in\ker\Pin$ gives the bound

\begin{equation*}
\max_{\ket{\phi}}\bra\phi(\pi_0\Pin^\perp+\pi_T \op U\Pout^\perp \op U^\dagger)\ket\phi \le \pi_0 + \pi_T\cos\vartheta, \end{equation*}

where $\vartheta$ is the angle between $\supp \Pin$ and $\supp \op U\Pout \op U^\dagger$.
This angle can be lower-bounded by the acceptance probability of the circuit:

\begin{equation*}
\cos^2\vartheta = \hspace{-1.8cm}\max_{\subalign{\hspace{2cm}\ket\eta&\in\supp \Pin\\\ket\xi&\in\supp \op U\Pout \op U^\dagger}}\hspace{-.5cm} |\braket{\eta}{\xi}|^2 \le \hspace{-1.2cm}\max_{\subalign{\hspace{1.4cm}\ket\eta&\in\supp \Pin\\\ket\xi&\in\supp \Pout}} |\bra{\eta}\op U\ket{\xi}|^2 \le \epsilon.
\end{equation*}

Similarly, if $\psi_0^2<\psi_T^2$, one can show an upper bound of $\pi_0\cos\vartheta + \pi_T$.
We thus obtain an overall upper bound

\begin{align*}
\cos^2\theta & \le \max\{\pi_0,\pi_T\} + \min\{\pi_0,\pi_T\}\sqrt\epsilon + 1 - \pi_0 - \pi_T \\ & \le 1  - \min\{\pi_0,\pi_T\}(1-\sqrt\epsilon).
\end{align*}

In Kitaev's lemma, we thus obtain a lower bound

\begin{equation*}
2\sin^2\frac\theta2 \ge 2\times\frac{1-\cos^2\theta}{8\cos^2\theta} \ge \frac14\min\{\pi_0,\pi_T\}(1-\sqrt\epsilon),
\end{equation*}

and the claim follows.

§.§ Metropolis Hamiltonians with Target Ground State Distributions

In this section we prove <ref>.
We assume the reader has some familiarity with Markov chain transition matrices; an introduction can e.g. be found in <cit.>.

Proof of <ref>.
Given a probability distribution $\pi$ with support everywhere on its domain $\mathcal{S}= \{0,\ldots,T\}$, let $\op P$ be the Markov chain with Metropolis transition probabilities defined on $\mathcal{S}$,

\begin{equation}
\op P_{t,t+1} = \frac{1}{4} \min\left\{1,\frac{\pi_{t+1}}{\pi_t}\right \} \quad , \quad \op P_{t,t-1}  = \frac{1}{4}\min\left\{1,\frac{\pi_{t-1}}{\pi_t}\right \} \quad \op P_{t,t} = 1 - \op P_{t,t+1} - \op P_{t,t-1}\label{eq:MetropolisTransitionProbabilities}
\end{equation}

for all $i \in \mathcal{S}$ (setting the expressions $\op P_{0,-1}$ and $\op P_{T,T+1}$ to zero) and $\op P_{t,t'} = 0$ for all $t,t'\in \mathcal{S}$ with $|t-t'| > 1$.
The choice of coefficient $1/4$ implies $\op P_{t,t} \geq 1/2$ for all $t$ and so $\op P$ is positive semi-definite.
The principal left eigenvector of this transition matrix $\op P := \sum_{t,t' \in \mathcal{S}} \op P_{t,t'}\ketbra{t}{t'}$ is $\bra\pi = \sum_{t} \pi_t \bra t$, and while $\op P$ is not a symmetric matrix, there is a well known similarity transformation that relates $\op P$ to a symmetric matrix, given by

\[
\op A:= \sum_{t,t' \in \mathcal{S}}\pi_t^{1/2} \pi_{t'}^{-1/2} \op P_{t,t'}\ketbra{t}{t'}.
\]

The two matrices are related by the fact that if $\bra{v_0}, \cdots, \bra{v_T}$ are the left eigenvectors of $\op P$ with eigenvalues $\lambda_0 = 1 \geq \lambda_1 \geq , \ldots , \geq \lambda_T\geq 0$, then $\ket{w_i} := \sum_ {t\in \mathcal{S}} \braket{v_i}{t} \braket{t}{v_0}^{-1/2} \; \ket t$ satisfies $A \ket{w_i} = \lambda_i \ket{w_i}$.
Therefore $\op A$ has the same eigenvalues as $\op P$, and in particular it has largest eigenvalue 1 corresponding to the eigenvector $\ket{w_0}$ with components satisfying $\braket{t}{w_0} = \braket{t}{v_0}^{1/2} = \sqrt{\pi_t}$.
Therefore $\op H = \1 - \op A$ is a nonnegative Hermitian matrix with ground state that has energy zero and components $\sqrt{\pi_t}$ in the time register basis, as claimed.

Markov chain spectral gaps.
Substantial efforts been devoted to characterizing spectral gaps of Markov chains.
A particularly fruitful characterization procedes by defining a quantity called the conductance,

\[
\Phi := \min_{S \subseteq \Omega} \frac{Q(S,S^c)}{\min\{\pi(S),\pi(S^c)\}} \quad , \quad Q(S,S^c) := \sum_{x \in S , y \in S^c } \pi(x) P(x,y)
\]

which determines the spectral gap within a quadratic factor,

\begin{equation}
\frac{\Phi^2}{2} \leq \Delta_{\op P} \leq 2 \Phi.
\label{eq:cheeger}
\end{equation}

The lower bound in <ref> is known as Cheeger's inequality, and it was initially discovered in the analysis of manifolds <cit.> before being adapted to the setting of Markov chains <cit.>.
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.

§.§ Explicit Construction of an $\Omega(T^{-2})$ UNSAT Penalty Circuit Hamiltonian

Proof of <ref>.
In this section let $\Hprop$ be the Metropolis Hamiltonian from <ref> corresponding to the probability distribution

\[
\pi_0 = \pi_T = \frac{1}{4} \quad \textrm{and} \quad \pi_t = \frac{1}{2(T-1)} \quad \textrm{for} \quad t = 1,\ldots,T-1.
\]

A few low energy eigenstates of $\Hprop$ are illustrated in <ref>.
Keeping with tradition <cit.>, we exhibit $\Hprop$ as a $T+1$ by $T+1$ matrix in the clock register basis,

\begin{equation}
\label{eq:hammatrix} \Hprop = \dfrac12
\parenMatrixstack{
\dfrac{1}{T -1}             & - \dfrac{1}{\sqrt{2 T - 2}} & 0              &                & \cdots         &                           & 0                         \\
- \dfrac{1}{\sqrt{2 T - 2}} & 1                           & - \dfrac{1}{2} & 0              &                &                           &                           \\
0                           & - \dfrac{1}{2}              & 1              & \ddots         & \ddots         &                           & \vdots                    \\
& 0                           & \ddots         & \ddots         & \ddots         & 0                         &  \\
\vdots                      &                             & \ddots         & \ddots         & 1              & - \dfrac{1}{2}            & 0                         \\
&                             &                & 0              & - \dfrac{1}{2} & 1                         & - \dfrac{1}{\sqrt{2T -2}} \\
0                           &                             & \cdots         &                & 0              & - \dfrac{1}{\sqrt{2T -2}} & \dfrac{1}{T - 1}
\end{equation}

Since $\pi_0$ and $\pi_T$ are $\Omega(1)$ it only remains to be checked that the spectral gap $\Delta_{\Hprop}$ of the clock Hamiltonian is $\Omega(T^{-2})$.  The spectral gap between the lowest two eigenvalues of $\Hprop$ is equal to the spectral gap between 1 and the second largest eigenvalue of the Metropolis transition matrix $\op P$, so we can apply Cheeger's inequality <ref> to $\pi$ and $\op P$.

The goal is to show that every subset $S$ of $\{0,\ldots,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 $\op P_{0,1} = (8T - 8)^{-1}$ so $\Phi(S)$ is $\Omega(T^{-1})$, with similar statements holding for $S = \{T\}$ and $S = \{0,T\}$.
Now if $S \subseteq \{1,\ldots,T-1\}$ is non-empty there must be at least one $t \in \{1,\ldots,T-1\} $ such that there is a $t \in S^c$ with $\op P_{t,t'} \geq 1/4$, and since $\pi_t = (2T -2)^{-1}$, this shows that $\Phi(S)$ is $\Omega(T^{-1})$ in this case as well.

Therefore $\Delta_{\op P}$ is $\Omega(T^{-2})$ by <ref>, and so $\Delta_{\Hprop} = \Omega(T^{-2})$ as well.  Using <ref> this concludes the proof of <ref>.

§ 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 <ref> yields a lower bound on the time needed for universal AQC using modified Feynman Hamiltonians to simulate the circuit model.

Low energy eigenstates of (a) the standard circuit-to-Hamiltonian construction and (b) the Metropolis Hamiltonian corresponding to the distribution with $\pi_0,\pi_T = 1/4$ that is used in this section.

The standard version of universal AQC is based on $\Hprop$ as given in <ref>, together with

\[
\Hinit := \ketbra 0 \otimes \1 =
\begin{pmatrix}
0                       & 0      & \multicolumn{2}{c}{\cdots} & 0                       \\
0                       & 1      & \ddots            &        & \multirow{2}{*}{\vdots} \\
\multirow{2}{*}{\vdots} & \ddots & \ddots            & \ddots &  \\
&        & \ddots            & 1      & 0                       \\
0                       & \multicolumn{2}{c}{\cdots} & 0      & 1
\end{pmatrix}
\otimes \1.
\]

The goal in universal AQC is to prepare the ground state of $\Hprop$ by continuously varying a Hamiltonian $\op H(s)$ that depends on an adiabatic parameter $0 \leq s \leq 1$.
First, when $s = 0$, the system is initialized in the ground state of $\op H(0) := \Hinit$, 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 $\op H(1) := \Hprop$.
Defining $\|\dot{\op H}\| = \max_s \|\dd \op H / \dd s\|$ and $\Delta = \min_s \Delta_{\op H}(s)$, an often used condition
for preparing the ground state of $\Hprop$ is for the total evolution time to satisfy $t_\textrm{adiabatic} = \Theta(\|\dot{\op H}\| \Delta^{-2})$ (see <cit.> for a review of rigorous adiabatic theorems).

This time scale was shown <cit.> to be bounded by $\poly(n)$ for the linear interpolation schedule, i.e.

\begin{equation}\label{eq:standardAdiabatic}
\op H(s) = (1-s) \Hinit + s \Hprop,
\end{equation}

where specifically $\Delta = \Omega(T^{-2})$ and $\|\dot{\op H}\| = O(1)$ so that $t_\textrm{adiabatic} = \Theta(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 <ref> 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 $\Omega(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 $\op U_1,\ldots,\op U_T$ one adds $r$ additional identity gates $\op U_r = \op U_{r+1} = \ldots = \op U_{r+T} = \1$, so that measuring $t\in [T,r+T]$ suffices to project the computational register to be in the end of the computation.

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.

We want to point out that modified Feynman Hamiltonians, together with the Metropolis Hamiltonian construction of <ref>, open up a new set of trade-offs in universal adiabatic computation that may be relevant for practical implementations.
Specifically, let $\op H^*_\textrm{prop}$ be the Hamiltonian used in <ref>.  The $\Omega(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 $\delta \approx 1 $ with the final step of the computation by padding the system with identity gates requires a total of $\BigO(T/(1-\delta))$ clock qubits, however one can instead prepare the weighted history state with $\pi_T = \delta$ 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 <ref> now must scale like $\BigO(T^{-1})$, as seen in <ref>.
This is a reasonable trade off, however, since the total number of qubits is generally the limiting factor in most experiments.

Proof of <ref>.
Having seen that it can be advantageous to prepare the non-uniform history state ground state of $\op H^*_\textrm{prop}$, it remains to be shown that this can be done efficiently.  In <ref> we proved that $\Delta_{\op H^*_\textrm{prop}} = \Theta(T^{-2})$, just as the minimum gap for the standard construction is $\Delta_{\op H(s = 1)} = \Theta(T^{-2})$.
A numerical comparison of the spectral gaps of $\op H(s)$ in <ref> and of $(1-s)\Hinit + s \Hprop^*(s)$ can be found in <ref>, 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 $\op 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 modified linear interpolation schedule,

\begin{equation}\label{eq:modifiedAdiabatic}
\op H^*(s) = \op H_0 + s A \op H^*_\textnormal{prop}.
\end{equation}

Choosing $A = T^4$ and an $\Omega(1)$ spectral gap for $0 \leq s \leq 1$, the standard estimate of the adiabatic run time $\Omega(\|\dot{\op H}\| \Delta_{\op H}^{-2})$ is then $\Omega(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 $\tilde{\op H}_\textnormal{final} = \op H^*_\textnormal{prop} + A^{-1} \op H_0$, and if $\{\ket{\psi_k^*}\}_{k = 0}^T$ and $\{E_k^*\}_{k = 0}^T$ denote the eigenstates and corresponding eigenvalues of $\op H^*_\textrm{prop}$, then, to first order in $A^{-1}$, the perturbed ground state $\ket{\tilde{\psi}}$ satisfies

\[
\| \ket{\tilde{\psi} } - \ket{ \psi^*_0} \|_1  = A^{-1} \sum_{k = 1}^T \frac{|\bra{ \psi_0 }\Hinit \ket{ \psi_k} |}{E^*_k - E^*_0}.
\]

Using the fact that $E^*_k - E^*_0 \geq \Delta_{\Hprop^*}$ and $\|\Hinit\| = 1$ this implies

\[
A^{-1} \sum_{k = 1}^T \frac{|\bra{ \psi_0 }\Hinit \ket{ \psi_k} |}{E^*_k - E^*_0}  \leq  A^{-1} \Delta_{\op H^*_\textrm{prop}}^{-1} \sum_{k = 1}^T |\bra{ \psi^*_0 }\Hinit \ket{ \psi^*_k} |  =\BigO(A^{-1} \Delta_{\op H^*_\textrm{prop}} ^{-1} T).
\]

Since $A = T^4$ we have $\|\ket{\tilde{\psi}} - \ket{\psi^*_0} \|_1 = 1 - \BigO(T^{-1})$, as claimed.

To see that $\op H^*(s)$ in <ref> has $\Delta_{\op H^*(s)} = \Omega(1)$ for all $s$, first note that $\Delta_{\op 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, \ldots, s_L = 1$, with a uniform step size $s_{i+1} = s_i + L^{-1}$.
Since $\op H^*(s_{i+1}) = \op H^*(s_i) + \left(\op H^*(s_{i+1}) - \op H^*(s_i)\right)$ and since $\op H^*(s_{i+1}) - \op H^*(s_i) = \Hprop^*$ 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) \geq 1$.
Next we apply the variational method with a trial state $\ket\phi$ equal to the ground state of $\Hprop^*$, to see that $\bra{ \phi} \op H^*(s) \ket{ \phi} = \bra{ \phi } \op H_0 \ket{ \phi} = 3/4$, and so $\Delta_{\op H^*(s)} \geq 1/4$ for all $s$.

§ TIGHTNESS OF THE GEOMETRICAL LEMMA FOR THE UNSAT PENALTY

§.§ A Tight Bound for the Clock Hamiltonian

In this section we prove that the UNSAT penalty of Kitaev's original construction is actually $\Omega(T^{-2})$, rather than the $\Omega(T^{-3})$ which can be shown using the geometrical lemma.  As noted in the introduction, this result was proven independently by  <cit.>, and appears to have been known for a while <cit.>.
We present a variant not reliant on Jordan's lemma in <ref>.

The Hamiltonian in Kitaev's original proof is $\Hkit := \Hprop + \ketbra 0\otimes\Pin + \ketbra T\otimes\Pout$, where $\Hprop$ is given by <ref> with $a_0=a_T=1$ and $a_t=2$ else, and $b_t=-1$ for all $t$.
We denote the encoded circuit with $\op U=\op U_T\cdots\op U_1$.
The corresponding clock- and computation registers then live on the Hilbert space $\mathcal H:=(\field C^{T+1})\otimes(\field C^2)^{\otimes 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 $\op H = \proj 0 + \Hclock + \proj T$.
Since $\op H$ is stoquastic, we can lower bound the ground state energy of $\op H$ by combining a suitable ansatz for the ground state with the following lemma.

Let $\op H$ be a Hermitian operator which is stoquastic in the $\ket{t}$ basis (meaning $\bra{ t} \op{H}\ket{t'} \leq 0$ for all $t \neq t'$).
Let $ E$ be its lowest eigenvalue.

\begin{equation}
E \ge \min_t \frac{\bra t \op H\ket\phi}{\braket{t}{\phi}}\label{eq:gap-lb}
\end{equation}

for any state $\ket\phi$ such that $\braket{t}{\phi} > 0$ for all $t$.

Noting that the state $\ket\phi$ in Lemma <ref> does not need to be normalized, define

\[
\ket\phi := \sum_{t = 0}^T \sin \left(\frac{\pi (t+1)}{T+2} \right ) \ket t .
\]

The bound <ref> can be evaluated using three cases.
The first case is $t = 0$, which yields

\begin{align*}
\frac{\bra 0 \op H\ket\phi}{\braket{ 0 }{ \phi}} & = \left [\sin\left(\frac{\pi}{T+2}\right) \right]^{-1} \left[2\sin\left (\frac{\pi}{T+2} \right ) - \sin\left (\frac{2 \pi}{T+2}\right ) \right] \\ &= 2 \left (1 - \cos \left (\frac{\pi}{T+2} \right) \right ) \\ &= \frac{\pi^2}{T^2} -  \BigO(T^{-3}) .
\end{align*}

The next case is $1 \leq t \leq T - 1$,

\begin{align*}
\frac{\bra t \op H\ket\phi}{\braket{ t }{ \phi}} & = \left [\sin\left(\frac{\pi(t+1)}{T+2}\right) \right]^{-1} \left [2  \sin\left(\frac{\pi(t+1)}{T+2}\right) -  \sin\left(\frac{\pi t}{T+2}\right) -  \sin\left(\frac{\pi(t+2)}{T+2}\right) \right ] \\ &=  2 \left (1 - \cos \left (\frac{\pi}{T+2} \right) \right ) \\ &= \frac{\pi^2}{T^2} -  \BigO(T^{-3}) .
\end{align*}

The final case is $t = T$,

\begin{align*}
\frac{\bra T \op H\ket\phi}{\braket{ T }{ \phi}} & = \left [\sin\left(\frac{\pi(T+1)}{T+2}\right) \right]^{-1}\left[2\sin\left (\frac{\pi(T+1)}{T+2} \right ) - \sin\left (\frac{\pi T}{T+2}\right ) \right] \\ &=2-\sin \left(\frac{\pi  T}{T+2}\right) \csc \left(\frac{\pi  (T+1)}{T+2}\right) \\ &= \frac{\pi^2}{T^2} -  \BigO(T^{-3})
\end{align*}

We have thus shown that $\bra{ t } \op H \ket{\phi} / \braket{ t }{ \phi }$ is $\Omega(T^{-2})$ for all $t$, and so applying  <ref> we can conclude that $E(\op H)$ is $\Omega(T^{-2})$.

§.§ A Tight Bound for the Full Circuit Hamiltonian

§.§.§ Block-Decomposition of the Full Circuit Hamiltonian

For the purpose of this discussion, we will assume that $\rank\Pin,\rank\Pout \ge d/2$; this is a natural assumption e.g. if $\Pin=\ketbra 1^{(1)}\otimes\1^{(2)}\otimes\cdots\otimes\1^{(d)}$ just penalizes the first qubit in a state $\ket1$.
Note that more penalized qubits generally increase the rank of $\Pin$ if we demand the penalties to be local operators (i.e. not something like $\ketbra1 \otimes \ketbra 0 \otimes \cdots$, but $\ketbra1\otimes\1 + \1\otimes\ketbra0\otimes\1 + \ldots$), so this assumption is justified.

We know that there exists a global unitary $\op W$ on $\mathcal H$ such that $\spec(\Hprop)=\spec(\op W^\dagger\Hprop\op W)=\spec(\Delta)$ up to multiplicities, where $\Delta$ is the Laplacian of a path graph of $T+1$ vertices:

\begin{equation*}
\Delta=
\begin{pmatrix}
1                       & -1 & 0                     & \multicolumn{2}{c}{\cdots} & 0                       \\
-1                      & 2  & -1                    &        &                   & \multirow{2}{*}{\vdots} \\
0                       & -1 & \ddots                & \ddots &                   &  \\
\multirow{2}{*}{\vdots} &    & \ddots                & \ddots & -1                & 0                       \\
&    &                       & -1     & 2                 & -1                      \\
0                       & \multicolumn{2}{c}{\cdots} & 0      & -1                & 1
\end{pmatrix}
\end{equation*}

\begin{equation}
\label{eq:hamKitaev} \op W^\dagger\Hkit\op W = \underbrace{\Delta\otimes\1 + \ketbra0\otimes\Pin}_{:=\op A} + \underbrace{\ketbra T\otimes\op U^\dagger\Pout\op U}_{:=\op B}.
\end{equation}

We choose to work in a basis where $\op A$ takes the form

\begin{equation}
\label{eq:A} \op A=\operatorname{diag}(\underbrace{\Delta',\ldots,\Delta'}_{\rank\Pin\ \text{times}},\Delta,\ldots,\Delta),
\end{equation}

and where $\Delta'=\Delta + \ketbra 0$.
Note that this is always possible: we simply re-order the computational register such that $$ penalizes the first $$ states.
Also note that $B=|T⟩⟨⊗|U^†U$ does not have a simple form in this basis (apart from having only a single entry \emph{within} each block in the time register basis, i.e.\ at the diagonal entry $|T⟩⟨$|).

If we naïvely try to diagonalize $\op B$, we will again mix up the nice block-diagonal form in <ref>; our goal is thus to find a unitary $\op V=\1_d\otimes(\op V'\oplus\op V'')$ which respects the block-diagonal structure of $\op A$, i.e. in particular leaves the upper left block invariant (which is automatically the case if $\dim\op V'\le\rank\Pin$).

While Jordan's original paper addresses the case of orthogonal transformations between subspaces, we can phrase it more suitable to our needs:

Let $\Pi_0$ and $\Pi_1$ be two Hermitian projectors in some Hilbert space .̋
Then there exists a decomposition of $\H$ into one- and two-dimensional subspaces $=̋⊕_i _̋i$, such that $_̋i$ is invariant under both $Π_0$ and $Π_1$, and such that $Π_j|__̋i≤1$ for all $j$ and $i$.
\end{lemma}
The proof is standard.
\Cref{lem:jordan} allows us to state the following corollary.
\begin{corollary}
\label{cor:tech}
Let $\Pi_0$ and $\Pi_1$ be projectors with $\rank \Pi_0=\rank \Pi_1=d/2$, and $\rank(\Pi_0+\Pi_1)=d$ is full rank.
Then there exists a unitary $\op V$ such that $\op V^\dagger\Pi_0\op Vr=\1_{d/2}\oplus0$.
\begin{equation*}
\op V^\dagger\Pi_1\op V=
\begin{pmatrix}
\op M_{aa} & \op M_{ab} \\ \op M_{ba} & \op M_{bb}
\end{pmatrix},
\end{equation*}
where each $d/2\times d/2$ block $\op M_{ij}$ is diagonal and full rank, and $\op M_{ab}=\op M_{ba}<0$.
\end{corollary}
\begin{proof}
Applying \cref{lem:jordan} to $\Pi_0$ and $\Pi_1$, we know that there exists a basis in which $\Pi_0$ is diagonal, and $\Pi_1=\bigoplus_i\op M_i$, where the $\op M_i$ are $2\times 2$ or $1\times 1$ Hermitian matrices.
Re-order the basis again such that $\Pi_0=\1_r\oplus0$ with $r=d/2$; we denote the unitary transformation from Jordan's lemma with this  reordering as $\op V$.

Under the same re-ordering, the matrix $\op V^\dagger\Pi_1\op V$ then necessarily has the form
\begin{equation}
\label{eq:matrix} \op V^\dagger\Pi_1\op V=
\begin{pmatrix}
\op M_{aa} & \op M_{ab} \\ \op M_{ba} & \op M_{bb}
\end{pmatrix}
\begin{tikzpicture}
[baseline] \node at (0,0) {$\begin{pmatrix}
\begin{array}
{cccc@{\hskip 8mm}cccc} \lambda_1 & 0         & \cdots & 0         & \xi_1  & 0      & \cdots & 0      \\
0                                 & \lambda_2 & \ddots & \vdots    & 0      & \xi_2  & \ddots & \vdots \\
\vdots                            & \ddots    & \ddots & 0         & \vdots & \ddots & \ddots & 0      \\
0                                 & \cdots    & 0      & \lambda_r & 0      & \cdots & 0      & \xi_r  \\[5mm]
\xi_1^*                           & 0         & \cdots & 0         & \mu_1  & 0      & \cdots & 0      \\
0                                 & \xi_2^*   & \ddots & \vdots    & 0      & \mu_2  & \ddots & \vdots \\
\vdots                            & \ddots    & \ddots & 0         & \vdots & \ddots & \ddots & 0      \\
0                                 & \cdots    & 0      & \xi_r^*   & 0      & \cdots & 0      & \mu_r
\end{array} \end{pmatrix}$};
\draw[dashed,gray] (3.1,0) -- (-3.1,0) (0,-2.4) -- (0,2.4);
\end{tikzpicture}
\end{equation}
A further global phase transformation (adjoining with a diagonal unitary, which leaves $\Pi_0$ invariant) allows us to assume that the $\xi_i=-|\xi_i|$, and the claim follows.
\end{proof}

We still need to show that the resulting Hamiltonian is in particular a graph Laplacian connecting the $T$\textsuperscript{th} entry in every block of $Δ$ in \cref{eq:A} with the $T$\textsuperscript{th} entry in at least one block of $Δ'$, 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.

\begin{lemma}
\label{lem:fullrank}
Let $\op U$ encode a \no instance.
Then $\Pin+\op U^\dagger\Pout\op U$ has full rank.
\end{lemma}
\begin{proof}
It is easy to see that if $\ker(\Pin+\op U^\dagger\Pout\op U)\neq0$, there would be a state that can be accepted with perfect probability---contradicting the assumption that $\op U$ encodes a \no instance.
\end{proof}

\begin{figure}[t]
\centering
\newcommand{\ux}{1.4 cm}
\begin{tikzpicture}
\matrix (magic) [
matrix of math nodes,
nodes = {
minimum size = \ux
left delimiter=(,
right delimiter=),
ampersand replacement=\&
\Delta \&  \&  \& \& \& \&\& \\
\& \Delta \& \&  \& \& \&\&  \\
\&  \& \Delta \& \& \& \&\&  \\
\& \& \& \Delta \& \& \& \&  \\
\& \& \& \& \Delta \& \&\&   \\
\& \& \&\& \& \Delta  \&     \\
\& \& \&\& \& \& \Delta \&   \\
\& \& \&\& \& \& \&\Delta    \\
\begin{scope}[
\foreach \i in {1,...,7} {
\draw[draw=black!20] (\i, 0) -- (\i, 8) (0, \i) -- (8, \i);
\draw (0, 4) -- (4, 4) -- (4, 8) (4, 0) -- (4, 4) -- (8, 4);

\foreach \i in {1,...,4} {
\node[scale=.66,blue] at (\i-1+.07, \i-1+.1) {$1$};

\node[scale=.66,red] at (\i -.1, \i -.1) {$\lambda_{\i}$};
\node[scale=.66,red] at (\i + 4 -.1, \i + 4 -.1) {$\mu_{\i}$};
\node[scale=.66,red] at (\i -.2, \i + 4 -.1) {$-|\xi_{\i}|$};
\node[scale=.66,red] at (\i + 4 -.2, \i -.1) {$-|\xi_{\i}|$};

\draw[red!40] (\i, \i - .1) -- (\i + 4 - .4, \i - .1) (\i + 4 - .1, \i) -- (\i + 4 - .1, \i + 4 - .2);
\draw[red!40] (\i - .1, \i) -- (\i - .1, \i + 4 - .2) (\i, \i + 4 - .1) -- (\i + 4 - .2, \i + 4 - .1);

\draw[->|] (-.5,.3) -- (-.5,0);
\draw[->|] (-.5,.7) -- (-.5,1);
\node at (-.5,.5) {$T$};
\draw[->|] (-.8,3.8) -- (-.8,0);
\draw[->|] (-.8,4.2) -- (-.8,8);
\node at (-.8, 4) {$d$ blocks};
\draw[->|] (8.5,1.6) -- (8.5,0);
\draw[->|] (8.5,2.4) -- (8.5,4);
\node at (8.5 + .3, 2) {\shortstack[l]{$\rank\Pin$\\blocks}};
\end{scope}
\end{tikzpicture}
\caption{Sketch of matrix $(\1\otimes\op V)^\dagger(\Delta\otimes\1 + \ketbra1\otimes\Pin +\ketbra T\otimes M)(\1\otimes\op V)$.}
\label{fig:matrix}
\end{figure}

This technical machinery allows us to prove \cref{theo:kitaev} in the next section.

\subsubsection{An $\Omega(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 $()=Ω(T^-2)$.
This will allow us to prove \cref{theo:kitaev}.
\paragraph{Proof of \cref{theo:kitaev}.}
Since the circuit is a \no-instance, there exists a minimal acceptance probability for any (valid) input $|x⟩∈$, which we denote with $ϵ$.
By \cref{lem:fullrank}, we know that we can apply \cref{cor:tech} to $$ and $U^†U$;  the unitary transformation bringing the latter into a form \cref{eq:matrix} while leaving $=⊕0$ we will denote with $V$.

Now perform this similarity transform on \cref{eq:hamKitaev}, i.e.
\begin{equation*}
(\1\otimes\op V^\dagger)\op W^\dagger\Hkit\op W(\1\otimes\op V)= \Delta\otimes 1+\proj 0\otimes (\1\oplus 0)+\proj T\otimes (\op V^\dagger\op U^\dagger\Pout\op U\op V).
\end{equation*}
The resulting matrix is depicted in \cref{fig:matrix}.
Since $U$ encodes a quantum circuit, we can immediately calculate the magnitudes of the $λ_i,μ_i$ and $ξ_i$'s (see \cref{eq:matrix,fig:matrix} as a reference).

\begin{enumerate}
\item If $\ket x\in\field C^d$, then $\bra x\op U^\dagger\Pout\op U\ket x=\|\Pout\op U\ket x\|^2$ is the probability that the circuit $\op U$ rejects input $\ket x$.
\item If $\ket x\in\ker\Pin$---i.e.\ for the $\op M_{bb}$ block---$\bra x\op U^\dagger\Pout\op U\ket x\ge1-\epsilon$.
Otherwise we have no non-trivial lower bound.
\item Assuming $\dim\supp\Pout=d/2$ (discard the rest), we can thus immediately conclude that each matrix block
\begin{equation*}
\op P_i =
\begin{pmatrix}
\lambda_i & -|\xi_i| \\ -|\xi_i| & \mu_i
\end{pmatrix}
\end{equation*}
is of $\rank\op P_i=1$ with $1\ge\mu_i\ge 1-\epsilon$.
\item Since the set of eigenvalues of a matrix is unique, we could continue diagonalizing $\op V^\dagger\Pout\op V$ by further diagonalizing each block $\op P_i$ separately; the result would be the same overall matrix as if we had diagonalized $\Pout$ in one step.
Since $\Pout$ is a psd projector, we thus know that each of the $\op P_i$ has to be a psd projector, and we can conclude
\begin{equation*}
\op P_i =
\begin{pmatrix}
\eta_i^2\mu_i & -\eta_i\mu_i \\ -\eta_i\mu_i & \mu_i
\end{pmatrix}
\end{equation*} for some $\eta_i:=\lambda_i/\mu_i\ge0$.
Then $1=\tr\op P_i=\mu_i(1+\eta_i^2) \ge (1-\epsilon)(1+\eta_i^2)$, and thus
\begin{equation*}
\eta_i \le \sqrt{\frac{1}{1-\epsilon}-1} = \sqrt{\frac{\epsilon}{1-\epsilon}} \le \sqrt{\frac\epsilon2},
\end{equation*}
and therefore $\lambda_i =\eta_i^2\mu_i \le \epsilon\mu_i/2 \le \epsilon/2$, and $|\xi_i|=\eta_i\mu_i \le \sqrt{\epsilon/2}$.
\item From $\mu_i\le1$, one can obtain a trivial bound $1\le1+\eta_i^2$, and thus obviously $\lambda_i\ge0$.
\end{enumerate}

\noindent
What remains to be analyzed is the spectrum of each of the pairs of blocks in \cref{fig:matrix}, i.e.\ blocks of the form $Δ+Δ'+$ matrix $P_i$ spread to the submatrix indexed by $T,2T$; more precisely, each block will have twice the size of $Δ$, and we can write it as a stoquastic matrix on $C^2⊗C^T+1$:
\begin{equation}
\label{eq:stoq-double-delta}
\op S = (\ketbra 0 + \ketbra 1)\otimes\Delta + \ketbra 0\otimes\ketbra 0 + \underbrace{\mu\left[\ketbra 1 + \eta^2 \ketbra 0 - \eta (\ketbra{0}{1}  +\ketbra{1}{0})\right]}_{=:\op L}\otimes\ketbra T,
\end{equation}
where $μ≥1-ϵ$ and $η≤√(ϵ/2)$.
For e.g.\ $S=8$ and reversing the second half of the time register (i.e.\ reversing the basis from $T$ to $2T$), this matrix looks like
\begin{equation*}
\op S_8=
\begin{pmatrix}
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 & \mu\eta ^2+1 & -\mu\eta & 0  & 0  & 0  \\ 0  & 0  & 0  &   -\mu\eta   &  1+\mu   & -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
\end{pmatrix}
\end{equation*}
Using a variational argument with the state
\begin{equation*}
\ket\phi:=\sum_{i=1}^T\sin\left(\frac{\pi i}{2T}\right)(\ket i + \ket{i+T})
\end{equation*}
and \cref{lem:lb}, we can explicitly show that $S=Ω(T^-2)$, independent of $μ$ and $η$.
The bound can be evaluated using five cases, which we summarize below.
\begin{align*}
\intertext{$t=1$:}
\left(2 \sin \left(\frac{\pi }{2 T}\right)-\sin \left(\frac{\pi }{T}\right)\right) \csc \left(\frac{\pi }{2 T}\right) & =\frac{\pi ^2}{4 T^2}+O(T^{-3})                                                       \\ \intertext{$1< t\le T-1$ and $T+1<t<T$:}
4 \sin ^2\left(\frac{\pi }{4 T}\right)                                                                                & =\frac{\pi ^2}{4 T^2}+O(T^{-3})                                                       \\ \intertext{$t=T$:}
\eta ^2 \mu -\eta  \mu  \sin \left(\frac{\pi }{2 T}\right)-\cos \left(\frac{\pi }{2 T}\right)+1                       & =\eta ^2 \mu -\frac{\pi  \eta  \mu }{2 T}+\frac{\pi ^2}{8 T^2}+O(T^{-3})              \\ \intertext{$t=T+1$:}
\mu -\eta  \mu  \csc \left(\frac{\pi }{2 T}\right)-2 \cos \left(\frac{\pi }{2 T}\right)+1                             & =-\frac{2 T (\eta  \mu )}{\pi }+(\mu -1)-\frac{\pi  \eta  \mu }{12 T}+\frac{\pi ^2}{4
T^2}+O(T^{-3})                                                                                \\ \intertext{$t=2T$:}
1-\sin \left(\frac{\pi  (T-1)}{2 T}\right)                                                                            & =\frac{\pi ^2}{8 T^2}+O(T^{-3})
\end{align*}
The claim of \cref{theo:kitaev} follows.
For convenience, we further collect the findings regarding the block matrix decomposition of the full circuit Hamiltonian given in the proof of \cref{theo:kitaev} in the following lemma.
\begin{lemma}
Kitaev's construction can be block-decomposed as $\Hkit=\bigoplus \op S_i$, where each block $\op S_i$ has the form given in \cref{eq:stoq-double-delta}.
The ground state energy of each of these blocks is $\Omega(T^{-2})$, and thus $E_p(\Hkit)=\Omega(T^{-2})$.
\end{lemma}

\section{Limitations on Further Improvement}\label{sec:limitations}
\subsection{Linear Clock Registers with Endpoint Penalties}\label{sec:limitation-linear}
The proof of \cref{theo:tridiag} 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 \cite{aharonov2008adiabatic} and the complexity of stoquastic Hamiltonians~\cite{bravyi2006merlin,bravyi2009complexity}.
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.

\paragraph{Proof of \cref{theo:tridiag}.}
In this section we continue with the notation of \cref{eq:ham}, 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$.
Define  $G := (-H)/(1-E)$ to be a shifted and rescaled version of $H$ which is designed to satisfy $G |ψ⟩ = |ψ⟩$, where $|ψ⟩$ labels the ground state of $H$.
For all $t,t'∈{0,…,T}$, define
\[
\op P_{t,t'} :=
\begin{cases}
\psi_{t'} \op G_{t,t'} \psi_{t}^{-1} & \text{if $\psi_t \neq 0$ and $\psi_{t'} \neq 0$}, \\
0                                    & \text{otherwise}.
\end{cases}
\]
In the following lemma we will show that the $P_t,t'$ 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'$ 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$, 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 \cref{eq:clockham}, we state the following lemma.
\begin{lemma}
\label{lem:unfrustrated} If $\psi_0 \neq 0$, $\psi_T \neq 0$, and $b_t \neq 0$ for $t = 0,\ldots,T$, then $\psi_t \neq 0$ for $t = 1,\ldots,T-1$ and $\op P_{t,t+1}  =\psi_{t+1} \op G_{t,t+1} \psi_t^{-1} \geq 0$ for all $t \in \{0,\ldots,T-1\}$.
\end{lemma}
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 \cref{theo:tridiag}l. Similarly, if $b_t' = 0$ for some $t'$, then  $|ψ^⊥⟩ := ∑_t=0^T ψ^⊥_t |t⟩$ defined by
\begin{equation}
\label{eq:perp} \psi^\perp_t :=
\begin{dcases}
\phantom{+}\frac{\psi_t}{\psi^2([0,t'])}       & 0 \leq t \leq t'  \\
-\frac{\psi_t}{\psi^2([t'+1,T])}  & t' < t \leq T - 1
\end{dcases}
\end{equation}
satisfies $⟨ ψ^⊥|ψ⟩ = 0$ and $H |ψ^⊥⟩ = E|ψ^⊥⟩$, which implies $Δ_H = 0$---so again  \cref{theo:tridiag} holds in this case\footnote{Note that the same idea behind \cref{eq:perp} can be used to upper bound the spectral gap by the minimum of $\pi_t \pi_{t+1}$ over all $t\in \{0,\ldots,T-1\}$, such that $\psi^2([0,t'])$ and $\psi^2([t'+1,T])$ are both $\Omega(1)$.}.

Now turning to the proof of Lemma \cref{lem:unfrustrated}.
From $H |ψ⟩ = E |ψ⟩$ we have that
\begin{align}
& a_{0}\psi_0 + b_{0}\psi_1 = E \psi_0, \label{eq:left-amplitude}                                                                       \\
& b^*_{i-1}\psi_{i-1} + a_i \psi_i +  b_i\psi_{i+1} = E \psi_i \quad \text{for } i = 1,\ldots,T-1\text{, and} \label{eq:mid-amplitudes} \\
& a_{T} \psi_{T} + b^*_{T-1} \psi_{T-1} = E \psi_{T}. \label{eq:right-amplitudes}
\end{align}
Since $P_t,t' = 0$ when $|t - t'| > 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 ≠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
\[
\psi_t b^*_{t} \psi_{t+1}^{-1} = \left(\frac{|\psi_t|}{|\psi_{t+1}|} \right)^2 \frac{\psi^*_{t+1}}{\psi^*_t} b^*_t =  \left(\frac{|\psi_t|}{|\psi_{t+1}|} \right)^2 \left(\psi_{t+1}b_t\psi_t^{-1}  \right)^*.
\]

Rearranging \cref{eq:left-amplitude} 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 \cref{eq:mid-amplitudes} is minimized when $ψ_tb_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 \cref{eq:mid-amplitudes} will be achieved when $ψ_t+1b_tψ^-1_t$ is negative as well.
Using the fact that $ψ_t ≠0$ from the inductive hypothesis, we may express \cref{eq:mid-amplitudes} as
\[
b^*_{t-1}\frac{\psi_{t-1}}{\psi_t} +  b_{t} \frac{\psi_{t+1}}{\psi_i} = E - a_{t}  \quad \text{for } t = 1,\ldots,t.
\]
Since $E - a_t$ is real and $ψ_t-1 b^*_t-1 ψ^-1_t = (|ψ_t-1|/|ψ_t|)^2 (ψ_tb_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 \cref{eq:mid-amplitudes} 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 \cref{eq:right-amplitudes}, which completes the proof of \cref{lem:unfrustrated}.

Having established that $P_t,t' ≥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:
\begin{enumerate}
\item $\op P$ is a stochastic matrix, i.e.\ $\sum_{t' = 0}^T \op P_{t,t'} = 1$ for all $t \in \{0,\ldots,T\}$, and therefore it can be regarded as the transition matrix of a discrete time Markov chain.
\item The largest eigenvalue of $\op P$ is equal to 1 and it corresponds to the unique principal eigenvector $\ket{\pi} = \sum_{t=0}^T |\psi_t|^2 \ket{t}$.
The probability distribution $\pi_t := \braket{ t }{\pi}$ is the stationary distribution of the corresponding Markov chain.
\item The Markov chain defined by $\op P$ is reversible with respect to its stationary distribution,
\begin{equation*}
\pi_t \op P_{t,t'} = \braket{t'}{\psi} \braket{\psi}{t} \op G_{t,t'} = \left (\braket{t}{\psi} \braket{\psi}{t'} \op G^*_{t,t'}\right )^* = \pi_t' \op P_{t',t}.
\end{equation*}
\item If $\ket{\psi_0} , \ket{\psi_1} , \ldots , \ket{\psi_T}$ are the eigenvectors of $\op H$ with eigenvalues $E_0 < E_1 \leq \ldots \leq E_T$, then $\ket{\phi_k} := \sum_{x\in \Omega} \braket{\psi_0}{x} \braket{x}{\psi_k} \ket x$ is an eigenvector of $\op P$ with eigenvalue $( 1 - E_k)/(1- E_0)$.
Since this is the complete list of eigenvectors of $\op P$, we have shown that the spectral gaps of $\op H$ and $\op P$ satisfy
\begin{equation}
\Delta_{\op P} = (1-E) \Delta_{\op H}.
\label{eq:gap-relate}
\end{equation}
\end{enumerate}

The relation \cref{eq:gap-relate} 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 \cref{eq:cheeger}: if the overlap of the stationary distribution with the end points $|0⟩$ and $|T⟩$ is constant, we can immediately conclude that the conductance $Φ$ is $(T^-1)$, by the fact that the stationary distribution is normalized; this implies $Δ_H=(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~\cite{Chen2013}, which we state here as a lemma.
\begin{lemma}
If $\op P$ is a birth and death chain with stationary distribution $\pi$, then the spectral gap $\Delta_{\op P}$ satisfies
\begin{equation}
\frac{1}{2 \ell} \leq \Delta_{\op P} \leq \frac{4}{\ell} \label{eq:ell-gap}
\end{equation}
\begin{equation}
\ell := \max \left \{ \max_{j : j \leq i'} \sum_{k = j}^{i' -1} \frac{\pi([0,j]}{\pi(k)\op P_{k,k+1}} , \max_{j: j > i'} \sum_{k=i'+1}^j \frac{\pi([j,T])}{\pi(k)\op P_{k,k-1}} \right\}\label{eq:bd-lemma}
\end{equation}
where $i'$ satisfies $\pi([0,i'])\geq 1/2$ and $\pi([i',n]) \geq 1/2$.
\end{lemma}
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$, \cref{eq:bd-lemma} becomes

\begin{equation*}
\ell \geq  \psi^2_0\sum_{t = 1}^{T/2 - 1} \frac{1}{\psi^2_t }.
\end{equation*}
Applying the inequality of the arithmetic and geometric means yields
\[
\sum_{t = 1}^{T/2 - 1} \frac{1}{\psi^2_t }  \geq \left( \frac{T}{2} - 1 \right) \left(\psi_1^2 \cdots \psi^2_{T/2-1}  \right)^{-1/k} \geq \left( \frac{T}{2} - 1 \right)^2 \left(\sum_{t=1}^{T/2-1} \psi_t  \right)^{-1},
\]
and so $ℓ=Ω(ψ^2_0 T^2)$.
Together with \cref{eq:ell-gap} we have that the spectral gap $Δ_P$ is $(ℓ^-1)$, and it follows that $Δ_H ·ψ^2_0=(T^-2)$, as claimed.

Finally, we note that \cref{theo:tridiag} 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 \cref{eq:ham}.
First, the problem of upper bounding the spectral gap of universal adiabatic constructions was addressed before~\cite{ganti2013gap} by combining the quantum lower bound for unstructured search with the technique of spectral gap amplification.
This previous work found a general $(T^-1)$ bound (where the tilde hides logarithmic factors) on the spectral gap of \emph{any} adiabatic Hamiltonian, an $(T^-2)$ gap for any frustration-free adiabatic Hamiltonian, and finally an $(T^-2)$ bound on the spectral gap of modified Feynman Hamiltonians of the form \cref{eq:ham} when the weights near the endpoints satisfy a reasonable assumption for any adiabatic computation.
Our \cref{theo:tridiag} corroborates this last result by showing a tight $(T^-2)$ upper bound on the spectral gap and the minimum overlap of the weighted history state with either endpoint of the computation.

\subsection{Diameter Bounds for simple generalized ULGs}\label{sec:sc-ulg-diameter-bound}
Following \cref{theo:tridiag}, 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 \cref{theo:tridiag} 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 \cite{Bausch2016} (as described in \cref{sec:limitationsIntro}) and a family of circuits $(C_i)_i∈N$, 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.

This family of circuits can be implemented by a family of standard circuit Hamiltonians ${H_i}_i ∈ℕ$, 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:
\begin{equation*}
\includegraphics{figures/graph-1}
\end{equation*}
Now assume there exists another Hamiltonian $H'$ with at least one path between $t=1$ and $t=T_i$, but of shorter length $T'<T_i$, e.g.
\begin{equation*}
\includegraphics{figures/graph-2}
\end{equation*}
\newcommand{\Hrest}{\op H_\textnormal{rest}}
Since $(1,…,T_i,T'-1,…,2',1)$ forms a loop, the assumption that the ULG is simple implies $(U_1,2…U_T_i -1,T_i)(U_T' -1, T'-2…U_2',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 \cref{sec:non-simple-ulg}.

\subsection{A Clock Diameter Bound}\label{sec:diameter-bound}
In \cref{sec:sc-ulg-diameter-bound}, 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 $ϵ=(promise gap)$.

But if we know that there have to be straight sections of length $T$ within any graph, how does this graph \emph{diameter} correspond to the spectral gap of the clock Hamiltonian?
And can we combine this with the case of non-simple ULGs (\cref{sec:non-simple-ulg})?
By \cref{lem:geo}, we know that $E_p(ϵ,T)≤E((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.

\paragraph{Proof of \cref{th:diam}.}
The most general such clock is an arbitrary Hermitian matrix, and we develop a diameter bound on it following \cite{KelnerMITLecturenotes2009}. Let $H$ be Hermitian on $C^T$, and---as in \cref{sec:limitation-linear}---define
\begin{equation}\label{eq:G}
\op G:=(\op H-\lmin)/(\| \op H \| - \lmin).
\end{equation}
Then $(G)⊂[0,1]$.
For two states $|u⟩,|v⟩∈C^T$, we define their \emph{distance} under $G$ as
\[
\dist_{\op G}(\ket u,\ket v):=\min\{ k : \bra u \op G^k \ket v \neq 0\}
\]
if it exists, and we set $_G(|u⟩,|v⟩)=∞$ otherwise; this is the case e.g.\ if $G$ is block-diagonal, and $|u⟩$ and $|v⟩$ are vectors with support completely contained in disjoint blocks.

The reason for calling it a \emph{distance} is obvious from the equality
\begin{equation*}
\dist_{\op G}(\ket u,\ket v)=\min\left\{d: \bra u\prod_{i=1}^d\left(\sum_{jk}\proj j\op G\proj k\right)\ket v\neq 0\right\},
\end{equation*}
i.e.\ it catches the minimum number of nonzero jumps under $G$ necessary to reach some overlap between $|u⟩$ and $|v⟩$.
The \emph{diameter} of $G$ is then defined as
\[
\diam\op G:=\max_u\min_v\{\dist_{\op G}(\ket u,\ket v)\}.
\]
It is clear that $G=H$.

If we use the spectral decomposition $G=∑_iλ_iψ_i$ and some polynomial $p$, then for any states $|u⟩$ and $|v⟩$, we have \newcommand{\pmin}{\pi_{\mathrm{min}}}
\begin{align*}
|\bra u p(\op G)\ket v| & =\left|\sum_i p(\lambda_i)\braket{u}{\psi_i}\braket{\psi_i}{v}\right| \\ &\ge p(1)|\pi_{u,v}| + \left|\sum_{i\ge 2}p(\lambda_i) u_i \bar v_i\right|\\ &\ge p(1)|\pi_{u,v}| - \max_{i\ge 2}p(\lambda_i)\sum_{i\ge 2}|u_i||v_i|\\ &\ge p(1)|\pi_{u,v}| - \max_{i\ge 2}p(\lambda_i),
\end{align*}
where $π_u,v:=u_1v̅_1$, and $u_i:=⟨u|ψ_i⟩$, $v̅_i:=⟨ψ_i|v⟩$.

One can show that there exists a family of polynomials $p_k$ with $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
\begin{equation*}
2(1+\sqrt{2\Delta})^{-k}<\pi_{u,v} \quad\Leftrightarrow\quad -k\ln(1+\sqrt{2\Delta})<\ln\left(\frac{\pi_{u,v}}{2}\right) \quad\Leftrightarrow\quad k>\frac{\ln(2/\pi_{u,v})}{\ln(1+\sqrt{2\Delta}}.
\end{equation*}
For $x∈(0,1)$ we further have a uniform bound\footnote{This bound is tight up to a factor of $2\ln2$, which is reached at $x=1$.}\ \ of $ln(1+√(2x))≤(1+1/√(x))$, which yields a diameter bound of
\[
\diam\op G\le\left(1+\frac{1}{\sqrt{2\Delta}}\right)\ln(2/\pi_{u,v}).
\]
This inequality still depends on our choice of states $|u⟩$ and $|v⟩$.
Assuming that $=min_i|⟨i|ψ_1⟩|^2$ denotes the minimum ground state overlap with any basis state $|i⟩$, we know that $|π_u,v|^2≥$.
If we further assume $>0$, then the diameter bound reads
\[
\diam\op G\le\left(1+\frac{1}{\sqrt{2\Delta}}\right)\ln(2/\pmin).
\]

What about the case where $=0$?
This would mean that there is at least one state $|x⟩$ for which $⟨x|ψ_1⟩=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 $>0$, and otherwise we restrict $|u⟩, |v⟩∈ψ_1$.
For the degenerate case we block-diagonalize $G$ and regard each such block separately.

To formalize this, we define a variant of the diameter which captures the ground space connectivity:
\begin{equation*}
\diam' \op G:=\max_{u\in\supp\proj{\psi_1}}\min_{v\in\supp\proj{\psi_1}}\{\dist_{\op G}(\ket u,\ket v)\}.
\end{equation*}
The diameter bound then reads
\begin{equation}\label{eq:diameter-bound}
\diam'\op G\le\left(1+\frac{1}{\sqrt{2\Delta}}\right)\ln(2/\pmin'),
\end{equation}
where $'=min_i∈ψ_1|⟨i|ψ_1⟩|^2$.
Using the fact from \cref{sec:sc-ulg-diameter-bound} 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$, \cref{eq:G}, we obtain \cref{th:diam}.

\subsection{Frustrated ULGs}\label{sec:non-simple-ulg}
In \cref{sec:sc-ulg-diameter-bound} 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.
\begin{equation*}
\end{equation*}
In case that $U=σ_x$, we can immediately write down the ULG Hamiltonian as
\begin{equation*}
\op H_G=
\begin{pmatrix}
2  & 0  & -1 & -1 \\
0  & 2  & -1 & -1 \\
-1 & -1 & 2  & 0  \\
-1 & -1 & 0  & 2
\end{pmatrix}
\end{equation*}
As we can see, this Hamiltonian by itself is already a graph Laplacian for the following graph:
\begin{equation*}
\includegraphics[]{figures/ulg-2}
\end{equation*}
However, our goal is to reduce the number of edges; if we instead work in the $|±⟩$-eigenbasis of the off-diagonal blocks of $H_G$, $+σ_x$, then
\begin{equation*}
\op H_G\sim
\begin{pmatrix}
2 & 0 & -2 & 0 \\
0 & 2 & 0  & 0 \\
2 & 0 & 2  & 0 \\
0 & 0 & 0  & 2
\end{pmatrix}
\end{equation*}
which in turn corresponds to the graph
\begin{equation*}
\includegraphics[]{figures/ulg-2b}
\end{equation*}
but such that the vertices $a_-$ and $b_-$ carry an \emph{extra penalty} of $2$.

This argument also works for more general $U$: labelling the eigenvalues of $+U$ with $λ_1,…,λ_n$, we have
\begin{equation}\label{eq:non-simple-ulg-2}
\op H_G\sim
\begin{pmatrix}
2\1 & \diag(\lambda_1,\ldots,\lambda_n) \\ \diag(\bar{\lambda_1},\ldots,\bar{\lambda_n}) & 2\1
\end{pmatrix}
\end{equation}
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
\begin{equation*}
\op P=\sum_{i=1}^n (2-|\lambda_i|)\proj{\lambda_i},
\end{equation*}
where as in \cref{eq:non-simple-ulg-2} the $|λ_i|≤U+≤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 \emph{is} the case, then one can analyse the UNSAT penalty of each component separately.
As can be seen in \cref{def:unsat}, the \no-\yes energy difference stems from $H_FK$---the Hamiltonian that includes in- and output penalties; $E()$ 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.

\section{Outlook}\label{sec: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 \emph{relative} energy penalties that are not simply made larger by e.g.\ increasing the overall norm of the Hamiltonian.

\paragraph{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 $(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 $(T)$ local terms of bounded norm---which may be of a form more general than \cref{eq:ham}---to achieve an UNSAT penalty that is independent of the length of the computation?

\paragraph{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 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 $(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 encoded 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$.

\paragraph{Constant relative UNSAT penalty.}
A circuit Hamiltonian with $O(m)$ local terms of bounded norm, where $m = (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.

\vspace{.5cm}
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 construction 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.

\section{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 provided 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 \cref{sec:jordan-proof,sec:direct-proof}.
\newpage
% $ biblatex auxiliary file $
% $ biblatex bbl format version 2.8 $
% Do not modify the above lines!
% This is an auxiliary file used by the 'biblatex' package.
% This file may safely be deleted. It will be recreated as
% required.
\begingroup
\makeatletter
\<EMAIL_ADDRESS>{Missing 'biblatex' package}
{The bibliography requires the 'biblatex' package.}
\aftergroup\endinput}
\endgroup

\sortlist[entry]{none/global/}
\entry{Kitaev2002}{incollection}{}
\name{author}{3}{}{%
given={Alexei\bibnamedelima Yu.},
giveni={A\bibinitperiod\bibinitdelim Y\bibinitperiod},
given={Mikhail\bibnamedelima N.},
giveni={M\bibinitperiod\bibinitdelim N\bibinitperiod},
\list{publisher}{1}{%
{Springer New York}%
\strng{namehash}{KAYSAVMN1}
\strng{fullhash}{KAYSAVMN1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{Quantum Information}
\verb{doi}
\verb 10.1007/978-0-387-36944-0_13
\endverb
\field{pages}{203\bibrangedash 217}
\field{title}{{Classical and quantum computing}}
\list{location}{1}{%
{New York, NY}%
\field{annotation}{%
contains Kitaev's geometrical lemma on p. 147%
\field{year}{2002}
\endentry

\entry{Kempe2006}{article}{}
\name{author}{3}{}{%
\keyw{adiabatic,complete problems,local hamiltonian problem,quantum
\strng{namehash}{KJKARO1}
\strng{fullhash}{KJKARO1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1137/S0097539704445226
\endverb
\verb{eprint}
\verb quant-ph/0406180
\endverb
\field{issn}{0097-5397}
\field{number}{5}
\field{pages}{1070\bibrangedash 1097}
\field{title}{{The Complexity of the Local {H}amiltonian Problem}}
\verb{url}
\verb http://epubs.siam.org/doi/abs/10.1137/S0097539704445226 http://arxiv.
\verb org/abs/quant-ph/0406180
\endverb
\field{volume}{35}
\field{journaltitle}{SIAM Journal on Computing}
\field{eprinttype}{arXiv}
\field{year}{2006}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{Oliveira2008}{article}{}
\name{author}{2}{}{%
given={Barbara\bibnamedelima M.},
giveni={B\bibinitperiod\bibinitdelim M\bibinitperiod},
\strng{namehash}{ORTBM1}
\strng{fullhash}{ORTBM1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{eprint}
\verb quant-ph/0504050
\endverb
\field{pages}{1\bibrangedash 23}
\field{title}{{The complexity of quantum spin systems on a two-dimensional
square lattice}}
\verb{url}
\verb http://dl.acm.org/citation.cfm?id=2016987 http://arxiv.org/abs/quant-
\verb ph/0504050
\endverb
\field{journaltitle}{Quantum Information {\&} Computation}
\field{eprinttype}{arXiv}
\field{year}{2005}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{aharonov2008adiabatic}{article}{}
\name{author}{6}{}{%
family={Van\bibnamedelima Dam},
familyi={V\bibinitperiod\bibinitdelim D\bibinitperiod},
\list{publisher}{1}{%
\strng{namehash}{AD+1}
\strng{fullhash}{ADVDWKJLZLSRO1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1137/080734479
\endverb
\verb{eprint}
\verb quant-ph/0405098
\endverb
\field{number}{4}
\field{pages}{755\bibrangedash 787}
\field{title}{Adiabatic quantum computation is equivalent to standard
quantum computation}
\field{volume}{50}
\field{journaltitle}{SIAM review}
\field{eprinttype}{arXiv}
\field{year}{2008}
\endentry

\entry{biamonte2008realizable}{article}{}
\name{author}{2}{}{%
\list{publisher}{1}{%
\strng{namehash}{BJLP1}
\strng{fullhash}{BJLP1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1103/PhysRevA.78.012352
\endverb
\verb{eprint}
\verb 1311.3161
\endverb
\field{number}{1}
\field{pages}{012352}
\field{title}{Realizable {H}amiltonians for universal adiabatic quantum
\field{volume}{78}
\field{journaltitle}{Physical Review A}
\field{eprinttype}{arXiv}
\field{year}{2008}
\endentry

\entry{Aharonov2009}{article}{}
\name{author}{4}{}{%
\strng{namehash}{AD+1}
\strng{fullhash}{ADGDISKJ1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1007/s00220-008-0710-3
\endverb
\verb{eprint}
\verb 0705.4077
\endverb
\field{number}{1}
\field{pages}{41\bibrangedash 65}
\field{title}{{The power of quantum systems on a line}}
\verb{url}
\verb http://link.springer.com/article/10.1007/s00220-008-0710-3 http://arx
\verb iv.org/abs/0705.4077 http://dx.doi.org/10.1007/s00220-008-0710-3
\endverb
\field{volume}{287}
\field{journaltitle}{Communications in Mathematical Physics}
\field{eprinttype}{arXiv}
\field{year}{2009}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{cubitt2016complexity}{article}{}
\name{author}{2}{}{%
\list{publisher}{1}{%
\strng{namehash}{CTMA1}
\strng{fullhash}{CTMA1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1137/140998287
\endverb
\verb{eprint}
\verb 0704.1287
\endverb
\field{number}{2}
\field{pages}{268\bibrangedash 316}
\field{title}{Complexity classification of local {H}amiltonian problems}
\field{volume}{45}
\field{journaltitle}{SIAM Journal on Computing}
\field{eprinttype}{arXiv}
\field{year}{2016}
\endentry

\entry{aharonov2013guest}{article}{}
\name{author}{3}{}{%
\list{publisher}{1}{%
\strng{namehash}{ADAIVT1}
\strng{fullhash}{ADAIVT1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1145/2491533.2491549
\endverb
\field{number}{2}
\field{pages}{47\bibrangedash 79}
\field{title}{Guest column: the quantum {PCP} conjecture}
\field{volume}{44}
\field{journaltitle}{Acm SIGACT news}
\field{eprinttype}{arXiv}
\field{year}{2013}
\endentry

\entry{Feynman1986}{article}{}
\name{author}{1}{}{%
given={Richard\bibnamedelima P.},
giveni={R\bibinitperiod\bibinitdelim P\bibinitperiod},
\strng{namehash}{FRP1}
\strng{fullhash}{FRP1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{abstract}{%
The physical limitations, due to quantum mechanics, on the functioning of
computers are analyzed.%
\verb{doi}
\verb 10.1364/ON.11.2.000011
\endverb
\field{isbn}{0600050750}
\field{issn}{0098-907X}
\field{number}{2}
\field{pages}{11}
\field{title}{{Quantum Mechanical Computers}}
\verb{url}
\verb https://www.osapublishing.org/abstract.cfm?URI=on-11-2-11
\endverb
\field{volume}{11}
\field{journaltitle}{Optics News}
\field{annotation}{%
there is a Foundations of Physics paper with more details at
\field{year}{1985}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{Gottesman2009}{article}{}
\name{author}{2}{}{%
\strng{namehash}{GDIS1}
\strng{fullhash}{GDIS1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.4086/toc.2013.v009a002
\endverb
\verb{eprint}
\verb 0905.2419
\endverb
\field{issn}{1557-2862}
\field{number}{1}
\field{pages}{31\bibrangedash 116}
\field{title}{{The Quantum and Classical Complexity of Translationally
Invariant Tiling and Hamiltonian Problems}}
\field{volume}{9}
\field{journaltitle}{Theory of Computing}
\field{eprinttype}{arXiv}
\field{year}{2013}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{breuckmann2014space}{article}{}
\name{author}{2}{}{%
given={Nikolas\bibnamedelima P.},
giveni={N\bibinitperiod\bibinitdelim P\bibinitperiod},
given={Barbara\bibnamedelima M.},
giveni={B\bibinitperiod\bibinitdelim M\bibinitperiod},
\list{publisher}{1}{%
{IOP Publishing}%
\strng{namehash}{BNPTBM1}
\strng{fullhash}{BNPTBM1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1088/1751-8113/47/19/195304
\endverb
\verb{eprint}
\verb 1311.6101
\endverb
\field{issn}{1751-8113}
\field{number}{19}
\field{pages}{195304}
\field{title}{{Space-time circuit-to-Hamiltonian construction and its
\field{volume}{47}
\field{journaltitle}{Journal of Physics A: Mathematical and Theoretical}
\field{eprinttype}{arXiv}
\field{year}{2014}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{Hallgren2013}{article}{}
\name{author}{3}{}{%
\strng{namehash}{HSNDNS1}
\strng{fullhash}{HSNDNS1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{eprint}
\verb 1312.1469
\endverb
\field{number}{9{\&}10}
\field{pages}{28}
\field{title}{{The Local {H}amiltonian problem on a line with eight states
is {QMA}-complete}}
\field{volume}{13}
\field{journaltitle}{Quantum Information and Computation}
\field{eprinttype}{arXiv}
\field{year}{2013}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{NagajTalk}{misc}{}
\name{author}{1}{}{%
\strng{namehash}{ND1}
\strng{fullhash}{ND1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{Tick-tock {G}oes the {C}lock}
\verb{url}
\verb https://www.youtube.com/watch?v=ADPzjtt6V04
\endverb
\field{type}{Lecture at the Simons Institute}
\field{year}{2014}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{Bausch2016}{article}{}
\name{author}{3}{}{%
\strng{namehash}{BJCTOM1}
\strng{fullhash}{BJCTOM1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1007/s00023-017-0609-7
\endverb
\verb{eprint}
\verb 1605.01718
\endverb
\field{pages}{52}
\field{title}{{The Complexity of Translationally-Invariant Spin Chains with
Low Local Dimension}}
\verb{url}
\verb http://arxiv.org/abs/1605.01718
\endverb
\field{journaltitle}{Annales Henri Poincar{\'{e}}}
\field{eprinttype}{arXiv}
\field{year}{2017}
\endentry

\entry{Usher2017}{article}{}
\name{author}{3}{}{%
given={Matty\bibnamedelima J.},
giveni={M\bibinitperiod\bibinitdelim J\bibinitperiod},
given={Dan\bibnamedelima E.},
giveni={D\bibinitperiod\bibinitdelim E\bibinitperiod},
\strng{namehash}{UNHMJBDE1}
\strng{fullhash}{UNHMJBDE1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{abstract}{%
A central result in the study of Quantum Hamiltonian Complexity is that the
k-Local hamiltonian problem is QMA-complete. In that problem, we must decide
if the lowest eigenvalue of a Hamiltonian is bounded below some value, or
above another, promised one of these is true. Given the ground state of the
Hamiltonian, a quantum computer can determine this question, even if the
ground state itself may not be efficiently quantum preparable. Kitaev's proof
of QMA-completeness encodes a unitary quantum circuit in QMA into the ground
space of a Hamiltonian. However, we now have quantum computing models based
on measurement instead of unitary evolution, furthermore we can use
post-selected measurement as an additional computational tool. In this work,
we generalise Kitaev's construction to allow for non-unitary evolution
including post-selection. Furthermore, we consider a type of post-selection
under which the construction is consistent, which we call tame
post-selection. We consider the computational complexity consequences of this
construction and then consider how the probability of an event upon which we
are post-selecting affects the gap between the ground state energy and the
energy of the first excited state of its corresponding Hamiltonian. We
provide numerical evidence that the two are not immediately related, by
giving a family of circuits where the probability of an event upon which we
post-select is exponentially small, but the gap in the energy levels of the
Hamiltonian decreases as a polynomial.%
\verb{doi}
\verb 10.1103/PhysRevA.96.032321
\endverb
\verb{eprint}
\verb 1703.08118
\endverb
\field{issn}{2469-9926}
\field{number}{3}
\field{pages}{032321}
\field{title}{{Nonunitary quantum computation in the ground space of local
\verb{url}
\verb http://arxiv.org/abs/1703.08118 http://dx.doi.org/10.1103/PhysRevA.96
\verb .032321 https://link.aps.org/doi/10.1103/PhysRevA.96.032321
\endverb
\field{volume}{96}
\field{journaltitle}{Physical Review A}
\field{eprinttype}{arXiv}
\field{year}{2017}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{Caha2017}{inproceedings}{}
\name{author}{3}{}{%
\strng{namehash}{CLLZND1}
\strng{fullhash}{CLLZND1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{abstract}{%
We present a collection of results about the clock in Feynman's computer
construction and Kitaev's Local Hamiltonian problem. First, by analyzing the
spectra of quantum walks on a line with varying endpoint terms, we find a
better lower bound on the gap of the Feynman Hamiltonian, which translates
into a less strict promise gap requirement for the QMA-complete Local
Hamiltonian problem. We also translate this result into the language of
adiabatic quantum computation. Second, introducing an idling clock
construction with a large state space but fast Cesaro mixing, we provide a
way for achieving an arbitrarily high success probability of computation with
Feynman's computer with only a logarithmic increase in the number of clock
qubits. Finally, we tune and thus improve the costs (locality, gap scaling)
of implementing a (pulse) clock with a single excitation.%
\verb{eprint}
\verb 1712.07395
\endverb
\field{title}{{The Feynman-Kitaev computer's clock: bias, gaps, idling and
pulse tuning}}
\verb{url}
\verb http://arxiv.org/abs/1712.07395
\endverb
\field{eprinttype}{arXiv}
\field{year}{2017}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{Aharonov2009a}{inproceedings}{}
\name{author}{4}{}{%
\list{publisher}{1}{%
{ACM Press}%
\strng{namehash}{AD+1}
\strng{fullhash}{ADAILZVU1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{Proceedings of the 41st annual ACM symposium on Symposium
on theory of computing - STOC '09}
\verb{doi}
\verb 10.1145/1536414.1536472
\endverb
\field{isbn}{9781605585062}
\field{pages}{417}
\field{title}{{The detectability lemma and quantum gap amplification}}
\verb{url}
\verb http://portal.acm.org/citation.cfm?doid=1536414.1536472
\endverb
\list{location}{1}{%
{New York, New York, USA}%
\field{eprinttype}{arXiv}
\field{year}{2009}
\endentry

\entry{BauschThesis}{thesis}{}
\name{author}{1}{}{%
\strng{namehash}{BJ1}
\strng{fullhash}{BJ1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.17863/CAM.16755
\endverb
\field{title}{Quantum Stochastic Processes and Quantum Many-Body Physics}
\list{institution}{1}{%
{University of Cambridge}%
\field{type}{phdthesis}
\field{month}{10}
\field{year}{2017}
\endentry

\entry{KelnerMITLecturenotes2009}{misc}{}
\name{author}{1}{}{%
\strng{namehash}{KJ1}
\strng{fullhash}{KJ1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{note}{Fall 2009, Massachusetts Institute of Technology: MIT
OpenCourseWare, \url{https://ocw.mit.edu}.}
\field{title}{18.409, Topics in Theoretical Computer Science: An
Algorithmist's Toolkit}
\verb{url}
\verb https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-
\verb computer-science-an-algorithmists-toolkit-fall-2009
\endverb
\endentry

\entry{Peres1985}{article}{}
\name{author}{1}{}{%
\strng{namehash}{PA1}
\strng{fullhash}{PA1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1103/PhysRevA.32.3266
\endverb
\field{issn}{0556-2791}
\field{number}{6}
\field{pages}{3266\bibrangedash 3276}
\field{title}{{Reversible logic and quantum computers}}
\verb{url}
\verb https://link.aps.org/doi/10.1103/PhysRevA.32.3266
\endverb
\field{volume}{32}
\field{journaltitle}{Physical Review A}
\field{year}{1985}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{ganti2013gap}{article}{}
\name{author}{2}{}{%
\list{publisher}{1}{%
{World Scientific}%
\strng{namehash}{GASR1}
\strng{fullhash}{GASR1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1142/S0219749913500639
\endverb
\verb{eprint}
\verb 1307.4993
\endverb
\field{number}{07}
\field{pages}{1350063}
\field{title}{On the gap of {H}amiltonians for the adiabatic simulation of
quantum circuits}
\field{volume}{11}
\field{journaltitle}{International Journal of Quantum Information}
\field{eprinttype}{arXiv}
\field{year}{2013}
\endentry

\entry{CubittLectureNotes}{misc}{}
\name{author}{1}{}{%
\strng{namehash}{CT1}
\strng{fullhash}{CT1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{Lecture notes in {A}dvanced {Q}uantum {I}nformation {T}heory}
\verb{url}
\verb http://www.dr-qubit.org/Advanced_Quantum_Information_Theory_course.ht
\verb ml
\endverb
\field{year}{2015}
\endentry

\entry{levin2009markov}{book}{}
\name{author}{3}{}{%
given={David\bibnamedelima Asher},
giveni={D\bibinitperiod\bibinitdelim A\bibinitperiod},
given={Elizabeth\bibnamedelima Lee},
giveni={E\bibinitperiod\bibinitdelim L\bibinitperiod},
\list{publisher}{1}{%
{American Mathematical Soc.}%
\strng{namehash}{LDAPYWEL1}
\strng{fullhash}{LDAPYWEL1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{title}{Markov chains and mixing times}
\field{year}{2009}
\endentry

\entry{Cheeger1970}{incollection}{}
\name{author}{1}{}{%
\list{publisher}{1}{%
{Princeton Univ. Press, Princeton, N. J.}%
\strng{namehash}{CJ1}
\strng{fullhash}{CJ1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{Papers dedicated to Salomon Bochner (1969)}
\field{pages}{195–199}
\field{title}{A lower bound for the smallest eigenvalue of the {L}aplacian,
Problems in Analysis}
\field{year}{1970}
\endentry

\entry{sinclair1989approximate}{article}{}
\name{author}{2}{}{%
\list{publisher}{1}{%
\strng{namehash}{SAJM1}
\strng{fullhash}{SAJM1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1016/0890-5401(89)90067-9
\endverb
\field{number}{1}
\field{pages}{93\bibrangedash 133}
\field{title}{Approximate counting, uniform generation and rapidly mixing
{M}arkov chains}
\field{volume}{82}
\field{journaltitle}{Information and Computation}
\field{year}{1989}
\endentry

\entry{aharonov2002quantum}{misc}{}
\name{author}{2}{}{%
\strng{namehash}{ADNT1}
\strng{fullhash}{ADNT1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{eprint}
\verb quant-ph/0210077
\endverb
\field{title}{Quantum {NP}-a survey}
\field{eprinttype}{arXiv}
\field{year}{2002}
\endentry

\entry{albash2018adiabatic}{article}{}
\name{author}{2}{}{%
given={Daniel\bibnamedelima A.},
giveni={D\bibinitperiod\bibinitdelim A\bibinitperiod},
\list{publisher}{1}{%
{American Physical Society}%
\strng{namehash}{ATLDA1}
\strng{fullhash}{ATLDA1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1103/RevModPhys.90.015002
\endverb
\verb{eprint}
\verb 1611.04471
\endverb
\field{issue}{1}
\field{pages}{015002}
\field{title}{Adiabatic quantum computation}
\verb{url}
\verb https://link.aps.org/doi/10.1103/RevModPhys.90.015002
\endverb
\field{volume}{90}
\field{journaltitle}{Rev. Mod. Phys.}
\field{eprinttype}{arXiv}
\field{year}{2018}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{Farhi2011}{article}{}
\name{author}{5}{}{%
\strng{namehash}{FE+1}
\strng{fullhash}{FEGJGDGSSP1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{eprint}
\verb 1010.0009
\endverb
\field{number}{9--10}
\field{title}{{Unstructured Randomness, Small Gaps and Localization}}
\field{volume}{11}
\field{journaltitle}{Quantum Information {\&} Computation}
\field{eprinttype}{arXiv}
\field{year}{2011}
\warn{\item Invalid format of field 'month'}
\endentry

\entry{Jordan1875}{article}{}
\name{author}{1}{}{%
\strng{namehash}{JC1}
\strng{fullhash}{JC1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{issn}{0037-9484}
\field{pages}{103\bibrangedash 174}
\field{title}{{Essai sur la g{\'{e}}om{\'{e}}trie {\`{a}} n dimensions}}
\verb{url}
\verb https://eudml.org/doc/85325
\endverb
\field{volume}{3}
\field{journaltitle}{Bulletin de la Soci{\'{e}}t{\'{e}} math{\'{e}}matique
de France}
\field{year}{1875}
\endentry

\entry{bravyi2006merlin}{inproceedings}{}
\name{author}{3}{}{%
\strng{namehash}{BSBATB1}
\strng{fullhash}{BSBATB1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{eprint}
\verb quant-ph/0611021
\endverb
\field{title}{Merlin-{A}rthur games and stoquastic complexity}
\field{eprinttype}{arXiv}
\field{year}{2006}
\endentry

\entry{bravyi2009complexity}{article}{}
\name{author}{2}{}{%
\list{publisher}{1}{%
\strng{namehash}{BSTB1}
\strng{fullhash}{BSTB1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\verb{doi}
\verb 10.1137/08072689X
\endverb
\verb{eprint}
\verb 0806.1746
\endverb
\field{number}{4}
\field{pages}{1462\bibrangedash 1485}
\field{title}{Complexity of stoquastic frustration-free {H}amiltonians}
\field{volume}{39}
\field{journaltitle}{Siam journal on computing}
\field{eprinttype}{arXiv}
\field{year}{2009}
\endentry

\entry{Chen2013}{article}{}
\name{author}{2}{}{%
\keyw{1 partially supported by,2 partially supported by,and phrases,birth
and death chains,cutoff phenomenon,nsc grant nsc100-2115-m-009-003-my2,nsf
grant dms-1004771}
\strng{namehash}{CGYSCL1}
\strng{fullhash}{CGYSCL1}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{abstract}{%
For birth and death chains, we derive bounds on the spectral gap and mixing
time in terms of birth and death rates. Together with the results of Ding et
al. in 2010, this provides a criterion for the existence of a cutoff in terms
of the birth and death rates. A variety of illustrative examples are
\verb{eprint}
\verb 1304.4346
\endverb
\field{number}{1}
\field{pages}{293\bibrangedash 321}
\field{title}{{On the mixing time and spectral gap for birth and death
\verb{url}
\verb http://arxiv.org/abs/1304.4346
\endverb
\field{volume}{10}
\verb{file}
\verb :C$\backslash$:/Users/Johannes/AppData/Local/Mendeley Ltd./Mendeley D
\verb esktop/Downloaded/Chen, Saloff-Coste - 2013 - On the mixing time and
\verb spectral gap for birth and death chains.pdf:pdf
\endverb
\field{journaltitle}{ALEA Lat. Am. J. Probab. Math. Stat.}
\field{eprinttype}{arXiv}
\field{year}{2013}
\endentry
\endsortlist
\endinput

\newpage
\appendix
\addtocontents{toc}{\protect\setcounter{tocdepth}{1}}
\section{Appendix}
\subsection{An  $\Omega(T^{-2})$ Scaling from Padding with Identities}\label{sec:padding-ham}
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 \emph{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 $ℋ$.
Define a padded circuit Hamiltonian on $C^2T⊗ℋ$ as
\begin{align}
\op H & = \sum_{t=-T/2}^{0}(\proj t + \proj{t+1} - \ketbra{t+1}{t} - \ketbra{t}{t+1})\otimes\1 \\ &+ \sum_{t=0}^{T}(\proj t + \proj{t+1})\otimes\1 - \ketbra{t+1}{t}\otimes \op U_t - \ketbra{t}{t+1}\otimes \op U_t^\dagger \\ &+ \sum_{t=T}^{3T/2}(\proj t + \proj{t+1} - \ketbra{t+1}{t} - \ketbra{t}{t+1})\otimes\1.
\end{align}
The overall encoded circuit of this Hamiltonian is thus
\begin{equation*}
\underbrace{\1\cdots\1}_{T/2\text{\ times}} \op U_T\cdots \op U_1  \underbrace{\1\cdots\1}_{T/2\text{\ times}} =: \op U_{3T/2}'\cdots \op U_{-T/2}'.
\end{equation*}
The ground state of this unbiased clock construction is a uniform superposition over the history of the computation, i.e.\ $|Ψ⟩=1/√(2T)∑_t=-T/2^3T/2|t⟩⊗U_t'⋯U_-T/2'|ϕ⟩$.

For some input and output penalty $,$ acting on the circuit qubits, we define the padded penalty Hamiltonian as
\begin{equation}
\op P = \sum_{t=-T/2}^{0}\proj t\otimes\Pin + \sum_{t=T}^{3T/2}\proj t\otimes\Pout.
\end{equation}
Denote the projector onto the kernel of this penalty term with
\begin{equation*}
\Pi_\mathrm{pen}:= \sum_{t=-T/2}^0\proj t\otimes\Pin^\perp +\sum_{t=T}^{3T/2}\proj t\otimes\Pout^\perp +\sum_{t=1}^{T-1}\proj t\otimes\1.
\end{equation*}
Let $W$ be the usual diagonalizing operator for $H$.
We first bound the angle $θ$ between $P$ and $H$:
\begin{align*}
\cos^2\theta
% & = \max_{\substack{\ket{\xi}\in\ker \op P \\\ket{\eta}\in\ker \op H}}|\braket{\xi}{\eta}|^2 \\ &= \max_{\substack{\ket{\xi}\\\ket{\eta}\in\ker \op H}}|\bra\eta\Pi_\text{pen}\ket{\xi}|^2 \\ &= \max_{\ket{\eta}\in\ker \op H} \bra{\eta} \Pi_\text{pen} \ket{\eta} \\ &= \max_{\ket{\eta}\in\ker \op H} \bra{\eta} \op W^\dagger (\op W\Pi_\text{pen}\op W^\dagger) \op W\ket{\eta} \\
&= \max_{\ket{\eta'}\in\ker \op W\op H\op W^\dagger} \bra{\eta'} \left( \sum_{t=-T/2}^0\proj t\otimes\Pin^\perp +\sum_{t=T}^{3T/2}\proj t\otimes\Pout^\perp +\sum_{t=1}^{T-1}\proj t\otimes\1 \right)\ket{\eta'} \\
% &= \max_{\ket{\phi}} \sum_{s=-T/2}^{3T/2}\frac 1{2T} \bra s\bra \phi\left( \sum_{t=-T/2}^0\proj t\otimes\Pin^\perp +\sum_{t=T}^{3T/2}\proj t\otimes\Pout^\perp +\sum_{t=1}^{T-1}\proj t\otimes\1 \right) \ket s\ket\phi \\
&= \max_{\ket{\phi}} \frac 1{2T} \bra{\phi}\left( \sum_{t=-T/2}^0  \proj t\otimes\Pin^\perp +\sum_{t=T}^{3T/2}  \proj t\otimes\Pout^\perp +\sum_{t=1}^{T-1}  \proj t\otimes\1 \right) \ket{\phi} \\ &= \max_{\ket{\phi}} \frac 14 \bra{\phi} \Pi_\text{in} + \op U\Pi_\text{out} \op U^\dagger \ket{\phi} + \frac 12.
\end{align*}
The inner product is then bounded by the acceptance probability $ϵ$ of the circuit, i.e.
\begin{align*}
\max_{\ket{\phi}} \bra{\phi} \Pi_\text{in} + \op U\Pi_\text{out} \op U^\dagger \ket{\phi} \le + \cos\vartheta \le 1 + \epsilon.
\end{align*}
Overall, this gives a bound
\begin{equation}
\cos^2\theta \le \frac14(3 + \epsilon),
\end{equation}
which gives precisely the same UNSAT penalty as the un-padded version used in \cref{sec:theo1proof}.

\subsection{Proof of $\Omega(T^{-2})$ Scaling without Jordan's Lemma}\label{sec:direct-proof}
We start in \cref{sec:jordan-proof}, after \cref{eq:A}.
If our goal is to avoid using Jordan's lemma, we need the following technical result.
\begin{lemma}\label{lem:supertech}
Let $\Pi\in\field C^{d\times d}$ be a projector, and two sets of vectors $\{\ket{e_i} \}, \{\ket{f_i} \}$ which span $\field C^d$ such that
\begin{align*}
\braket{e_i}{e_j}=\braket{f_i}{f_j} & =\delta_{ij}       &  & (i)   \\
\braket{e_i}{f_j}                   & =0                 &  & (ii)  \\
\bra{e_i}\Pi\ket{e_j}               & \propto\delta_{ij} &  & (iii) \\
\bra{f_i}\Pi\ket{f_j}               & \propto\delta_{ij} &  & (iv)
\end{align*}
Then either:
\begin{enumerate}
\item For all $i$, $\bra{e_i}\Pi\ket{f_j}\neq 0$ for at most one $j$.
\item If $\bra{e_i}\Pi\ket{f_j}\neq 0$ and $\bra{e_i}\Pi\ket{f_{j'}}\neq 0$ for some $j'\neq j$, then necessarily $\bra{f_j}\Pi\ket{f_j}=\bra{f_{j'}}\Pi\ket{f_{j'}}$.
\end{enumerate}
\end{lemma}
\begin{proof}
First observe that $(i)$ and $(ii)$ imply that the set $\{\ket{e_i} \}\cup \{\ket{f_i} \}$ forms an orthonormal basis of $\field C^d$. For any $j$ for which
\begin{equation}\label{eq:supertech-1}
\bra{e_i}\Pi\ket{f_j}\neq 0,
\end{equation}
we can thus show
\begin{align*}
0 & \neq\bra{e_i}\Pi\ket{f_j}                                                                &  \\
& =\bra{e_i}\Pi\Pi\ket{f_j}                                                                &  & \text{since $\Pi$ is a projector}                                      \\
& =\bra{e_i}\Pi\left(\sum_k\ketbra{e_k} + \sum_l\ketbra{f_l} \right)\Pi\ket{f_j}           &  & \text{as the $\ket{e_i}$ and $\ket{f_i}$ form an ONB} \\
& =\bra{e_i}\Pi\ket{e_i}\bra{e_i}\Pi\ket{f_j} + \bra{e_i}\Pi\ket{f_j}\bra{f_j}\Pi\ket{f_j} &  & \text{by $(iii)$ and $(iv)$}\\
& =\bra{e_i}\Pi\ket{f_j}(\bra{e_i}\Pi\ket{e_i} + \bra{f_j}\Pi\ket{f_j}),                   &
\end{align*}
and thus $\bra{e_i}\Pi\ket{e_i} + \bra{f_j}\Pi\ket{f_j}=1$. If there exist two $j\neq j'$ for which \cref{eq:supertech-1} holds, then necessarily $\bra{f_j}\Pi\ket{f_j}=\bra{f_{j'}}\Pi\ket{f_{j'}}$.
\end{proof}

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 $$ 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 $$ by $Ω(T^-2)$.
\begin{lemma}\label{lem:tech}
Let $\op M\in\field C^{d\times d}$ be a projector. Then for any $1\le s< d$, there exists a block-diagonal unitary $\op V=\op V'\oplus\op V''$ with $\dim \op V'=s$ such that $\op D=\op V^\dagger\op M\op V$ is stoquastic. Furthermore, $\op V$ can be chosen such that---if we denote the rank of the upper-left $s\times s$ block with $r_a$ and the complementary lower-right block rank with $r_b$---$\op D_{ij}\neq 0$ if and only if
\begin{align*}
& i=j\land j\le r_a             && (i)\\
\text{or}\quad & s\le i=j\le s+r_b             && (ii) \\
\text{or}\quad & s\le j=s+i\le\min\{r_a,r_b\}  && (iii) \\
\text{or}\quad & s\le i=s+j\le\min\{r_a,r_b\}. && (iv)
\end{align*}
\end{lemma}
\begin{proof}
Let $r=\rank\op M$, and write $\op M=\sum_{i=1}^r\ketbra{m_i}$ as eigendecomposition with orthonormal vectors $\ket{m_i}$.  Split each of the eigenvectors $\ket{m_i}=:\ket{a_i}\oplus\ket{b_i}$, where $\dim\ket{a_i}=s$ (we abuse the direct sum notation here to mean simply dovetailing two vectors).  Then $\op M$ can be expressed as block-matrix:
\op M=\sum_{i=1}^r\ketbra{m_i}=:\sum_i\begin{pmatrix}
\ketbra{a_i} & \ketbra{a_i}{b_i} \\
\ketbra{b_i}{a_i} & \ketbra{b_i}
\end{pmatrix}
\op M_{aa} & \op M_{ab} \\
\op M_{ab}^\dagger & \op M_{bb}
\end{pmatrix}.
The matrix $\op M_{aa}$ is Hermitian since $\op M$ is. We can thus find a diagonalizing unitary $\op A:=\sum_{i=1}^s\ketbra{\alpha_i}{i}$, such that $\op A^\dagger\op M_{aa}\op A$ is diagonal, and similarly $\op B$ for $\op M_{bb}$; here the $\ket i$ just label the standard basis, and the $\ket{\alpha_i}$ an orthonormal eigenbasis of $\op A$.  We further pick $\op A$ and $\op 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 $\op V=\op A\oplus\op B$, we would immediately verify claims $(i)$ and $(ii)$.

It is, however, not obvious what $\op A^\dagger\op M_{ab}\op B$ looks like, so we need to do some more work. We calculate the matrix entries:
\begin{equation}\label{eq:tech-1}
\bra x\op A^\dagger\op M_{ab}\op B\ket y = \sum_{j=1}^s\braket{x}{j}\bra{\alpha_j}\sum_i\ketbra{a_i}{b_i} \sum_{k=1}^{d-s}\ket{\beta_k}\braket{k}{y} = \sum_{i}\braket{\alpha_x}{a_i}\braket{b_i}{\beta_y}.
\end{equation}
We expand $\ket{\alpha'_i}:=\ket{\alpha_i}\oplus\ket0$, and $\ket{\beta'_i}:=\ket0\oplus\ket{\beta_i}$, which allows us to apply \cref{lem:supertech} to $\op M$, $\{\ket{\alpha'_i} \}$ and $\{\ket{\beta'_i} \}$. Take some row $x$; if there is only one column index $y$ for which \cref{eq:tech-1}$\neq0$ we are done.  If, on the other hand, there are at least two $y\neq y'$ for which \cref{eq:tech-1} $\neq 0$, we can define a unitary $\op R$ via
\begin{align*}
\ket{\beta'_y} &\longmapsto \frac{1}{\sqrt{1+\gamma^2}}\left(\ket{\beta'_y} + \gamma\ket{\beta'_{y'}}\right)\\
\ket{\beta'_{y'}} &\longmapsto \frac{1}{\sqrt{1+\gamma^2}}\left(\ket{\beta'_y} - \gamma\ket{\beta'_{y'}}\right),
\end{align*}
where $\gamma=\bra{\alpha_x}\Pi\ket*{\beta'_y} / \bra{\alpha_x}\Pi\ket*{\beta'_{y'}}$.  It is then easy to verify that $\bra x(\op A\oplus\op B\op R)^\dagger\op M(\op A\oplus\op B\op R)\ket{y'}=0$, and because of the degeneracy $\bra y\op B^\dagger\op M_{bb}\op B\ket y=\bra {y'}\op B^\dagger\op M_{bb}\op B\ket{y'}$, $\op R^\dagger\op B^\dagger\op M\op B\op R$ 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 $\op V^\dagger\op M\op V$ with a diagonal matrix where each entry is of modulus 1, thus eliminating the different phases in the $\xi_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 $\op V$.

\noindent
After some reordering, the resulting matrix $\op V^\dagger\op M\op V$ has the form
\small
\begin{equation}\label{eq:matrix-alt}
\begin{tikzpicture}
[baseline] \node at (0,0) {$\begin{pmatrix}
\begin{array}{ccccccc@{\hskip 8mm}ccccccc}
\lambda_1 &     0     &   0    &    \cdots     & \cdots &   0    &   0    & -|\xi_1| &    0     &   0    &    \cdots    & \cdots &   0    &   0    \\
0     & \lambda_2 & \ddots &               &        &        &   0    &    0     & -|\xi_2| & \ddots &              &        &        &   0    \\
0     &  \ddots   & \ddots &    \ddots     &        &        & \vdots &    0     &  \ddots  & \ddots &    \ddots    &        &        & \vdots \\
\vdots   &           & \ddots & \lambda_{r_a} &   0    &        & \vdots &  \vdots  &          & \ddots & -|\xi_{r_o}| &   0    &        & \vdots \\
\vdots   &           &        &       0       &   0    & \ddots & \vdots &  \vdots  &          &        &      0       &   0    & \ddots & \vdots \\
0     &           &        &               & \ddots & \ddots &   0    &    0     &          &        &              & \ddots & \ddots &   0    \\
0     &     0     & \cdots &    \cdots     & \cdots &   0    &   0    &    0     &    0     & \cdots &    \cdots    & \cdots &   0    &   0    \\[5mm]
-|\xi_1|  &     0     &   0    &    \cdots     & \cdots &   0    &   0    &  \mu_1   &    0     &   0    &    \cdots    & \cdots &   0    &   0    \\
0     & -|\xi_2|  & \ddots &               &        &        &   0    &    0     &  \mu_2   & \ddots &              &        &        &   0    \\
0     &  \ddots   & \ddots &    \ddots     &        &        &        &    0     &  \ddots  & \ddots &    \ddots    &        &        & \vdots \\
\vdots   &           & \ddots & -|\xi_{r_o}|  &   0    &        &        &  \vdots  &          & \ddots &  \mu_{r_b}   &   0    &        & \vdots \\
\vdots   &           &        &       0       &   0    & \ddots &        &  \vdots  &          &        &      0       &   0    & \ddots & \vdots \\
0     &           &        &               & \ddots & \ddots &   0    &    0     &          &        &              & \ddots & \ddots &   0    \\
0     &     0     & \cdots &    \cdots     & \cdots &   0    &   0    &    0     &    0     & \cdots &    \cdots    & \cdots &   0    &   0
\end{array}
\end{pmatrix}$};
\draw[dashed,gray] (6.6,0) -- (-6.6,0) (0,-4.3) -- (0,4.4);
\end{tikzpicture}
\end{equation}
\normalsize
where $r_o:=\min\{r_a,r_b\}$, which finally satisfies claims $(i)-(iv)$. The claim of the lemma follows.
\end{proof}
One can then show by an application of \cref{lem:fullrank} that for a \no-instance, $r_o=r=d/2$.

The remaining argument follows as in \cref{sec:jordan-proof}.

\end{document}