Proof of efficient, parallelized, universal adiabatic quantum computation
Ari Mizel

 
 ]Proof of efficient, parallelized, universal adiabatic quantum computation

ari@arimizel.com
Laboratory for Physical Sciences, 8050 Greenmead Drive, College Park,
Maryland, USA 20740




We give a careful proof that a parallelized version of adiabatic quantum computation can efficiently simulate universal gate model quantum computation.  The proof specifies an explicit parameter-dependent Hamiltonian H(λ) that is based on ground state quantum computation <cit.>.  We treat both a 1-dimensional configuration in which qubits on a line undergo nearest neighbor 2-qubit gates and an all-to-all configuration in which every qubit undergoes 2-qubit gates with every other qubit in the system.

2015
 
 
 











[
    Ari Mizel
    December 30, 2023
=====================





§ INTRODUCTION


Investigating the physics of computation, researchers studied computing in a thermodynamically reversible fashion <cit.> and studied computing with a quantum mechanical system <cit.>.  In 1985, Feynman proposed a model <cit.> addressing both together – reversible classical computation with a quantum mechanical apparatus.  This paper formulated a “ballistic” version of quantum computing in which a time-dependent quantum system evolves from input state to output state in accordance with the dynamics imposed by a time-independent Hamiltonian.  At the end of his paper, Feynman mentioned the possibility of generalizing the model to permit parallelization (“concurrent operation”).  Margolus <cit.> carried out such a generalization, deriving a 1+1-dimensional form of parallelized quantum computation, retaining the ballistic model of a time-dependent quantum system evolving via a time-independent Hamiltonian.  These ballistic versions of quantum computation are well-suited for the investigation of thermodynamic reversibility and other fundamental physics questions but seem impractical if one wishes to realize an actual working device.  Among other issues, the Hamiltonians proposed by Feynman and Margolis require at least 3-body interactions.

Seminars at Berkeley in 1998 introduced the idea of using a ground state to perform universal quantum computation <cit.>.  This proposal was motivated by the practical problem of realizing a quantum computer.  In this approach, the time-independent ground state of a time-independent Hamiltonian is used to perform a quantum computation that is specified as a program of unitary gates.  This proposal rediscovered some technical features of the ballistic approach but introduced universal quantum computation in the ground state, rather than a time-dependent state.  The hope was that a system residing in the ground state would enjoy inherent robustness against decoherence.  In contrast with the earlier ballistic work, the ground state quantum computation (GSQC) model required only 2-body interactions in the time-independent Hamiltonian and also allowed parallelized quantum computation without Margolis's restriction to a 1+1-dimensional configuration.  There were early sketches of designs based on this model <cit.> and more theoretical work <cit.>.  At around the same time, very different motivations led Kitaev to independently consider universal quantum computing with ground states <cit.>.  Kitaev was interested in computationally complexity theory in the quantum context, and he carefully studied the eigenstates of Feynman's model.  This work was not primarily focused on questions of physical implementation; indeed, Kitaev did not hesitate to incorporate 5-body interactions in his Hamiltonian.

The initial idea behind <cit.> was to cool a system into the ground state of the GSQC Hamiltonian.  In 1999, a second GSQC paper <cit.> was submitted that further scrutinized the original GSQC plan to reach the ground state by cooling.    The quantum adiabatic algorithm gained the attention of quantum computing researchers around the same time as a means of solving optimization problems <cit.>.   As a result, by the time <cit.> was published in 2002, a note had been inserted that GSQC could employ adiabatic evolution (“one approach might be to turn on gradually the tunneling matrix elements in the Hamiltonian”) to reach the ground state.

In 2004, another group of Berkeley-associated researchers studied this idea of performing universal quantum computation by adiabatic tuning of a ground state.  Taking Kitaev's work  <cit.> on the Feynman model as a point of departure, rather than the GSQC formalism <cit.>, they carefully bounded the gap under adiabatic tuning of the Hamiltonian to show that universal adiabatic quantum computing could efficiently simulate the gate model in a noise-free setting <cit.>.  Their work was embraced by the quantum computer science community, and it generated substantial follow-up research.  In 2007, in response to this interest, <cit.> made the adiabatic argument of <cit.> more explicit for the GSQC Hamiltonian as opposed to the Feynman construction <cit.>.  Members of the quantum computer science community have critiqued this work based upon its level of rigor and completeness <cit.> and upon its correctness <cit.>.  Recently, a new proof <cit.> has appeared for a restricted 1+1-dimensional model <cit.>.  This work is rigorous, in accordance with the expectations of the quantum computer science community, but it is restricted to a 1+1-dimensional model, includes no 1-qubit gates, and requires the number of qubits in the computation to exceed the depth of the computation – a vexatious constraint.  In this paper, we revisit the proof of universal adiabatic quantum computation using GSQC <cit.> and supply proofs that are rigorous, include 1-qubit gates, permit lengthy computations in which the depth exceeds the number of qubits, and address a configuration of qubits with all-to-all connectivity as well as nearest-neighbor connectivity in 1+1 dimensions.  The proof techniques that we introduce may be of broader interest.

This paper is organized as follows.  In section II, we review the GSQC Hamiltonian.  We invoke the adiabatic theorem to upper bound its adiabatic evolution time in terms of a lower bound on its gap.  Section III derives an expression for this lower bound on the GSQC Hamiltonian gap in terms of 2 quantities that are bounded for a circuit consistent with a 1-dimensional configuration of qubits.  The argument is extended to a circuit consistent with an all-to-all configuration in which every qubit interacts with every other qubit.  Section IV proves that probability of measuring the output of the computation is at least 1/3.  We conclude in section V.



§ GSQC HAMILTONIAN AND COMPUTATION TIME


An adiabatic quantum computation is specified in terms of a parameter-dependent Hamiltonian H(λ).  One imagines preparing the system in the ground state of H(0) and adiabatically increasing the parameter λ from 0 to 1 to carry the system into the ground state of H(1).  The initial Hamiltonian H(0) is designed to have an easily-prepared ground state while the final Hamiltonian H(1) is designed so that its ground state contains the solution to some computational problem.

For universal adiabatic quantum computation, the computational problem in question is any given gate model quantum algorithm.  It is natural to define the gate model algorithm in terms of a program of unitary gates acting on M qubits during N time steps.  The number of time steps N is also known as the circuit depth, while the number of qubits M is sometimes termed the circuit width.   For each time step i ∈ [1,…,N] and each qubit A ∈ [1,…,M], the algorithm specifies a 1-qubit gate U_A,i∈𝐔(2) acting on A or a 2-qubit gate U_A,i;B,i∈𝐔(4) acting on A and some partner qubit  B.  For universal adiabatic quantum computation, our task is to design a Hamiltonian H(λ) such that the ground state of H(1) contains the results of this gate model algorithm.

To address this task, begin by considering a trivial algorithm with M=1, consisting only of 1-qubit gates U_1,i.  The solution to the gate model algorithm is U_1,N… U_1,1|0⟩.  There is a readily identified Hamiltonian of which this is the ground state, -U_1,N… U_1,1|0⟩<0| U_1,1^†… U_1,N^†, but this Hamiltonian explicitly involves the matrix product U_1,N… U_1,1.  Implementing such a Hamiltonian would require a classical precomputation of U_1,N… U_1,1, obviating any need to execute the quantum algorithm.  We want H(1) to depend upon the individual unitary gates (i.e. the algorithm itself) but not explicitly upon their product (i.e. the solution to the algorithm). 

We need to apply unitary gates sequentially within the ground state of H(1).  We do so by promoting the classical time step variable i to a quantum mechanical coordinate in Hilbert space.  In his construction for ballistic quantum computation <cit.>, Feynman introduced a clock particle with Hilbert space {| i ⟩| i=0,…,N }.  We employ a different approach <cit.> that avoids 3-body interactions in our Hamiltonian.  We expand the Hilbert space of our computational particle itself from {|0⟩,|1⟩} to {|0_i⟩,|1_i⟩| i = 0,…, N}.  It proves convenient to introduce fermionic creation operators c^†_A,i,0 and c^†_A,i,1 such that |0_i⟩  and |1_i⟩ of qubit A are c^†_A,i,0| vac⟩ and c^†_A,i,1| vac⟩, respectively.  We also define the row vector C^†_A,i = [ c^†_A,i,0      c^†_A,i,1].  In terms of these new operators, the solution  U_1,N… U_1,1|0⟩ of our trivial M=1 qubit gate model algorithm becomes C^†_1,N U_1,N… U_1,1[[ 1; 0 ]] | vac⟩.  Rather than making this the ground state of H(1), we consider the (unnormalized) state C^†_1,N U_1,N… U_1,1[[ 1; 0 ]]| vac⟩+C^†_1,N-1 U_1,N-1… U_1,1[[ 1; 0 ]]| vac⟩+ … + C^†_1,0[[ 1; 0 ]]  | vac⟩.  This “history" state is comprised of a sum of states corresponding to all time steps i=0,…,N of the computation.

The history state is the ground state of the Hamiltonian 
H(1)=h_1^1(INIT)+∑_i=1^Nh^i_1(U_1,i) where 

    h^i_A(U) ≡ℰ[..C_A,i^†-C_A,i-1^†U^†] [ C_A,i-UC_A,i-1].

Here,

    h^i_A(INIT) = ℰ c^†_A,i,1 c_A,i,1

“initializes" qubit A by imposing an energy penalty on the state C^†_1,N U_1,N… U_1,1[[ 0; 1 ]]| vac⟩+C^†_1,N-1 U_1,N-1… U_1,1[[ 0; 1 ]]| vac⟩+ … + C^†_1,0[[ 0; 1 ]]  | vac⟩, an alternate history state corresponding to a different input.  For a general U, the term (<ref>) causes qubit A to transition from |0_i-1⟩ to a superposition of |0_i⟩ and |1_i⟩ while |1_i-1⟩ transitions to an orthogonal superposition of |0_i⟩ and |1_i⟩.  In the case in which U is just the 2 × 2 identity matrix ℐ, the term (<ref>) causes qubit A to transition from |0_i-1⟩ to  |0_i⟩ and from |1_i-1⟩ to  |1_i⟩.  Fig. <ref> depicts a schematic physical realization of the H(1).




To reliably extract the computational output from the history state, it is possible to rescale <cit.> the coefficient of its term C^†_1,N U_1,N… U_1,1[[ 1; 0 ]]| vac⟩ or to append identity gates to the end of the calculation <cit.>.  The first approach is probably more suitable if one is interested in physically constructing a computer, since it involves less hardware.  The second approach is usually simpler for proofs.  

One can generalize this framework to multiqubit gate model computations.  We assume that each set of qubit states C_A,i is occupied by a single particle: the system is an eigenstate of ∑_i=0^N C_A,i^†C_A,i, with eigenvalue +1, for all A=1 to M.  For a trivial multiqubit algorithm consisting of only 1-qubit gates U_A,i, the solution to the gate model algorithm is ⊗_A=1^M ( Π _i=1^N  U_A,i|0⟩).  The corresponding history state is

    ⊗_A=1^M ( C^†_A,N U_1,N… U_1,1[[ 1; 0 ]] +C^†_A,N-1 U_1,N-1… U_1,1[[ 1; 0 ]]+ … + C^†_A,0[[ 1; 0 ]])  | vac⟩;

it is the ground state of 

    H(1)=∑_A=1^M h^1_A(INIT) + ∑_A=1^M∑_i=1^Nh^i_A(U_A,i).

Fig. <ref>(a) generalizes Fig. <ref> to the many-qubit case of Hamiltonian (<ref>). 




When a 2-qubit gate is included in the multiqubit gate model computation, one replaces U_A,j⊗ U_B,j in ⊗ _A=1^M (Π _i=1^N  U_A,i|0⟩) with U_A,j;B,j∈𝐔(4).  In the history state, we similarly replace U_A,j⊗ U_B,j with U_A,j;B,j.  There is a complication here since the history state initially contains some problematic terms in which U_A,j appears but not U_B,j and some problematic terms in which U_B,j appears but not U_A,j.  We resolve the complication by deleting “time-invalid” terms from the history state that contain U_A,i_A⊗ U_B,i_B with i_A and i_B on opposite sides of j, such that (i_A - j+1/2)(i_B-j+1/2) < 0.  The resulting history state is the ground state of H(1) provided that we replace h^j_A(U_A,j)+h^j_B(U_B,j) with h_A,B^j,j(U_A,j;B,j) + h_A,B^j,j(P).  Here,

    h_A,B^i,j(U)   ≡   ℰ[ C_A,i^†⊗ C_B,j^† - C_A,i-1^†⊗ C_B,j-1^†  U^†] 
          [  C_A,i⊗ C_B,j - U C_A,i-1⊗ C_B,j-1],

for any 2-qubit unitary operator U, while

    h_A,B^i,j(P)    =   ℰ∑_k<i,l≥ jC_A,k^†C_A,k⊗ C_B,l^†C_B,l
           +C_A,l^†C_A,l⊗ C_B,k^†C_B,k

imposes an energy penalty on the time-invalid terms that we deleted from the history state.  If h_A,B^j,j(P) were absent from our Hamiltonian, the time-invalid terms would become additional zero-energy ground states: a ground state supported by a time-invalid region in which qubit A resides at time steps i_A < j and qubit B resides at time steps i_B ≥ j and a ground state supported by a time-invalid region in which qubit A resides at time steps i_A ≥  j and qubit B resides at time steps i_B < j As noted by <cit.>, the penalty Hamiltonian was omitted from <cit.>.  This was corrected in <cit.>.  That revision, with the others we make here, should address any shortcomings in <cit.>..  Fig. <ref>(c) gives a schematic representation of the 2-qubit gate Hamiltonian h_A,B^j,j(U_A,j;B,j) + h_A,B^j,j(P) that replaces the two 1-qubit Hamiltonians h^j_A(U_A,j)+h^j_B(U_B,j) sketched in Fig. <ref>(b).

To use the GSQC Hamiltonian for computation, we would like to ensure that system occupies the ground state of H(1).  The original GSQC proposal <cit.> suggested that cooling could drive the system down to the ground state.  Later, the idea of computation by adiabatic evolution became widely known, and <cit.> pointed out that it could be applied to GSQC.  To adiabatically carry the system into the ground state, we  introduce an adiabatic parameter λ into the Hamiltonian.  We define H(λ) so that H(0) has a relatively simple ground state of H(0) and carry it into the ground state of H(1) by adiabatic evolution from λ = 0 to 1.  The following definition introduces λ dependence into the GSQC Hamiltonian in a suitable fashion.   It also includes a minor generalization that makes it possible to introduce and retire qubits at intermediate time-steps.


Consider a gate model quantum algorithm defined by circuit width M, circuit depth N, 1-qubit gates 𝒢_1 ≡{U_A,i}, and 2-qubit gates 𝒢_2 ≡{U_A,j;B,j}.  Suppose that the first gate acting on qubit A occurs at its original time step o_A≥ 1, the last gate acting on qubit A occurs at its final time step f_A ≤ N, and an element of either 𝒢_1 or 𝒢_2 acts on qubit A at every time step between o_A and f_A.  Suppose further that the first gate acting on every qubit is a 1-qubit identity gate ℐ.    The corresponding ground state quantum computation (GSQC) Hamiltonian with M independent λ parameters is

    H^independent(λ_1,…,λ_M)   =∑_A=2^Mℰ (1-λ_A-1^3)  ∑_i=o_A ^f_AC^†_A,i C_A,i+ ∑_A=1^M h^o_A-1_A(INIT)+  h^o_A_A(λ_A ℐ) 
           + ∑_i=1^N  (∑_U_A,i∈𝒢_1(1- δ_i,o_A) h^i_A(U_A,i) + ∑_U_A,i;B,i∈𝒢_2  h_A,B^i,i(U_A,i;B,i)  + h_A,B^i,i(P)).

This Hamiltonian is assumed to act within a basis of eigenstates of ∑_i=o_A-1^f_A C_A,i^†C_A,i, with +1 eigenvalue, for A ∈ [1,…,M].  

In terms of (<ref>), a GSQC Hamiltonian with a single λ parameter is defined using functions λ_A(λ)

    H(λ) = H^independent(λ_1(λ),λ_2(λ),…,λ_M(λ)).

The function λ_A(λ) has the property that H(0) = H^independent(0,…,0) and  λ_A+1 increases from 0 to 1 after λ_A has already finished increasing from 0 to 1.  For concreteness, set λ_A(λ)= F(Mλ-A) where F(x) = (10x^3-15 x^4 + 6 x^5) Θ(x) Θ(1-x) + Θ(x-1), in terms of the Heaviside function Θ(x).  This function begins at F(x) = 0 for x ≤ 0 and increases to reach F(x) = 1 for x ≥ 1 with well-behaved first and second derivatives.





For H(λ) to provide an appropriate adiabatic path to H(1), it is desirable for H(λ) to have a non-degenerate ground state at all values of λ.  This is demonstrated in the following theorem.

The GSQC Hamiltonian of Def. <ref> has a non-degenerate, zero energy ground state |ψ_0 (λ) ⟩.
  


First note that the GSQC Hamiltonian is a sum of positive semi-definitive terms.  It therefore cannot have any negative eigenvalues.  We will show that it does have a zero eigenvalue, which must be the ground state energy, and that the associated eigenstate is unique.

The GSQC Hamiltonian is assumed to act within a specific basis, as described in Def. <ref>.  We can write an arbitrary state in this basis in the form 

    [ ∑_i_1,…,i_M∑_b_1,…,b_Mψ_i_1,…,i_M(b_1,…,b_M) ⊗_A=1^M c^†_A,i_A,b_A]| vac⟩

where ψ_i_1,…,i_M(b_1,…,b_M) is a complex number that vanishes if any i_A is outside the range o_A-1 ≤ i_A ≤ f_A.

We construct the zero energy ground state as follows.  Suppose that a given term h^i_A(U_A,i) appears in (<ref>).  If such a term is to annihilate (<ref>), the equation ψ_i_1,…,i_A=i,…,i_M (b_1,…,b_A,…,b_M) = ∑_β_A = 0^1 [U_A,i]_b_A;β_Aψ_i_1,…,i_A=i-1,…,i_M(b_1,…,β_A,…,b_M) must hold, where [U_A,i]_b_A;β_A is a matrix element of U_A,i.   (When h^i_A(λ_A ℐ ) appears in (<ref>), the right hand side of the equation acquires an extra factor of λ_A: ψ_i_1,…,i_A=i,…,i_M (b_1,…,b_A,…,b_M) = λ_A ∑_β_A = 0^1 δ_b_A;β_Aψ_i_1,…,i_A=i-1,…,i_M(b_1,…,β_A,…,b_M).)  Suppose that a given term h_A,B^i,i(U_A,i;B,i) + h_A,B^i,i(P) appears in (<ref>).  If such a term is to annihilate (<ref>), the equation ψ_i_1,…,i_A=i,…,i_B=i,…,i_M(b_1,…,b_A,…,b_B,…,b_M) = ∑_β_A,β_B=0^1 [U_A,i;B,i]_b_A,b_B;β_A,β_Bψ_i_1,…,i_A=i-1,…,i_B=i-1…,i_M(b_1,…,β_A,…,β_B,…,b_M) must hold.  Moreover, we must have ψ_i_1,…,i_A≥ i,…,i_B<i,…,i_M(b_1,…,b_A,…,b_B,…,b_M)=ψ_i_1,…,i_A<i,…,i_B≥ i,…,i_M(b_1,…,b_A,…,b_B,…,b_M)=0 if h_A,B^i,i(P) is to annihilate (<ref>).  From these equations, we can uniquely deduce ψ_i_1,…,i_A,…,i_M(b_1,…,b_M) from ψ_i_1,…,i_A-1,…,i_M(b_1,…,b_M).  Thus, starting with ψ_i_1=o_1-1,…,i_M=o_M-1(b_1,…,b_M), we can uniquely deduce every ψ_i_1,…,i_M(b_1,…,b_M), thereby constructing a zero energy state.

The state is annihilated by ∑_A=1^M h^o_A-1_A(INIT), so ψ_i_1=o_1-1,…,i_M=o_M-1(b_1,…,b_M) must vanish unless b_1 = … = b_M = 0.   The starting state ψ_i_1=o_1-1,…,i_M=o_M-1(b_1,…,b_M) is therefore unique up to an overall constant.  Since every ψ_i_1,…,i_A,…,i_M(b_1,…,,b_M) uniquely follows from the starting state, we conclude that ∑_A=1^M h^o_A-1_A(INIT)+  h^o_A_A(λ_A ℐ) + ∑_i=1^N  (∑_U_A,i∈𝒢_1(1- δ_i,o_A) h^i_A(U_A,i) + ∑_U_A,i;B,i∈𝒢_2  h_A,B^i,i(U_A,i;B,i)  + h_A,B^i,i(P)) has a unique, zero energy ground state.

There is an extra term ∑_A=2^M∑_i=o_A ^f_Aℰ (1-λ_A-1^3)  C^†_A,i C_A,i in the definition of H(λ), but this term also annihilates the unique, zero energy ground state.  This is because, in the ground state, qubit A is localized at time step o_A-1 as long as λ_A=0; thus, ∑_i=o_A ^f_Aℰ (1-λ_A-1^3)  C^†_A,i C_A,i annihilates the ground state as long as λ_A=0.  Moreover, we have defined H(λ) so that λ_A deviates from 0 only after λ_A-1 becomes fixed at 1 rendering ∑_i=o_A ^f_Aℰ (1-λ_A-1^3)  C^†_A,i C_A,i = 0.


Note that the ground state of H(0) is simply the product state ⊗_A=1^M c^†_A,0,0|vac⟩, which is presumably straightforward to prepare.  The strategy of adiabatic quantum computation is to prepare the ground state of H(1) by slowly carrying λ from 0 to 1.  To assess the efficiency of this strategy, we bound the required amount of time.  The adiabatic theorem provides an estimate of this time given the energy gap between the ground state of H(λ) and its first-excited state.  Myriad forms of the adiabatic theorem have appeared in the literature; a review appears in <cit.>.  We invoke one recent form from <cit.>. 


Suppose that the spectrum of H(λ)  restricted to P(λ)  consists of m(λ)  eigenvalues (each possibly degenerate, crossing permitted) separated by a gap g(λ)  from the rest of the spectrum of H(λ), and H, Ḣ , and Ḧ are bounded operators. (This assumption is always fulfilled in finite-dimensional spaces.) Then, for  |ψ⟩∈ P(0)  and any λ∈[0,1],

    ⟨ψ| U^†_T(λ) (1 - P(λ))  U_T(λ)  |ψ⟩≤ A(λ)^2, P_T(λ)-P(λ)≤ A(λ),

where
A(λ) ≤1/T[ mḢ/g^2 |_λ=0 + mḢ/g^2 |_λ  +  ∫_0^λ(m Ḧ/g^2 + 7 m √(m)Ḣ^2/g^3) ].



To apply this theorem to our H(λ),  we note that m(λ) = 1.  Using the triangle inequality for the norm, we deduce Ḣ≤ |2λ_A λ̇_̇Ȧ| +| λ̇_̇Ȧ|+|3λ_A^2 λ̇_̇Ȧ| ≤ 6(15/8) Mℰ≤ 12 Mℰ, and Ḧ≤ |2 λ̇_̇Ȧ^2 + 2 λ_A λ̈_̈Ä| + |λ̈_̈Ä| + |6 λ_A λ̇_̇Ȧ^2+3 λ_A^2 λ̈_̈Ä| ≤ 8 |λ̇_̇Ȧ|^2 + 6| λ̈_̈Ä| ≤ (8(15/8)^2 + 6(10/√(3))) M^2ℰ≤ 63M^2ℰ using the expression for F(x) in Def. <ref>.   Therefore, the amount of excitation of the ground state during adiabatic evolution is bounded by the quantity ((24M+63M^2)ℰ/g_min^2 + 7(144 M^2)ℰ^2/g_min^3)/T < 1095M^2ℰ^2/Tg_min^3. Thus, the amount of excitation will be small if T ≫ 1095M^2ℰ^2/g_min^3.  To use this expression, we need to derive a lower bound on the energy gap g_min.  Note that this expression is quite pessimistic, and a time T ≫ 1/g_min may be sufficient <cit.>.  However, to ensure rigor, we employ the pessimistic expression in this paper.






§ GAP OF H(Λ)


The following lemma simplifies our analysis of g_min by allowing us to substitute identity gates for the unitary gates 𝒢_1 ≡{U_A,i}, and 𝒢_2 ≡{U_A,j;B,j} in H(λ).

[Identity gates]

Starting with H(λ), define a new Hamiltonian H(λ) in which every 1-qubit gate U_A,j is replaced with an identity gate ℐ  and every 2-qubit gate U_A,j;B,j is replaced with ℐ⊗ℐ.  This H(λ) can be obtained from H(λ) by a unitary transformation that preserves the energy gap.




We prove this lemma by exhibiting the unitary transformation

    𝒰  =  ∑_i_1=o_1-1^f_1…∑_i_M=o_M-1^f_M⊗_A=1^M C_A,i_A^† V(i_1,…,i_M) ⊗ _B=1^M C_B,i_B
       =    ∑_i_1=o_1-1^f_1…∑_i_M=o_M-1^f_M∑_b_1=0^1…∑_b_M=0^1∑_b^'_1=0^1…∑_b^'_M=0^1
          V(i_1,…,i_M)_b_1,…,b_M;b^'_1,…,b^'_M⊗_A=1^M c_A,i_A,b_A^†⊗ _B=1^M c_B,i_B,b^'_B

Here, V(i_1,…,i_M) is a 2^M by 2^M unitary matrix that acts on the C_B,i_B column-vectors, leaving the qubit indices B and time steps i_B fixed but changing the bit values b_B.

We show that 𝒰 is unitary in the basis described in Def. <ref>: eigenstates of ∑_i=o_A-1^f_A C_A,i^†C_A,i, with +1 eigenvalue, for A=1,…,M.  To demonstrate unitarity, note that c_B,i_B,b^'_B⊗_A=1^M c_A,j_A,β_A|ψ⟩ =  0 for all states |ψ⟩  in the basis.  Indeed, 0=(∑_i=o_A-1^f_A C_A,i^†C_A,i - 1)|ψ⟩, implying c_A,j,bc_A,j^',b^'(∑_i=o_A-1^f_A C_A,i^†C_A,i - 1)|ψ⟩ = 0 = (∑_i=o_A-1^f_A C_A,i^†C_A,i +1) c_A,j,bc_A,j^',b^'|ψ⟩.  Since (∑_i=o_A-1^f_A C_A,i^†C_A,i +1) is a positive operator, it follows that c_A,j,bc_A,j^',b^'|ψ⟩ = 0 and thus c_B,i_B,b^'_B⊗_A=1^M c_A,j_A,β_A|ψ⟩ =  0.  With this fact in mind, compute

    𝒰^†𝒰|ψ⟩  = ∑_i_1=o_1-1^f_1…∑_β^'_M=0^1 V(i_1,…,i_M)^†_b_1,…,b_M;b^'_1,…,b^'_M
           V(j_1,…,j_M)_β^'_1,…,β^'_M;β_1,…,β_M⊗_A=1^M c_A,i_A,b_A^†
          ⊗ _B=1^M (δ_i_B,j_Bδ_b^'_B,β^'_B - c^†_B,j_B,β^'_Bc_B,i_B,b^'_B)
          ⊗_A=1^M c_A,j_A,β_A|ψ⟩

The only contribution from ⊗ _B=1^M (δ_i_B,j_Bδ_b^'_B,β^'_B - c^†_B,j_B,β^'_Bc_B,i_B,b^'_B) comes from ⊗ _B=1^M δ_i_B,j_Bδ_b^'_B,β^'_B since c_B,i_B,b^'_B⊗_A=1^M c_A,j_A,β_A|ψ⟩ =  0.  Thus, 

    𝒰^†𝒰|ψ⟩  = ∑_i_1=o_1-1^f_1…∑_b^'_M=0^1V(i_1,…,i_M)^† _b_1,…,b_M;b^'_1,…,b^'_M
          V(i_1,…,i_M)_b^'_1,…,b^'_M;β_1,…,β_M⊗_A=1^M c_A,i_A,b_A^† c_A,i_A,β_A|ψ⟩
        =    ∑_i_1=o_1-1^f_1…∑_i_M=o_M-1^f_M⊗_A=1^M C_A,i_A^† C_A,i_A|ψ⟩  = |ψ⟩.


If the gate model quantum algorithm contains only one qubit gates, then take V(i_1,…,i_M) ≡⊗ _B=1^M (U_B,i_B⋯ U_B,1).  If a two-qubit gate U_A,j;B,j appears instead of U_A,j and U_B,j  in the gate model algorithm, replace  U_A,j⊗ U_B,j in this definition with U_A,j;B,j  when i_A, i_B ≥ j and otherwise set U_A,j = U_B,j = ℐ.  Direct calculation shows that H(λ)|ψ⟩=𝒰^† H(λ)𝒰|ψ⟩.


Note that H(λ) does not change the bit value of any qubit: it has no matrix element between c_A,i,b and c_A,i,1-b for any A, i, or b.  Fig. <ref>, to be compared with Fig. <ref>, shows this simplification graphically.  Thus, H(λ) is block-diagonal in the basis of bit values, and we will find it convenient to study it block-by-block.  Note, in particular, that its ground state resides in the block in which all bits have value 0 and ∑_A=1^M h^o_A-1_A(INIT) vanishes.

Our lower bound on the gap will make use of the following generic lemma about the sums of Hamiltonians <cit.>.

[Eigenvalue Bound for Sum of Hamiltonians]
Let h be a Hamiltonian with a ground state space 𝒮_0 of states of energy e_0 and a first excited energy e_1.  Let δ h be a positive semi-definite Hamiltonian with maximum eigenvalue δ h.  Then a lower bound for the eigenvalues of h+δ h is

    min_|ψ_0⟩∈𝒮_0 e_0 + (e_1-e_0) ⟨ψ_0| δ h |ψ_0⟩/(e_1-e_0) + ⟨ψ_0| δ h |ψ_0⟩ + δ h .




Without loss of generality, we can write the ground state of h+δ h in the form a |ψ_0⟩ + b |δψ⟩, where |ψ_0⟩ is a normalized state in 𝒮_0, |δψ⟩ is a normalized state orthogonal to 𝒮_0,  and |a|^2+|b|^2=1.  Expressing h + δ h-e_0 in the basis of |ψ_0⟩, |δψ⟩ gives the 2 × 2 matrix

    [[       ⟨ψ_0 |δ h| ψ_0 ⟩         ⟨ψ_0 |δ h| δψ⟩;        ⟨δψ |δ h| ψ_0 ⟩ ⟨δψ |h + δ h -e_0| δψ⟩ ]].

If the eigenvalues of this matrix are ε_0 ≤ε_1, then, since h-e_0 and δ h are positive semi-definite, we know that ε_0 and ε_1 are non-negative.  It follows that ε_0 ≥ε_0 ε_1/(ε_0+ε_1), which is the ratio of the determinant to the trace. 

The determinant of this matrix is at least ⟨δψ |h-e_0| δψ⟩⟨ψ_0 |δ h| ψ_0 ⟩ since ⟨ψ_0 |δ h| ψ_0 ⟩⟨δψ |δ h| δψ⟩ - |⟨δψ |δ h| ψ_0 ⟩|^2 ≥ 0.  Dividing by the trace of this matrix gives ⟨ψ_0 |δ h| ψ_0 ⟩/[1+(⟨ψ_0 |δ h| ψ_0 ⟩+ ⟨δψ |δ h| δψ⟩)/ ⟨δψ |h -e_0| δψ⟩].  This is minimized by setting ⟨δψ |δ h| δψ⟩ to its maximum value δ h and ⟨δψ |h -e_0| δψ⟩ to its minimum value e_1-e_0, which gives 

    e_0 + (e_1-e_0) ⟨ψ_0| δ h |ψ_0⟩/(e_1-e_0) + ⟨ψ_0| δ h |ψ_0⟩ + δ h .

We minimize over choices of |ψ_0⟩ to obtain the bound that appears in the statement of the lemma.


To lower bound the gap of H(λ), we now cast the circuit of Def. <ref> into a more specific form.  Our first case of interest is a one-dimensional configuration in which the qubits are positioned on a line and 2-qubit gates are performed between nearest neighbors.   It is reminiscent of the configuration considered in <cit.> but permits computations with N ≫ M and includes 1-qubit gates.  A sketch of the configuration appears in Fig. <ref>.



A GSQC Hamiltonian H(λ) of Def. <ref> has a one-dimensional configuration if it is derived from the following type of circuit.  The circuit acts on an odd number of qubits M and is generated from a underlying algorithm of even depth n ≥ M-1.  To the end of the circuit are added an extra n+M-1 time steps of 1-qubit identity gates acting on every qubit, bringing the depth to 2n+M-1.  The 1-qubit gates and the 2-qubit gates are then segregated into separate time steps such that no 2-qubit gate acts at an odd time step.  At time step 2j+1, for j ∈ [1,…,(2n+M-1)], every qubit A undergoes a 1-qubit gate U_A,2j+1.  At time step 2j+2, for j ∈ [1,…,(2n+M-1)], there are 2-qubit gates U_A,2j+2;B,2j+2 that follow a specific pattern consistent with a 1-dimensional layout of qubits.  In particular, when j is odd, A=2 and B=3 undergo a 2-qubit gate, qubits A=4 and B=5 undergo a 2-qubit gate, qubits A=6 and B=7 undergo a 2-qubit gate, and so on.  Qubit 1 is the only qubit to undergo a 1-qubit gate U_1,2j+2 =ℐ at time step 2j+2 when j is odd.  When j is even, the pattern of gates switches, so that qubits A=1 and B=2 undergo a 2-qubit gate, qubits A=3 and B=4 undergo a 2-qubit gate, qubits A=5 and B=6 undergo a 2-qubit gate, and so on.  Qubit M is the only qubit to undergo a 1-qubit gate U_M,2j+2 = ℐ at time step 2j+2 when j is even.  The pattern of 2-qubit gates is summarized in Table <ref>.  The segregation into 1-qubit gate time steps and 2-qubit gate time steps doubles the depth of the circuit to 2(2n+M-1), from original time step 3 to final time step 2(2n+M).

In addition to the gates above, every qubit undergoes a 1-qubit identity gate U_2(2n+M)+1 =ℐ.  Each of the qubits with even A begins with two additional 1-qubit identity gates U_A,1 = U_A,2 = ℐ, so that o_A = 1 and f_A = 2(2n+M)+1.  Each of the qubits with odd A<M finishes with two additional 1-qubit identity gates U_A,2(2n+M)+2 = U_A,2(2n+M)+3 = ℐ so that o_A = 3 and f_A = 2(2n+M)+3.  Qubit A=M has o_A =3 and f_A = 2(2n+M)+1.   The net depth of the circuit is N = 2(2n+M)+3 ≥ 6M-1.  Only identity gates act during the final 2n+2M =  (N-3)/2+M time steps of the circuit.


The Hamiltonian of Def. <ref> is depicted in Fig. <ref> for the case M=5, N=9.  (The values M=5, N=9 are chosen to keep the figure a manageable size despite violating the condition N≥ 6 M-1.)  The figure is simplified, analogously to Fig. <ref>, under the assumption that all gates are identity gates (Lem. <ref>).










Apply Lem. <ref> to the Hamiltonian H(λ) of Def. <ref>, and let  | ψ_0 (λ)⟩ be the resulting ground state.  Let A be the integer satisfying A-1/M≤λ < A/M for λ < 1 and let A=M for λ =1.  (Thus, A = ⌊ M λ⌋+1 for λ <1.)  Let e_1(λ) be the lowest non-zero eigenvalue of H(λ) -  h^o_A_A(λ_A ℐ) in the sub-block in which all bits have bit value zero.  Then H(λ) has a gap g(λ) bounded below by

    g_min = min_λ1/4e_1(λ) ⟨ψ_0 (λ)| c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0 (λ)⟩.




Note that H(λ) commutes with C^†_B,o_B-1C_B,o_B-1 for all B > A, so it can be diagonalized into 2^M-A blocks with C^†_B,o_B-1C_B,o_B-1 fixed at either 0 or 1 for each B > A.  To find the first excited state, we can limit our attention to the block of H(λ) in which all qubits B > A =  ⌊ M λ⌋ +1 are quiescent, with C^†_B,o_B-1,0C_B,o_B-1,0 having eigenvalue 1.

To see this, consider a block in which C^†_B,o_B-1C_B,o_B-1 has eigenvalue 0 for some particular B > A+1.  Note that H(λ) contains the term ∑_i=o_B^f_Bℰ(1-λ_B-1^3) C^†_B,iC_B,i.  Since B>A+1, we have λ_B-1=λ_B=0, so this sum becomes ∑_i=o_B^f_Aℰ C^†_B,iC_B,i.  This pushes the energies of all states in the block up to ℰ or greater.

This argument needs a little adjustment when we consider the block in which C^†_B,o_B-1,0C_B,o_B-1,0 has eigenvalue 1 for all quiescent qubits B > A+1 but eigenvalue 0 for a single itinerant qubit B=A+1.  The energy of every state in the block is at least ℰ(1-λ_A^3) because of the contribution of ∑_i=o_B^f_Bℰ(1-λ_B-1^3) C^†_B,iC_B,i =  ℰ(1-λ_A^3)  ∑_i=o_B^f_BC^†_B,iC_B,i  = ℰ(1-λ_A^3) to H(λ).  Thus, if λ_A ≤ 3/4, every state in the block has energy (1-(3/4)^3) ℰ or greater.  But what happens when the energy ℰ(1-λ_A^3) becomes small as λ_A approaches 1?  In the basis of Def. <ref>, ℰ(1-λ_A^3) ≥ℰ(1-λ_A^3)(C^†_A,o_A-1C_A,o_A-1+C^†_A,o_AC_A,o_A).  When 3/4 < λ_A < 1, ℰ(1-λ_A^3)(C^†_A,o_A-1C_A,o_A-1+C^†_A,o_AC_A,o_A) + h_A^o_A(λ_A ℐ) > h_A^ o_A(ℐ) = (h_A^ o_A(λ_Aℐ) + ∑_i=o_A+1^f_A+1ℰ(1-λ_A^3) C^†_A+1,iC_A+1,i|_λ_A=1,  so it follows that the smallest energy in the block when 3/4<λ_A<1 is lower bounded by the smallest energy in the block when λ_A =1.  Thus, we do not have to consider the block when 3/4 < λ_A <1 as long as we study the block when λ_A=1.  Note, however, that λ_A reaches 1 precisely when λ reaches the value λ^' = A/M, which triggers the value of A to increment to A^' = ⌊ M λ^'⌋+1 = A+1.   Because A has incremented to A^', the itinerant qubit B=A+1 is now qubit B=A^', and it follows that our block at λ_A=1 can be studied by studying the block of H(λ^') in which all qubits B > A^' are quiescent with C^†_B,o_B-1,0C_B,o_B-1,0 having eigenvalue 1.

The conclusion is that we can focus, for 0<λ<1, on the block of H(λ) in which all qubits B > A are quiescent with C^†_B,o_B-1,0C_B,o_B-1,0 having eigenvalue 1.  The application of Lem. <ref> allows us to treat all unitary gates in H(λ) as identity gates so our block can be further diagonalized into 2^M sub-blocks in the basis of bit values.  All of its 2^M sub-blocks are identical except for the contribution of the positive definite initialization Hamiltonian ∑_A=1^M h^o_A-1_A(INIT).  The (normalized) ground state | ψ_0 (λ)⟩ of Thm. <ref> resides in the sub-block in which the initialization Hamiltonian vanishes identically – the sub-block in which all the bit values are zero.  In part (a) of the following, we apply Lem. <ref> to bound the first excited state of H(λ) in this sub-block.  In part (b), we apply Lem. <ref> to bound the ground state energy of H(λ) in the other 2^M-1 sub-blocks.

(a) Set δ h =  h^o_A_A(λ_A ℐ), h = H(λ) -  δ h, and focus on the sub-block in which all bits have bit value zero.  The sub-block contains the ground state of H(λ), | ψ_0 (λ)⟩.  Because of the subtraction of δ h, h has an additional zero-energy, orthogonal ground state besides | ψ_0 (λ)⟩; we assign it the label | ψ_0^⊥ (λ)⟩.  Lem. <ref> gives the following lower bound on the lowest energy of H(λ)  in the sub-block, in the space orthogonal to | ψ_0 (λ)⟩:

    e_1(λ) ⟨ψ_0^⊥(λ)| h^o_A_A(λ_A ℐ) |ψ_0^⊥(λ)⟩/e_1(λ) + ⟨ψ_0^⊥(λ)| h^o_A_A(λ_A ℐ) |ψ_0^⊥(λ)⟩ + λ_A^2+1 .

To evaluate ⟨ψ_0^⊥(λ)| h^o_A_A(λ_A ℐ) |ψ_0^⊥(λ)⟩, note that |ψ_0(λ)⟩ = κ_0[ λ_A(λ) + (1-λ_A(λ)) c^†_A,o_A-1,0c_A,o_A-1,0] |ψ_0(A/M)⟩
since |ψ_0(A/M)⟩ corresponds to the case λ=A/M, λ_A =  1.  The orthogonal ground state is |ψ_0^⊥(λ)⟩ = κ_0^⊥[ 1 + (μ-1) c^†_A,o_A-1,0c_A,o_A-1,0] |ψ_0(A/M)⟩.  Orthogonality implies μ = λ_A(1 - 1/⟨ψ_0(A/M)|c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0(A/M)⟩) while the normalization constants are κ_0 = 1/√(λ_A^2+(1-λ_A^2) ⟨ψ_0(A/M)|c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0(A/M)⟩) and κ_0^⊥ = 1/√(1+(μ^2-1) ⟨ψ_0(A/M)|c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0(A/M)⟩).

We find that ⟨ψ_0^⊥(λ)| h^o_A_A(λ_A ℐ) |ψ_0^⊥(λ)⟩ = λ_A ^2+ ⟨ψ_0(A/M)|c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0(A/M)⟩/(1-⟨ψ_0(A/M)|c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0(A/M)⟩).  Inserting these expressions into our lower bound, and simplifying under the assumption e_1(λ)<1, we find a bound e_1(λ)⟨ψ_0(A/M)|c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0(A/M)⟩/2. 

(b) Consider the other 2^M-1 sub-blocks in which 1 or more qubits have bit value 1. The initialization Hamiltonian makes a contribution ℰ c^†_B,o_B-1,1c_B,o_B-1,1 to the sub-block for each qubit with bit value 1.  This positive semi-definite contribution is smallest in sub-blocks for which a single qubit B has bit value equal to 1; if we go to a sub-block that includes another positive semi-definite term, we can only push the energy of its ground state higher.  Thus, we are justified in focusing on the case in which the initialization Hamiltonian contributes ℰ c^†_B,o_B-1,1c_B,o_B-1,1 to the block for a single qubit B.

Set δ h =  h^o_A_A(λ_A ℐ) +h^o_B-1_B(INIT) and h = H(λ) -  δ h.  Lem. <ref> gives the following lower bound on the lowest energy of H(λ) in this block of interest:

    min_|ψ⟩ = cosθ|ψ_0(λ)⟩ +sinθ|ψ_0^⊥(λ)⟩e_1(λ) ⟨ψ|δ h |ψ⟩/e_1(λ) +  ⟨ψ|δ h |ψ⟩ +  λ_A^2+2 .

We minimize over θ to find ⟨ψ|δ h |ψ⟩ and obtain the smallest result when A=B.  Assuming that e_1(λ)<1, we derive a lower bound  e_1(λ) ⟨ψ_0(A/M)|c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0(A/M)⟩/4, which is smaller than the bound in (a).


We now bound g_min of Thm. <ref> by bounding the quantities e_1(λ) and ⟨ψ_0 (λ)| c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0 (λ)⟩. 



Let H(λ) be a GSQC Hamiltonian (Def. <ref>) of a circuit that conforms with the one-dimensional configuration of Def. <ref>.  Then  ⟨ψ_0 (λ)| c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0 (λ)⟩≥ 1/N, where A is the integer satisfying A-1/M≤λ < A/M (with A=M if λ =1).



Because it has zero energy, the ground state must have the same probability density on all time-valid choices of {i_1,…,i_M}.  The claim of the lemma therefore comports with the naive expectation that each qubit occupies each time step with probability at least ∼ 1/N.  A careful proof follows.

Suppose that A < M.  Then, in the ground state |ψ_0 (λ)⟩, qubits A+1,…,M are localized at time steps o_A+1-1,…,o_M-1 respectively.    Because qubit A+1 resides inertly at position o_A+1-1, there are only 4 valid time step values o_A - 1,…,o_A+2 available to qubit A before it finds itself unable to traverse a 2-qubit gate with qubit A+1.  For each valid time step, there are 4 valid time step values available to qubit A-1.  For each of those time step values, there are 4 valid time step values available to qubit A-2.  This pattern continues down to qubit 1.  Introducing a normalization constant κ_0, we have ⟨ψ_0 (λ)| c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0 (λ)⟩ = 4^A-1κ_0^2, while ⟨ψ_0 (λ)| c^†_A,o_A,0c_A,o_A,0|ψ_0 (λ)⟩=⟨ψ_0 (λ)| c^†_A,o_A+1,0c_A,o_A+1,0|ψ_0 (λ)⟩=⟨ψ_0 (λ)| c^†_A,o_A+2,0c_A,o_A+2,0|ψ_0 (λ)⟩ = λ_A^2 4^A-1κ_0^2.  Since the sum of these matrix elements must be 1, we can solve for κ_0 and conclude that ⟨ψ_0 (λ)| c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0 (λ)⟩ = 1/(1+3λ_A^2) ≥ 1/4 > 1/N.

Next suppose that A=M.  In this case, in the ground state |ψ_0 (λ)⟩, qubit A visits all N-3 time steps from o_M-1=2 to f_M = N-2.  Again, ⟨ψ_0 (λ)| c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0 (λ)⟩ = 4^A-1κ_0^2, while ⟨ψ_0 (λ)| c^†_A,o_A,0c_A,o_A,0|ψ_0 (λ)⟩ = … = ⟨ψ_0 (λ)| c^†_A,f_A,0c_A,f_A,0|ψ_0 (λ)⟩ = λ_A^2 4^A-1κ_0^2.  We conclude that ⟨ψ_0 (λ)| c^†_A,o_A-1,0c_A,o_A-1,0|ψ_0 (λ)⟩ = 1/(1+(N-4) λ_A^2) ≥ 1/(N-3) > 1/N. 


To bound g_min using Thm. <ref>, our remaining task is to lower bound the quantity e_1(λ).  We assume that Lem. <ref> has been applied to H(λ), and our attention is focused on the sub-block of H(λ) -  h^o_A_A(λ_A ℐ) with all zero bit values.  The operator c^†_A,o_A-1,0c_A,o_A-1,0 commutes with this Hamiltonian.  We will argue below that that the smallest value of e_1(λ) occurs when λ = 1 and c^†_A,o_A-1,0c_A,o_A-1,0 = c^†_M,o_M-1,0c_M,o_M-1,0 has eigenvalue 0.  To analyze this case, it is useful to associate a graph with H(1) -  h^o_M_M(ℐ) as follows.  The vertices of the graph lie in one-to-one correspondence with time-valid points i = (i_1,i_2,…,i_M ) for which i_M ≥ o_M and all penalty Hamiltonians of the form (<ref>) vanish To compute e_1(λ), we need not consider those very high-energy states which the penalty Hamiltonian does not annihilate..  The set of vertices is called V.  There is an edge connecting any two vertices between which there is a non-zero Hamiltonian matrix element.  All edges have equal weight because every such matrix element has the same value -ℰ for H(1) -  h^o_M_M( ℐ).  Two vertices i and i ^' connected by an edge are called adjacent; we write i∼ i ^' to express adjacency.

Any state vector | ψ⟩ in the Hilbert space of interest can be described in terms of the function ψ(i_1,…,i_M) = ⟨vac| ⊗_A=1^M c^†_A,i_A,0| ψ⟩.  If | ψ⟩ is annihilated by the penalty Hamiltonian (<ref>), then ψ(i_1,…,i_M) will be supported on the vertices of the graph.  The expectation value of H(1) -  h^o_M_M( ℐ) in the state is given by


    E_ψ =  ⟨ψ| H(1) -  h^o_M_M( ℐ) | ψ⟩ = ℰ∑_ i∼ i ^'| ψ( i ) - ψ( i ^')|^2/∑_ i∈ V| ψ( i )|^2.

The state with smallest E_ψ is ψ_0( i ) = 1/√( V), a constant function with E_ψ_0= 0.  We are interested in lower bounding the smallest energy E_ψ of any state orthogonal to ψ_0( i ) .  The following lemma, closely related to a result in <cit.>, is our workhorse.

[Paths]

Consider a graph with vertices V.  Let V be even.  Let ϕ( i) be a real valued function, orthogonal to ψ_0( i) so that ∑_ i∈ Vϕ( i) = 0.  We wish to lower bound E_ϕ, the expectation value (<ref>), for ϕ( i).

Suppose that there is a positive integer T large enough to permit the existence of a path P( i,t):  V⊗[0,1,… , T] → V with the following properties:


  (I) The path must begin as the identity: P( i,0) =  i.

  (II) The path must advance by at most an edge at a time: P( i,t) = P( i,t+1) or P( i,t)∼ P( i,t+1).

  (III) The path must produce a one-to-one mapping to vertices at the final time T: P( i,T)=P( i^',T) ⇔ i =  i^'.

  (IV) Set Φ equal to the median value of ϕ( i) and let ψ( i) = ϕ( i) - Φ.  Because Φ is the median value of ϕ( i), we can partition V into a set P in which ψ( i) is non-negative and a disjoint set N in which ψ( i) is non-positive, with P =  N =  V/2. The path must allow a second partition of V into pairs of adjacent vertices i∼ i^' such that either P( i,T) ∈ P P( i^',T) ∈ N or P( i,T) ∈ N P( i^',T) ∈ P.


Suppose that B = max_ i∼ i^' B_ i, i^', where, for any i∼ i^', B_ i, i^' gives the number of instances in which P employs the edge between i and i^'.  Explicitly, B_ i, i^' = ∑_ i^''∈ V∑_t=0^T-1( δ_P( i^'',t), iδ_P( i^'',t+1), i^'+ δ_P( i^'',t+1), iδ_P( i^'',t), i^') where δ_ i, i^'' = 1 ⇔ i =  i^''.  Then, E_ϕ≥ 2ℰ/(2T+1)(2B+1).





Note that 

    E_ψ = ℰ∑_ i∼ i^'| ψ( i) - ψ( i^')|^2/∑_ i∈ V| ψ( i)|^2 = ℰ∑_ i∼ i^'| ϕ( i) - ϕ( i^')|^2/∑_ i∈ V| ϕ( i)|^2 - Φ (ϕ( i) +ϕ^*( i)) +  |Φ|^2 = ℰ∑_ i∼ i^'| ϕ( i) - ϕ( i^')|^2/∑_ i∈ V| ϕ( i)|^2 +  |Φ|^2≤ E_ϕ.

Thus,a lower bound for E_ψ also lower bounds E_ϕ.  


Note that (III) implies

    2 ∑_ i∈ V| ψ( i)|^2 =   2 ∑_ i∈ V| ψ(P( i,T))|^2  =   ∑_ i∈ V| ψ(P( i,T))|^2 +  | ψ(P( i^'( i) ,T))|^2

where i^'( i) is the partner of i in the second partition described in (IV).  It follows from (IV) that ψ(P( i,T)) ψ(P( i^'( i),T)) ≤ 0, so

    2 ∑_ i∈ V| ψ( i)|^2 ≤∑_ i∈ V| ψ(P( i,T)) -  ψ(P( i^'( i),T))|^2.

Each term on the right hand side expands into a telescoping sum

    | ψ(P( i,T)) -  ψ(P( i^',T))|^2
       =    | ψ(P( i,T)) -  ψ(P( i,T-1)) + … +   ψ(P( i,1)) -  ψ(P( i,0)) . 
           + ψ(P( i,0)) -  ψ(P( i^',0)) 
           + . ψ(P( i^',0)) -  ψ(P( i^',1)) + … + ψ(P( i^',T-1)) -  ψ(P( i^',T)) |^2.
       ≤    (2T+1) ( | ψ(P( i,T)) -  ψ(P( i,T-1))|^2 + … +  | ψ(P( i,1)) -  ψ(P( i,0))|^2 .
           +  | ψ(P( i,0)) -  ψ(P( i^',0))|^2 
          . + | ψ(P( i^',T)) -  ψ(P( i^',T-1))|^2 + … +  | ψ(P( i^',1)) -  ψ(P( i^',0))|^2 )

where we have suppressed the dependence of i^'( i) to lighten the notation.

Using (I), we can write | ψ(P( i,0)) -  ψ(P( i^',0))|^2 = | ψ( i) - ψ( i^')|^2, so

    2 ∑_ i∈ V| ψ( i)|^2    ≤    (2T+1) ( ∑_ i∈ V∑_t=0^T-1| ψ(P( i,t)) -  ψ(P( i,t+1))|^2  . 
          .  +  ∑_ i∈ V∑_t=0^T-1| ψ(P( i^'( i),t)) -  ψ(P( i^'( i),t+1))|^2 + ∑_ i∈ V| ψ( i) - ψ( i^')|^2 ) 
        =     (2T+1) (2 ∑_ i^''∈ V∑_t=0^T-1| ψ(P( i^'',t)) -  ψ(P( i^'',t+1))|^2 + ∑_ i∈ V| ψ( i) - ψ( i^')|^2 ).

Rewriting the first sum and adding terms to the second sum, we use (II) to obtain

    2 ∑_ i∈ V| ψ( i)|^2     ≤    (2T+1) (2 ∑_ i^''∈ V∑_t=0^T-1∑_ i∼ i^'(δ_P( i^'',t), iδ_P( i^'',t+1), i^'+ δ_P( i^'',t+1), iδ_P( i^'',t), i^') | ψ( i) -  ψ( i^')|^2 . 
          .  + ∑_ i∼ i^'| ψ( i) - ψ( i^')|^2 )  
        =     (2T+1)  ∑_ i∼ i^'  (2B_ i, i^'+1) | ψ( i) -  ψ( i^')|^2
       ≤    (2T+1) (2B+1)   ∑_ i∼ i^'| ψ( i) -  ψ( i^')|^2.

Dividing the initial expression and the final expression by (2T+1)(2B+1) ∑_ i∈ V| ψ( i)|^2 yields the desired inequality.


We have written Lem. <ref> so that it only applies to graphs that have V even, and moreover only to graphs that can be partitioned into pairs of adjacent vertices.  These assumptions are almost certainly inessential, but they simplify the proof of the Lemma.

In the Appendix, we apply this lemma to examples of increasing complexity. The proof for our graph of interest, the one-dimensional configuration (Def. <ref>) depicted in Fig. <ref>, references these examples.


For a circuit with a one-dimensional configuration of qubits (Def. <ref>) the minimum gap is bounded by

    g_min≥ℰ/(12M(N+2M-4)+1)(4(N+4M-4)+1)(2N).





We first argue that e_1(λ) is smallest when λ = 1.  If λ<(M-1)/M, note that e_1(λ) is associated with an excited state of H(λ) -  h^o_A_A(λ_A ℐ) for which all qubits B > A are fixed at c^†_B,o_B-1,0c_B,o_B-1,0.  In this state, there are only 4 valid time step values o_A - 1,…,o_A+2 available to qubit A before it finds itself unable to traverse the 2-qubit gate with qubit A+1.  Otherwise, as far as the energy of excited this state is concerned, we may as well have a computer with A qubits rather than M qubits: qubits B>A play no role in determining the energy of the excited state.  We can lower bound the energy of the excited state using the same technique that we use below to lower bound e_1(1), except that M is replaced with A and f_A is replaced with o_A+2.  Since these replacements increase the lower bound, we can focus on e_1(1) and need not consider the case λ < (M-1)/M further.  And, noting that H(λ) -  h^o_M_M(λ_M ℐ) is independent of λ for (M-1)/M ≤λ≤ 1, we can just fix λ =1.

Once we fix λ =1, we note that H(1) -  h^o_M_M( ℐ) commutes with c^†_M,o_M-1,0c_M,o_M-1,0.  If we work among states with c^†_M,o_M-1,0c_M,o_M-1,0 equal to 1, then qubit M-1 is confined to a 4 time-steps o_M - 1,…,o_M+2.  We can lower bound the energy of the excited state using the same technique that we use below, except that M is replaced with M-1 and f_A is replaced with o_A+2.  Thus, we instead work among states with c^†_M,o_M-1,0c_M,o_M-1,0 equal to 0.

Now, we bound e_1(1) by closely following the strategy of Ex. 4 of the Appendix, with a small modification to accommodate the extra time steps with 1-qubit gates.  The vertices of our graph can be labelled (k_1,…,k_M).   The one-dimensional configuration (Def. <ref>) has been chosen so that, at a fixed value of k_α,  k_α-1 is constrained to 1 of 4 consecutive values.  We relabel these 4 values using new variables i_α-1∈{0,1,2,3} that lie in correspondence with the 4 consecutive values of k_α-1.  For α = M, i_M ≡ k_M ∈{3, …, N-2 }.

The graph has the following edges in terms of the relabelled coordinates i_α.  The 2-qubit gates provide edges between (i_1,…,i_α-1=3,i_α=1,…,i_M) and (i_1,…,i_α-1-3=0,i_α+1=2,…,i_M).  The 1-qubit gates provide edges between (i_1,…,i_α=0,…,i_M) and (i_1,…,i_α+1=1,…,i_M) and between (i_1,…,i_α=2,…,i_M) and (i_1,…,i_α+1=3,…,i_M).  There are additional 1-qubit edges between (i_1,…,i_α,…,i_M) and (i_1,…,i_α+1,…,i_M)  for α=1 or α = M and at the beginning and end of the computation for other i_α.

We  define j_M(i_1,…,i_M) as in Ex. 3 and 4, ensuring ∑_i_1 = 0^3…∑_i_M-1 = 0^3 sign  ψ(i_1,…,i_M-1,j_M(i_1,…,i_M)) = 0 for each fixed i_M ∈{3,…, N-2}.  As in Ex. 4, we define P^(M)(i_1,…,i_M,t) = Q^(M)((i_1,…,i_M),t sign (j_M(i_1,…,i_M) - i_M)) for 0 ≤ t ≤ 6M | j_M(i_1,…,i_M) - i_M| and P^(M)((i_1,…,i_M),t) = (i_1,…,j_M(i_1,…,i_M)) for 6M | j_M(i_1,…,i_M) - i_M|≤ t ≤ T^(M).  

We define Q^(M) so that it establishes a path from (i_1,…,i_M-1,i_M) to (i_1,…,i_M-1,i_M+1).  If  i_M  mod  4 ≡ 1, i_M  mod  4 ≡ 2,  i_M  mod  4 ≡ 3, then there is a direct edge from (i_1,…,i_M) to (i_1,…,i_M+1), so we can set Q^(M)((i_1,…,i_M),t) = (i_1,…,i_M+1) for 1 ≤ t ≤ 6M.  Otherwise, we advance i_M using the following downward sweep, upward sweep procedure analogous to that of Ex. 4.

(1) If i_M-1≤ 1, set α = M-1 and perform a “downward sweep” of α as follows.   If (i_1(τ),…,i_α(τ),…,i_M(τ)) ≡ Q^(M)((i_1,…,i_M),τ) has i_α(τ) ≤ 1, determine if there is a direct edge from (i_1(τ),…,i_α(τ),…,i_M(τ)) to (i_1(τ),…,i_α(τ)+1,…,i_M(τ)) and then an edge to (i_1(τ),…,i_α(τ)+2,…,i_M(τ)) due to two 1-qubit gates.  If both edges are available, set Q^(M)((i_1,…,i_M),τ+1) = (i_1(τ),…,i_α(τ)+1,…,i_M(τ)), set Q^(M)((i_1,…,i_M),τ+2) = (i_1(τ),…,i_α(τ)+2,…,i_M(τ)), increment τ by 2, and halt the downward sweep of α.  If i_α(τ) ≤ 1 but no such direct connection to i_α (τ)+ 2 is available, examine i_α -1(τ).  If i_α-1(τ) ≥ 2, then we subtract 2 from i_α-1(τ) and add 2 to i_α(τ) using the paths shown in Table <ref>.  Decrement α and continue the downward sweep.  If the downward sweep reaches α=1, we must have i_1(τ) ≤ 1. Thus, there will always be an edge to (i_1(τ)+1,…,i_M) and then an edge to (i_1(τ)+2,…,i_M) due to two 1-qubit gates, and the downward sweep will inevitably halt at some α = A.

We then begin an “upward sweep," setting α = A+1.  If i_α-1(τ) ≥ 2 and i_α(τ) ≤ 1, then we subtract 2 from i_α-1(τ) and add 2 to i_α using Table <ref>.  We increment α and continue the upward sweep.  When we reach α = M, we make the final advance of i_M to i_M+1 using Table <ref>.

The downward sweep and upward sweep involve at most M values of α each, and each change in α requires at most 3 edges as given in Table <ref>.  Thus, τ is at most 6M when both sweeps are complete.  If τ < 6M, fix Q^(M)((i_1,…,i_M),τ) = (i_1,i_2,i_3,…,i_M-2,i_M-1,i_M+1) for all remaining τ up to 6M.  This completes the definition of Q^(M) when i_M-1≤ 1.

(2) If i_M-1≥ 2, begin with Table <ref>.   Then, follow the downward sweep and upward sweep procedures described in case (1).  Just omit the final advance – do not use Table <ref> a second time.

As in Ex. 4, we stitch multiple Q^(M) together to complete the definition.  We can then move on to P^(M-1) and Q^(M-1) and so on until we have a complete definition of P.  Using reasoning analogous to that of Ex. 4, we find that T = 6M(N-2)+6(M-1)(4)+6(M-2)(4)+6(1)(4) = 6M(N+2M-4) and B ≤ 2N+2(4+…+4) = 2(N+4M-4); we then apply Lem. <ref> to obtain e_1(1) = E_ϕ≥ 2ℰ/(12M(N+2M-4)+1)(4(N+4M-4)+1).  Combining this result with earlier results gives the desired bound on g_min.


Note that g_min is greater than order 1/N^4, assuming M ≤ N, consistent with the claims of <cit.>.  Thm. <ref> implies that an adiabatic evolution time T ≫ 1095M^2ℰ^2/g_min^3 ≈ 4 × 10^12 M^5 N^9/ℰ is sufficient for computation with H(λ).













Now, we bound the gap for a circuit with all-to-all qubit connectivity.  







  Consider the circuit used to define H(λ) in Def. <ref>.  Suppose that the 1-dimensional configuration of Def. <ref> is altered so that the 2-qubit gates U_A,2j+2;B,2j+2 of H(λ) give opportunities for every pair of qubits to interact via 2-qubit gates.  All pairs are treated democratically, consistent with an all-to-all physical connectivity of qubits.  In particular, the 2-qubit gates U_A,2j+2;B,2j+2 conform to the “round-robin tournament” pattern, presented in Table <ref>.    When 2j+2 = 4, qubits A=2 and B=3 undergo a 2-qubit gate U_A,4;B,4, as do qubits A=4 and B=5, qubits A=6 and B=7, and so on out to A=M-1 and B=M.  Qubit 1 undergoes a 1-qubit gate.  When 2j+2 = 6, qubits A=1 and B=2 undergo a 2-qubit gate U_A,6;B,6, as do qubits A=3 and B=4, qubits A=5 and B=6, and so on out to A=M-2 and B=M-1.  Qubit M undergoes a 1-qubit gate.  The pattern of gates at 2j+2 = 8 is obtained by keeping A = M fixed and shifting the other U_A,4;B,4 entries around the table in a clockwise fashion.  The pattern of gates at 2j+3 = 10 is obtained by keeping A = 1 fixed and shifting the other U_A,6;B,6 entries around the table in a clockwise fashion.  In general, the pattern of gates at 2j+2 ≥ 8 is obtained by keeping the top left A index fixed and shifting the other U_A,2j-2;B,2j-2 entries around the table in a clockwise fashion.

As in the 1-dimensional configuration of Def. <ref>, there are extra 1-qubit identity gates at the time steps near i=1 and i=N.  The qubits with even A have o_A = 1.  The qubits with odd A have o_A = 3.  The largest time step with 2-qubit gates occurs at i=N-3.  Any qubit index that appears as the first index A of a 2-qubit gate U_A,N-3;B,N-3 at time step N-3 has f_A = N.  The remaining qubits have final time step f_A = N-2.



The following theorem bounds the gap for this pattern of 2-qubit gates using Thm. <ref>.


For a circuit with the all-to-all configuration of gates specified in Def. <ref>, g_min obeys the lower bound given in Thm. <ref> for a 1-dimensional configuration of gates.



We refer to our Hamiltonian, describing a configuration of qubits with all-to-all connectivity, as H^all-to-all(λ).  We refer to the Hamiltonian of Thm. <ref>, describing a 1-dimensional configuration of qubits, as H^1d(λ).  We assume that Lem. <ref> has been applied to both H^1d(λ) and H^all-to-all(λ), so that only identity gates appear in each Hamiltonian.  We will show that the resulting two Hamiltonians are related by a unitary transformation in their penalty-free low-energy subspace, from which the proof immediately follows.

Define the unitary operator

    𝒲_A,k;B,k    =    ∑_i_A< k, i_B < k C^†_A,i_A C_A,i_A C^†_B,i_B C_B,i_B  +  ∑_i_A< k, i_B ≥ k C^†_A,i_A C_A,i_A C^†_B,i_B C_B,i_B
           + ∑_i_A ≥ k, i_B< k C^†_A,i_A C_A,i_A C^†_B,i_B C_B,i_B  + ∑_i_A ≥ k, i_B ≥ k C^†_A,i_A C_A,i_B C^†_B,i_B C_B,i_A

This operator swaps qubits A and B if both reside at time step k or later and has no affect on any other qubits.  Within the basis of eigenstates specified in Def. <ref>, it leaves invariant any 1-qubit or 2-qubit gate at time step k-1 or earlier as well as any associated penalty Hamiltonian.  It leaves h_A,B^k,k(ℐ⊗ℐ)+h_A^k+1(ℐ) + h_B^k+1(ℐ) invariant.  It transforms any 2-qubit gate between A and C or B and C at a time step k+2 or later: h_A,C^k+2,k+2(ℐ⊗ℐ) = 𝒲^†_A,k;B,k  h_B,C^k+2,k+2(ℐ⊗ℐ)𝒲_A,k;B,k.  Because 𝒲_A,k;B,k only swaps A and B if they are both at time step k or later, it does not perfectly transform the associated penalty Hamiltonian h_B,C^k+2,k+2(P) into h_A,C^k+2,k+2(P).  However, note that the penalty-free subspace of 𝒲^†_A,k;B,k(h_A,B^k,k(P) + h_B,C^k+2,k+2(P))𝒲_A,k;B,k is identical with the penalty-free subspace of h_A,B^k,k(P) + h_A,C^k+2,k+2(P).   Indeed, if i_A, i_B  < k or i_A, i_B ≥ k, 𝒲^†_A,k;B,k(h_A,B^k,k(P) + h_B,C^k+1,k+1(P))𝒲_A,k;B,k is identical with h_A,B^k,k(P) + h_A,C^k+1,k+1(P).  On the other hand, if i_A < k, i_B  ≥ k or  i_A ≥ k, i_B  < k, then 𝒲^†_A,k;B,kh_A,B^k,k(P)𝒲_A,k;B,k and h_A,B^k,k(P) both impose a penalty, so we are outside the penalty-free subspace.  It is sufficient to focus on the penalty-free subspace for our proof because g_min is associated with a state that lies in this subspace.

Suppose that we start with H^1d(λ) and apply the transformation (<ref>) to every pair in Table <ref> at time step 2j+2 = 6, except the leftmost pair (1,2).  Explicitly, we let 𝒲_k≡𝒲_M-2,k;M-1,k…𝒲_5,k;6,k𝒲_3,k;4,k and compute 𝒲^†_6 H^1d(λ) 𝒲_6.  The pattern of pairs from time step 2j+2 ≥ 8 in Table <ref> that characterizes H^1d(λ) changes to the pattern shown in Table <ref> once we use h_A,B^k,k(ℐ⊗ℐ) = h_B,A^k,k(ℐ⊗ℐ) to swap the label in the A row and the label in the B row.   The pairing of qubits at time step 2j+2 = 8 in 𝒲^†_6 H^1d(λ) 𝒲_6 is now identical with that of H^all-to-all(λ). 








Suppose that prior to applying the transformation 𝒲_6, we had applied the transformation (<ref>) to every pair in Table <ref> at time step 2j+2 = 8, except the leftmost pair (M,M-1).  That is, we define 𝒱_k≡𝒲_M-3,k;M-2,k…𝒲_4,k;5,k𝒲_2,k;3,k and compute 𝒲^†_6𝒱^†_8 H^1d(λ) 𝒱_8  𝒲_6.  The pattern in Table <ref> now changes to that in Table <ref>, which now agrees with the pairing in Table <ref> up to time step 2j+2 = 10.







More generally, the table associated with 

    𝒲^†_6𝒱^†_8 𝒲^†_10𝒱^†_12…𝒲^†_N-5𝒱^†_N-3 H^1d(λ) 𝒱_N-3𝒲_N-5…𝒱_12𝒲_10𝒱_8  𝒲_6.

agrees at all rows with Table <ref>.  To prove this, we note that 𝒲_6 converted row 2j+2=8 of Table <ref> to row 2j+2 = 8 of Table <ref>.  We note also that 𝒱_8  𝒲_6 effected the clockwise shift (the permutation that carries 3 to 2, 5 to 3, etc.) that turned row 2j+2=10 of Table <ref> into row 2j+2 = 10 of Table <ref>.  It follows that the product 𝒱_2j+2𝒲_2j…𝒱_8𝒲_6 gives repeated clockwise shifts, changing row 2j+2 of Table <ref> into  row 2j+2 of Table <ref> for even j.  It also follows that the product 𝒲_2j+2(𝒱_2j𝒲_2j-2…𝒱_8𝒲_6) changes row 2j+2 of Table <ref> into the second row of Table <ref>  and then applies repeated clockwise shifts, giving 2j+2 row of Table <ref> for odd j.

Thus, Hamiltonian (<ref>) agrees with H^all-to-all(λ) on their penalty-free subspaces, proving the theorem.


As in the one-dimensional case, Thm. <ref> implies that an adiabatic evolution time T ≫ 1095M^2 ℰ^2 /g_min^3 ≈ 4×10^12 M^5 N^9/ℰ is sufficient for computation in the case of all-to-all connectivity.



§ MEASURING OUTPUT


After we have carried λ to 1, we need to measure the output of the computation.  The following theorem bounds the probability that a measurement finds all qubits in the final (N-3)/2 + M time steps.  Since Def. <ref> specifies that all gates in these time steps are identity gates, the output of the computation can be correctly obtained if all qubits found in this range, even if they are not found at their final time step f_A.


Consider a circuit with the 1-dimensional configuration of gates specified in Def. <ref> or the all-to-all configuration of gates specified in Def. <ref>.  If λ = 1, the probability that a measurement finds all qubits at the last (N-3)/2 + M time steps is at least 1/3.



The argument parallels the proof of Lem. <ref>.  When λ=1, the probability that qubit M is at any time step i goes like 4^M-1 times a normalization constant.  This is equal for each of the N-3 possible time steps of qubit M, so the probability qubit M resides at any given time step is 1/(N-3).  In particular, the probability that it resides on the last (N-1)/2 - (M-1) time steps is at least (N-1)/2(N-3) - (M-1)/(N-3) > 1/3 since N ≥ 6M-1 in Def. <ref>.

If qubit M resides on the last (N-1)/2 - (M-1) time steps, then the 2-qubit gates in the circuit ensure that qubit M-1 resides on the last (N-1)/2 - (M-1) + 2 time steps, qubit M-2 resides on the last (N-1)/2 - (M-1) + 4 time steps, and so on.  We conclude that all qubits 1,…,M necessarily reside on the last (N-1)/2 - (M-1) + 2(M-1) = (N-1)/2 + (M-1) = (N-3)+M time steps.




§ CONCLUSION


We have provided a careful analysis of parallelized, universal adiabatic quantum computation.  Taking as input an arbitrary quantum algorithm described as a circuit of unitary gates, we defined a system and its Hamiltonian H(λ) possessing several key properties.  The ground state of H(λ) is non-degenerate.   The ground state of H(0) is a simple product state that seems straightforward to prepare.  The amount of time needed to adiabatically evolve from λ=0 to λ=1, such that the system remains almost completely in the instantaneous ground state of H(λ), is bounded by a polynomial function of the width and the depth of the circuit of unitary gates.  Thus, the computation can be executed efficiently.  Finally, the output of the quantum algorithm can be extracted with high-probability by measuring the ground state of H(1).  

We considered a case in which H(λ) has restricted connectivity derived from a circuit operating on a one-dimensional configuration of qubits.  We also considered a case in which H(λ) has all-to-all qubit connectivity.  

Throughout this paper, we made the assumption that the adiabatic quantum computation is proceeding in a noise-free, zero-temperature environment.  The problem of making adiabatic quantum computation fault-tolerant against thermal excitations is challenging and fascinating.  One suspects that the parallelized execution of gates integral to our H(λ) could play a role in such fault-tolerance since parallel gates are essential for fault-tolerance in the circuit model.



§ ACKNOWLEDGEMENTS


The author is very grateful for helpful remarks by Van Molino and by Stephen DiPippo.

apsrev4-1





§ APPENDIX


Example 1: 1-dimensional chain

Consider a 1-dimensional chain.  The set V_1={ i_1,…, i_N_1} is comprised of an even number of vertices V_1 = N_1.  (Note that i_1, a first vertex in V_1, is distinct from i_1, the first component of the vertex i.)  Edges join i_1 to i_2,  i_2 to i_3, …, and i_N_1 - 1 to i_N_1.  Given any non-vanishing ϕ( i) orthogonal to the ground state, we seek a lower bound on E_ϕ, the expectation value (<ref>) of its energy.  We will prove a bound by applying Lem. <ref> to a suitable path P( i,t).

Using the definitions in Lem. <ref>, note that N =  P = N_1/2 vertices.  Label the elements of N by i_n_1,…, i_n_N_1/2 and the elements of P by i_p_1,…, i_p_N_1/2.  Let us specify a path P( i,t) that carries even locations i_2 α in the chain to elements of N and odd locations i_2α-1 in the chain to elements of P.  In particular, for α=1,…,N_1/2, define P( i_2 α,t) =  i_2 α + t  sign (n_α - 2α) for 0 ≤ t ≤|n_α - 2 α| and  P( i_2 α,t) =  i_n_α for |n_α - 2 α| ≤ t ≤ N_1.  Similarly, define P( i_2 α-1,t) =  i_2 α-1 + t  sign (p_α - (2α-1)) for 0 ≤ t ≤|p_α - (2α-1) | and P( i_2α-1,t) =  i_p_α for |p_α - (2α-1) | ≤ t ≤ N_1.  Set T = N_1.    This P( i,t) satisfies the requirements of the Lemma.  A computation shows that B < N_1.  Thus, E_ϕ≥ 2ℰ/(2N_1+1)(2N_1+1).  Comparing to the exact result for the chain <cit.>,  2ℰ(1-cosπ/(N_1)) ≈ℰ(π/N_1)^2, we see that our bound underestimates its value by a factor of about 2 π^2.

To illustrate this construction with concrete numbers, let N_1 = 6, ϕ( i_1) = ϕ( i_2) = ϕ( i_3) = -1, and  ϕ( i_4) = ϕ( i_5) = ϕ( i_6) = 1 as shown in Fig. <ref>.  Choose Φ = 0, the median value of ϕ( i).  Then N = { i_1, i_2, i_3}, so n_1 = 1, n_2 = 2, n_3=3, and P = { i_4, i_5, i_6}, so p_1 = 4, p_2 = 5, and p_3=6.  The definition of P( i,t) follows Table <ref> where T = 6.  Note that the P( i,t) presented in the table satisfies all of the requirements of Lem. <ref>: (I) P( i,0) =  i, (II) P( i,t) advances by at most one edge at a time, (III) P( i,6) is one-to-one.  Finally, one sees that (IV) is satisfied from the final column of the table, if we pair i_1∼ i_2, i_3 ∼ i_4, and i_5 ∼ i_6.   The conclusion is that E_ϕ≥ 2ℰ/(13)^2 ≈ 0.012ℰ.  The exact result is 2ℰ(1-cosπ/6) ≈ 0.27ℰ.









Example 2: 2-dimensional chain

Consider a graph of the form V_1 ⊗ V_2 where V_1 = N_1 and V_2 = N_2 are even integers.  The vertices i∈ V_1 ⊗ V_2 have i_1 ∈{1,…, N_1 } and i_2 ∈{1,…, N_2 }.  We have i∼ i^' if i^'_1  = i_1 +1 and i^'_2  = i_2 or  if i^'_1  = i_1 and i^'_2  = i_2 +1.  Fig. <ref> shows an example with N_1 = N_2 = 4.  Given any non-vanishing ϕ( i) satisfying ∑_ i∈ Vϕ( i) = 0, we seek a lower bound on the expectation value of its energy, E_ϕ.

Our strategy is to define a path P^(2) to shuffle the i_2 values of vertices until ∑_i_1 = 1^N_1 sign  ψ(P^(2)( i,T^(2))) = 0 for each fixed i_2 ∈{1,…, N_2 }.  After the shuffling is complete, the problem can be solving using the method of Ex. 1 independently at each i_2.  The shuffling will use T^(2) = N_2 steps.

We specify P^(2) in terms a function j_2: {1,…,N_1 }⊗{1,…,N_2 }→{1,…,N_2 }.   This function j_2( i) assigns a new i_2 coordinate to each vertex in the graph.  Given j_2,  we set P^(2)( i,t) = (i_1,i_2 + t sign (j_2( i) - i_2)) for 0 ≤ t ≤ |j_2( i) - i_2| and P^(2)( i,t) = (i_1,j_2( i)) for |j_2( i) - i_2| ≤ t ≤ T^(2).  This P^(2) carries each vertex i=(i_1,i_2) to (i_1,j_2( i)).

We now define j_2( i).  Condition (III) of Lem. <ref> requires that P^(2)( i,T^(2)) be one-to-one, so we keep track of a pool of “remaining” vertices to ensure that the (i_1,j_2( i)) are distinct for distinct i=(i_1,i_2).  To start, the pool of remaining vertices is simply the whole set R_0 =  V_1 ⊗ V_2.  We proceed inductively from i_2 to i_2+1.   Start with i_2 = 1.   Let I_i_2^ P = {i_1|  (i_1,k_2) ∈ R_i_2 - 1⇒ (i_1,k_2) ∈ P}.  This is a set of i_1 values for which j_2(i_1,i_2) can be chosen somewhat indiscriminately since any remaining (i_1,j_2) will give a ψ(i_1,j_2) ≥ 0 irrespective of the choice of j_2.  Similarly, define the set I_i_2^ N = {i_1| (i_1,k_2) ∈ R_i_2 - 1⇒ (i_1,k_2)  ∈ N}.  Finally, I_i_2 = {1,…,N_1} -  I_i_2^ P∪ I_i_2^ N gives the i_1 values for which j_2(i_1,i_2) should be chosen more deliberately to target ψ(i_1,j_2) ≥ 0 or ψ(i_1,j_2) ≤ 0.    With the sets I_i_2^ P, I_i_2^ N, I_i_2 established, we can define j_2.  For each i_1 ∈ I_i_2^ P∪ I_i_2^ N, pick any j_2(i_1,i_2) such that (i_1,j_2) ∈ R_i_2 - 1.  For N_1/2  -   I_i_2^ N elements i_1 of  I_i_2, choose j_2(i_1,i_2) such that (i_1,j_2) ∈  R_i_2 - 1 and ψ((i_1,j_2)) ≤ 0  (i.e. (i_1,j_2) ∈  R_i_2 - 1∩ N).   For the remaining N_1/2  -   I_i_2^ P elements i_1 of I_i_2, choose j_2(i_1,i_2) such that (i_1,j_2) ∈ R_i_2 - 1 and ψ(i_1,j_2) ≥ 0 (i.e. (i_1,j_2) ∈  R_i_2 - 1∩ P).   Set R_i_2 = R_i_2-1∖{(i_1,j_2(i_1,i_2))| i_1 ∈{1,…,N_1}} to update the pool of remaining vertices.  Increase i_2 by 1 and continue the induction until j_2(i_1,i_2) is defined for all i_2 ≤  N_2.

With j_2(i_1,i_2) defined, and therefore P^(2) as well, we have ∑_i_1 = 1^N sign  ψ(P^(2)((i_1,i_2),T^(2))) = 0 for any fixed i_2 ∈{1,… N_2 }.  At each fixed i_2, we can use the method of Ex. 1 to define P^(1)_i_2(P^(2)((i_1,i_2),T^(2)),t) for 0 ≤ t ≤ T^(1) = N_1.  Our overall map is then obtained by stringing P^(1) and P^(2) together, so that P((i_1,i_2),t) = P^(2)((i_1,i_2),t) for 0 ≤ t ≤ T^(2)  and P((i_1,i_2),t) = P^(1)_i_2(P^(2)((i_1,i_2),T^(2)),t-T^(2)) for T^(2)≤ t ≤ T^(1)+T^(2).  This map has T = T^(1) + T^(2) = N_1+N_2.  Because P^(2) only uses edges that change i_2 and P^(1) only uses edges that change i_1, we compute that B = max  {N_1,N_2}.  Lem. <ref> implies that E_ϕ≥ 2/(2(N_1+N_2)+1)(2 max  {N_1,N_2}+1).  This should be compared to the exact result  2(1-cosπ/ max  {N_1,N_2}) ≈π^2/( max  {N_1,N_2})^2.

We illustrate this procedure in the case N_1 = N_2= 4 shown in Fig. <ref>.  A sample function ϕ( i) is shown in Fig. <ref> and listed in Table <ref>.    The median value of ϕ( i) is Φ=0.25, which is used to define ψ( i) = ϕ( i) - Φ displayed in Fig. <ref>. One finds that N = {(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,4),(4,1)} and P = {(1,1),(1,2),(1,3),(3,2),(3,3),(4,2),(4,3),(4,4)}.  Note that each has N_1 N_2/2 = 8 elements as expected since  Φ was chosen to be the median of ϕ( i).

To define j_2( i), we start with i_2 = 1 and let R_0 include all 16 vertices in the graph.  We find that I_1^ P is empty since there is no choice of i_1 that guarantees ψ((i_1,k_2)) ≥ 0 for all k_2.  On the other hand, I_1^ N = {2} since ψ(2,k_2) ≤ 0 for all k_2.  It follows that I_1 = {1,3,4}.  We can indiscriminately choose j_2(2,1)=1 since, for any choice we make, ψ(2,j_2(2,1)) ≤ 0.  We choose j_2(1,1) = 4 and confirm that ψ(1,j_2(1,1)) ≤ 0.  Then we choose  j_2(3,1) = 2 so  that ψ(3,j_2(3,1)) ≥ 0 and j_2(4,1) =2 so that  ψ(4,j_2(4,1)) ≥ 0.  Based on our choice of j_2(i_1,1), we now have ∑_i_1=1^4  sign ψ(i_1,j_2(i_1,1)) = 0 as desired.  We used vertices {(i_1,j_2(i_1,i_2)) | i_1 ∈{1,…,N_1}} = {(1,4),(2,1),(3,2),(4,2)}, so there are 12 remaining vertices in R_1={(1,1),(1,2),(1,3),(2,2),(2,3),(2,4),(3,1),(3,3),(3,4),(4,1),(4,3),(4,4) }.

We move on to i_2 = 2.  Now, I_2^ P = {1} because ψ(1,1), ψ(1,2), and ψ(1,3) are all non-negative while ψ(1,4) need not concern us since we already used (1,4) and thus (1,4) ∉ R_1.  We find that I_2^ N = {2} because ψ(2,2), ψ(2,3), and ψ(2,4) are all non-positive.  The remaining values of i_1 are in I_2 = {3,4}.  We can indiscriminately choose j_2(1,2) = 1 since (1,1) ∈ R_1 and j_2(2,2) = 2 since (2,2) ∈ R_1.  We choose j_2(3,2) = 3 and j_2(4,2) = 1.  Then, ψ(1,j_2(1,2)) ≥ 0, ψ(2,j_2(2,2)) ≤ 0, ψ(3,j_2(3,2)) ≥ 0, and ψ(4,j_2(4,2)) ≤ 0, which implies  ∑_i_1=1^4  sign ψ(i_1,j_2(i_1,2)) = 0 as desired.  We have 8 remaining vertices in R_2 = {(1,2),(1,3),(2,3),(2,4),(3,1),(3,4),(4,3),(4,4) }.

We go to i_2 = 3.  Now, I_3^ P = {1,4}, I_3^ N = {2,3}, and I_3 is empty.  We can indiscriminately choose j_2(1,3) = 2, j_2(4,3) = 3, j_2(2,3) = 3, and j_2(3,3) = 1.  Then, ψ(1,j_2(1,3)) ≥ 0, ψ(2,j_2(2,3)) ≤ 0, ψ(3,j_2(3,3)) ≤ 0, and ψ(4,j_2(4,3)) ≥ 0, which implies  ∑_i_1=1^4  sign ψ(i_1,j_2(i_1,3)) = 0 as desired.  We have 4 remaining vertices in R_3 = {(1,3),(2,4),(3,4),(4,4) }.

The final value is i_2=4.  We see that I_4^ P = {1,4}, I_4^ N = {2,3}, and I_4 is empty.  Given the remaining vertices in R_3, we have no choice remaining: j_2(1,4) = 3, j_2(4,4) = 4, j_2(2,4) = 4,  and j_2(3,4) = 4.  Then, ψ(1,j_2(1,4)) ≥ 0, ψ(2,j_2(2,4)) ≤ 0, ψ(3,j_2(3,4)) ≤ 0, and ψ(4,j_2(4,4)) ≥ 0, which implies  ∑_i_1=1^4  sign ψ(i_1,j_2(i_1,4)) = 0.  Table <ref> shows that the map from (i_1,i_2) to (i_1,j_2(i_1,i_2)) is one-to-one.  Fig. <ref> shows that shifts along the columns by P^(2) lead to ∑_i_1=1^4  sign ψ(P^(2)((i_1,j_2(i_1,i_2)),T^(2))) = 0 along each row.

Finally, we use the map P^(1) to shift along each row.  Defining the total map P( i,T), that strings together P^(1) and P^(2)  with  T=T^(1)+T^(2), we thus ensure sign ψ(P( i,T)) alternates along each row.  Lem. <ref> then implies that E_ϕ≥ 2ℰ/(17)(9) while the exact answer is 2ℰ(1-cosπ/ 4) ≈ℰπ^2/16.























Example 3: M-dimensional chain

Consider a graph of the form V_1 ⊗…⊗ V_M defined analogously to the graphs of Ex. 1 and Ex. 2.  To bound E_ϕ for this graph,  we can reduce one dimension at a time, just as we did in Ex. 2.

Define P^(M) with T^(M) = N_M in terms of j_M: {1,…,N_1 }⊗…⊗{1,…,N_M }→{1,…,N_M }.  Explicitly, set P^(M)( i,t) = (i_1,…,i_M + t sign (j_M(i_1,…,i_M) - i_M)) for 0 ≤ t ≤ |j_M(i_1,…,i_M) - i_M| and P^(M)( i,t) = (i_1,j_M(i_1,…,i_M)) for |j_M(i_1,…,i_M) - i_M| ≤ t ≤ T^(M).

To define j_M(i_1,…,i_M), let R_0 =  V_1 ⊗…⊗ V_M and start with i_M = 1.  Proceed inductively, letting I_i_M^ P = {(i_1,…,i_M-1)|  (i_1,…,i_M-1,k_M) ∈ R_i_M - 1⇒ (i_1,…,i_M-1,k_M)  ∈ P}, I_i_M^ N = {(i_1,…,i_M-1)| (i_1,…,i_M-1,k_M) ∈ R_i_M - 1⇒ (i_1,…,i_M-1,k_M)  ∈ N}, and I_i_M = {1,…,N_1}⊗…⊗{1,…,N_M-1} -  I_i_M^ P∪ I_i_M^ N.    For each (i_1,…,i_M-1) ∈ I_i_M^ P∪ I_i_M^ N, choose any j_M(i_1,…,i_M) such that (i_1,…,i_M-1,j_M) ∈ R_i_M - 1.  For N_1 … N_M-1/2  -   I_i_M^ N elements (i_1,…,i_M-1) ∈ I_i_M, choose a specific j_M(i_1,…,i_M) such that (i_1,…,i_M-1,j_M) ∈ N∩ R_i_M - 1.  For the remaining N_1 … N_M-1 /2  -   I_i_M^ P elements (i_1,…,i_M-1) ∈ I_i_M, choose a specific j_M(i_1,…,i_M) such that (i_1,…,i_M-1,j_M) ∈ P∩ R_i_M - 1.   Set R_i_M = R_i_M-1 - {(i_1,…,i_M-1,j_M(i_1,…,i_M))|(i_1,…,i_M-1) ∈{1,…,N_1}⊗…⊗{1,…,N_M-1}}.  Increase i_M by 1 and continue the induction until j_M(i_1,…,i_M) is defined for all i_M ≤  N_M.

After completing the definition of P^(M), we have ∑_i_1 = 1^N_1…∑_i_M-1 = 1^N_M-1 sign  ψ(P^(M)( i,T^(M))) = 0 for each fixed i_M ∈{1,…, N_M }.  We then define P^(M-1)_i_M(P^(M)( i,T^(M)),t) for each i_M ∈{1,…,N_M }.  The definition progresses like that of P^(M), with M replaced everywhere by M-1.  Then we have ∑_i_1 = 1^N_1…∑_i_M-2 = 1^N_M-2 sign  ψ(P^(M-1)_i_M(P^(M)( i,T^(M)),T^(M-1))=0 for each fixed (i_M-1,i_M).  We turn to P^(M-2)_i_M-1,i_M(P^(M-1)_i_M(P^(M)( i,T^(M)),T^(M-1)),t), then to P^(M-3)_i_M-2,i_M-1,i_M(P^(M-2)_i_M-1,i_M(P^(M-1)_i_M(P^(M)( i,T^(M)),T^(M-1)),T^(M-2)),t), and eventually to P^(2)_i_3,…,i_M(P^(3)_i_4,…,i_M((…),T^(3)),t) satisfying ∑_i_1 = 1^N_1 sign  ψ(P^(2)_i_3,…,i_M(P^(3)_i_4,…,i_M((…),T^(3)),T^(2))) = 0 for each (i_2,i_3,…,i_M).  The next step is to define P^(1)_i_2,…,i_M(P^(2)_i_3,…,i_M((…),T^(2)),t) for each fixed (i_2,…,i_M) by following the method of Ex. 1.  Finally, we string the series of maps P^(M)( i,t) to P^(1)_i_2,…,i_M(P^(2)_i_3,…,i_M(…,T^(2)),t) together into

    P( i,t) = {[                                                   P^(M)( i,t)                                                                                                                0≤ t ≤ T^(M);                          P^(M-1)_i_M(P^(M)( i,T^(M)),t-T^(M))                                                                                                    T^(M)≤ t ≤ T^(M)+T^(M-1);                                                             ⋮                                                                                                                            ; P^(1)_i_2,…,i_M(P^(2)_i_3,…,i_M((…),T^(2)),t-(T^(M)+…+T^(2)))                                                                                            T^(M)+…+T^(2)≤ t ≤ T^(M)+…+T^(1) ].

and set T = T^(M)+…+T^(1) = N_1 +… + N_M.  Noting that B = max  {N_1,…,N_M}, we find E_ϕ≥ 2ℰ/(2N_1 +… + 2N_M+1)(2 max  {N_1,…,N_M}+1) ≥ 2ℰ/(2 M max  {N_1,…,N_M}+1)(2 max  {N_1,…,N_M}+1).  Note that there is an extra factor of M in the denominator compared to the exact result 2ℰ(1-cosπ/ max  {N_1,…,N_M}) ≈π^2ℰ/( max  {N_1,…,N_M})^2.

Example 4: M-dimensional chain with 2-qubit gates


Consider the system depicted in Fig. <ref>, for which M=5 and N=6.  We study this system, generalized to arbitrary odd M and even N.  The vertices V of its graph can be labelled (k_1,…,k_M).   For odd α, k_α is constrained to lie in the interval {1,…,N}, and, for even α, k_α is constrained to lie in the interval {0,…,N-1}.  At every time step between 2 and N-1, 2-qubit gates act, so there are many additional constraints on the indices due to the requirement that the penalty Hamiltonian (<ref>) must vanish.

The graph has the following edges.  If k_M is even, there is an edge between (k_1,…,k_M) and (k_1,…,k_M+1).  If k_1 and k_2 are even, there is an edge between (k_1,k_2,…,k_M) and (k_1+1,k_2+1,…,k_M).  If k_3 and k_4 are even, there is an edge between (k_1,k_2,k_3,k_4,…,k_M) and (k_1,k_2,k_3+1,k_4+1,…,k_M).  This pattern holds out to qubit M-1: if k_M-2 and k_M-1 are even, there is an edge between (k_1,…,k_M-2,k_M-1,k_M) and (k_1,…,k_M-2+1,k_M-1+1,k_M).    On the other hand, if k_1 is odd, there is an edge between (k_1,…,k_M) and (k_1+1,…,k_M).  If k_2 and k_3 are odd, there is an edge between (k_1,k_2,k_3,…,k_M) and (k_1,k_2+1,k_3+1,…,k_M).  If k_4 and k_5 are odd, there is an edge between (k_1,k_2,k_3,k_4,k_5,…,k_M) and (k_1,k_2,k_3,k_4+1,k_5+1,…,k_M).  This pattern holds out to qubit M: if k_M-1 and k_M are odd, there is an edge between (k_1,…,k_M-1,k_M) and (k_1,…,k_M-1+1,k_M+1).   Finally, there are some extra 1-qubit gates near k_α=1 and k_α = N.  For odd α, there is an edge between (k_1,…,k_α=N-1,…,k_M) and (k_1,…,k_α=N,…,k_M).  For even α, there is an edge between (k_1,…,k_α=0,…,k_M) and (k_1,…,k_α=1,…,k_M). 

To bound the gap of the system, it is useful to relabel the vertices (k_1,…,k_M) by new indices (i_1,…,i_M).  First, stipulate that i_M ≡ k_M.  Now, by definition, the penalty (<ref>) vanishes on all the (k_1,…,k_M).  Given a fixed value of k_α,  one notices that k_α-1 constrained to just 2 possible time step values.    We relabel these 2 values i_α-1 = 0 or 1.  In particular, for α even, k_α = 0 implies k_α-1=1 or 2 while  k_α > 0 implies k_α-1 = 2 ⌊ (k_α+1)/2 ⌋ -1 or  2 ⌊ (k_α +1)/2 ⌋.  We define

    i_α-1 = {[                   k_α-1-2                   k_α = 0; k_α-1 - 2 ⌊ (k_α+1)/2 ⌋+1                    k_α >0 ]. .

For α odd,  k_α < N implies k_α-1 = 2 ⌊ (k_α)/2 ⌋ or 2⌊ (k_α)/2 ⌋ +1 while k_α = N implies k_α-1 =N-2 or N-1.  We define

    i_α-1 = {[ k_α-1 -  2 ⌊ (k_α)/2 ⌋                k_α < N;            k_α-1-(N-2)                k_α = N ]. .

Since i_α-1 = {0,1} and i_M ∈{1, …, N }, there are V =  2^M-1 N vertices (i_1,…,i_M) ∈ V.

The graph has the following edges in terms of the relabelled coordinates i_α.  The 2-qubit gates provide edges between (i_1,…,i_α-1=1,i_α=0,…,i_M) and (i_1,…,i_α-1-1=0,i_α+1=1,…,i_M).  The 1-qubit gates provide edges between (i_1,…,i_M-1,i_M) and (i_1,…,i_M-1,i_M+1) when i_M is even and between (i_1=0,…,i_M-1,i_M) and (i_1+1=1,…,i_M-1,i_M).  There are additional 1-qubit gate edges at the beginning and end of the computation.

We wish to bound the energy E_ϕ for some ϕ( i) orthogonal to the ground state, using Lem. <ref>.  It is therefore necessary to establish a map P^(M).  First,  we define j_M(i_1,…,i_M) so that, as in Ex. 3, ∑_i_1 = 0^1…∑_i_M-1 = 0^1 sign  ψ(i_1,…,i_M-1,j_M(i_1,…,i_M)) = 0 for each fixed i_M ∈{1,…, N}.  In contrast to Ex. 3, (i_1,…,i_M-1,i_M + t sign (j_M(i_1,…,i_M-1) - i_M)) is an invalid choice here for P^(M) because i_M cannot in general advance independently of i_M-1: there are constraints on the coordinates.  Taking these constraints into account, we need to choreograph the path Q^(M)((i_1,…,i_M),t) that takes (i_1,…,i_M-1,i_M) to (i_1,…,i_M-1,i_M+1).  We will then define P^(M) in terms of Q^(M).

Start by setting Q^(M)((i_1,…,i_M),t=0) = (i_1,…,i_M).  If i_M  mod  2 ≡ 0 or i_M = N-1, there is an edge between (i_1,…,i_M-1,i_M) and (i_1,…,i_M-1,i_M+1) via a 1-qubit gate.  We can then define Q^(M)((i_1,…,i_M),t) = (i_1,…,i_M+1) for 1 ≤ t ≤ 2M, and Q^(M) is successfully specified.  If i_M  mod  2 ≡ 1, the situation is more complicated since qubit M can only advance in tandem with qubit M-1.  We distinguish 2 cases.

(1) If i_M-1 = 0, set α = M-1 and τ =0, and perform a “downward sweep” of α as follows.  If (i_1(τ),…,i_α(τ),…,i_M(τ)) ≡ Q^(M)((i_1,…,i_M),τ) has i_α(τ) = 0, determine if there is a direct edge from (i_1(τ),…,i_α(τ) = 0,…,i_M(τ)) to (i_1(τ),…,i_α(τ)+1 = 1,…,i_M(τ)) due to a 1-qubit gate.  If such a direct edge is available, set Q^(M)((i_1,…,i_M),τ+1) = (i_1(τ),…,i_α(τ)+1 = 1,…,i_M(τ)), increment τ, and halt the downward sweep of α.   If i_α(τ) = 0 but no direct edge is available, examine i_α -1(τ).  If i_α-1(τ) = 1, then there is an edge from (i_1(τ),…,i_α-1(τ)=1,i_α(τ) = 0,…,i_M(τ)) to (i_1(τ),…,i_α-1(τ)-1=0,i_α(τ)+1 = 1,…,i_M(τ)) due to a 2-qubit gate.  Set Q^(M)((i_1,…,i_M),τ+1) = (i_1(τ),…,i_α-1(τ)-1=0,i_α(τ) +1 = 1,…,i_M(τ)).  Increment τ, decrement α, and continue the downward sweep.  If the downward sweep reaches α=1, we will have i_1(τ) = 0, and there will always be a direct edge from (i_1(τ)=0,i_2(τ),…,i_M(τ)) to (i_1(τ)+1=1,i_2(τ),…,i_M) due to a 1-qubit gate.  Thus, the downward sweep will inevitably halt.  When the downward sweep halts at some α = A, one finds that inevitably Q^(M)((i_1,…,i_M),τ) = (i_1,…,i_A-1,1,i_A,i_A+1,…,i_M-2,i_M), with i_A, i_A+1, …, i_M-2 each translated one slot over compared to the initial vertex (i_1,…,i_A-1,i_A,i_A+1,…,i_M-2,i_M-1,i_M).

We then begin an “upward sweep.”  If i_A = 1, we note that (i_1,…,i_A-1,1,i_A ,i_A+1,…,i_M-2,i_M)=(i_1,…,i_A-1,i_A,1,i_A+1 ,…,i_M-2,i_M).   If i_A = 0, then there is an edge from (i_1,…,i_A-1,1,i_A ,i_A+1,…,i_M-2,i_M) to (i_1,…,i_A-1,i_A,1,i_A+1,…,i_M-2,i_M) due to a 2-qubit gate.  Thus, we increment τ and set Q^(M)((i_1,…,i_M),τ) = (i_1,…,i_A-1,i_A,1,i_A+1 ,…,i_M-2,i_M).  For either value of i_A, we are left with Q^(M)((i_1,…,i_M),τ) = (i_1,…,i_A-1,i_A,1,i_A+1,…,i_M-2,i_M).  Repeat this process for α = A+1, moving the extra 1 to the right to obtain  Q^(M)((i_1,…,i_M),τ) = (i_1,…,i_A-1,i_A,i_A+1,1,…,i_M-2,i_M).  Continue the upward sweep of α until Q^(M)((i_1,…,i_M),τ) = (i_1,…,i_M-2,1,i_M).  Increment τ and make the final advance on the edge from (i_1,…,i_M-2,1,i_M) to (i_1,…,i_M-2,0,i_M+1): Q^(M)((i_1,…,i_M),τ) = (i_1,i_2,i_3,…,i_M-2,i_M-1 = 0,i_M+1).  At this point, τ is at most 2M.  If τ < 2M, fix Q^(M)((i_1,…,i_M),τ) = (i_1,i_2,i_3,…,i_M-2,i_M-1,i_M+1) for all remaining τ up to 2M.  This completes the definition of Q^(M) when i_M-1 = 0.

(2) If i_M-1 = 1, set τ = 1 and define Q^(M)((i_1,…,1,i_M),τ) = (i_1,…,i_M-2,0,i_M+1).  Then, follow the downward sweep and upward sweep procedures described in case (1).  Just omit the final advance since i_M has already been increased to i_M+1.

This definition of Q^(M)((i_1,…,i_M),t) for 0 ≤ t ≤ 2M ensures that Q^(M)((i_1,…,i_M),0) = (i_1,…,i_M) and Q^(M)((i_1,…,i_M),2M) = (i_1,…,i_M+1) and that Q^(M) advances one edge at a time.  A graphical illustration of Q^(M)((0,0,1,0,3),t) appears in Fig. <ref>, for the case M=5 and N=6 appearing in Fig. <ref>.



We will want to increment i_M by more than 1 and to decrement i_M as well.  So, we extend this definition of Q^(M)((i_1,…,i_M),t) to allow t > 2M and t < 0 by stitching multiple Q^(M) maps together:


    Q^(M)((i_1,…,i_M),t)= {[     Q^(M)((i_1,…,i_M+r),t-2Mr)                                             2Mr ≤ t ≤ 2M(r+1); Q^(M)((i_1,…,i_M-r),2Mr-| t |)                                            -2Mr≤ t ≤ -2M(r-1);                                ]. .


Using this definition of Q^(M), we fix T^(M) = 2 M N and write P^(M)((i_1,…,i_M),t) = Q^(M)((i_1,…,i_M),t sign (j_M(i_1,…,i_M-1) - i_M)) for 0 ≤ t ≤ 2M | j_M(i_1,…,i_M) - i_M| and P^(M)((i_1,…,i_M),t) = (i_1,…,j_M(i_1,…,i_M)) for 2M | j_M(i_1,…,i_M) - i_M|≤ t ≤ T^(M).   As desired, this definition of P^(M) implies ∑_i_1 = 0^1…∑_i_M-1 = 0^1 sign  ψ(P^(M)((i_1,…,i_M),T^(M))) = 0 for each fixed i_M ∈{1,…, N }.

With P^(M) specified, we proceed by analogy to Ex. 3 and define P^(M-1)_i_M(P^(M)((i_1,…,i_M),T^(M)),t) for each i_M ∈{1,…,N }.  The definition progresses like that of P^(M), with M replaced everywhere by M-1.  However, since i_M-1∈{0,1}, we have T^(M-1) = 2(M-1) and need not extend the definition of Q^(M-1)((i_1,…,i_M),t) beyond -2(M-1) ≤ t ≤ 2(M-1).  After P^(M-1) comes P^(M-2) and so on.  Following Ex. 3, we eventually define P((i_1,…,i_M),t) and T = T^(M)+…+T^(1) = 2M N + 2(M-1) +…+2(1) = M(2 N+ M-1).

To apply Lem. <ref>, we need the value of B.  Fixing our attention on a given edge, we first ask how many times Q^(M)((i_1,…,i_M),t) uses this edge for 0≤ t≤ 2M.  If i_M=N-1 or i_M  mod  2 ≡ 0, Q^(M) uses the edge between (i_1,…,i_M) and (i_1,…,i_M+1).  This edge is not used for any other starting vertex.  If i_M  mod  2 ≡ 1, things are more involved.  If i_M-1 = 1, Q^(M)((i_1,…,i_M),t) starts with the edge between (i_1,…,i_M-1,i_M) and (i_1,…,0,i_M+i_M-1).  This edge is used by at most 2 starting vertices: the first edge of the “downward sweep” used by the starting vertex i_1,…,i_M-1=1,i_M and the final edge of the “upward sweep” used by the starting vertex i_1,…,i_M-1=0,i_M.  In general, the downward sweep  involves edges between (i_1,…,i_α-1=1,i_α = 0,…,i_M) and (i_1,…,i_α-1-1=0,i_α +1 = 1,…,i_M). During the downward sweep, each edge can be determined using only knowledge of the previous edge used.  The downward sweep completes in (i_1,…,i_A,1,i_A+1,…,i_M+i_M-1), from which the starting vertex (i_1,…,i_M) can be uniquely extracted since i_M  mod  2 ≡ 0.  Since each edge of the downward sweep cascades to a unique end vertex from which the starting vertex (i_1,…,i_M) can be uniquely identified, two distinct starting vertices cannot use the same edge during their downward sweeps.  After the downward sweep, Q^(M) uses an upward sweep starting from (i_1,…,i_A,1,i_A+1,…,i_M+i_M-1).  Each edge used in the upward sweep can be determined using only knowledge of the previous edge used.  The upward sweep completes in (i_1,…,i_M+1), which is clearly a unique function of the original starting vertex (i_1,…,i_M).  Thus, 2 distinct starting vertices cannot use the same edge during their upward sweeps.  We conclude that a given edge can be used by at most 2 starting vertices – it can be used in the downward sweep of one starting vertex and the upward sweep of a second starting vertex.   This is true for all t up to 2M.  It is possible that the same edge will be used 2 more times whenever t increases by another 2M.  Since T^(M) = 2 MN,  we see that P^(M) can use a given edge at most 2N times.  For α < M,  there are 2 values of i_α rather than N values, so P^(α) can use an edge at most 2(2) times.  It follows that B ≤ 2 (N)+2 (2+…+2) = 2(N+2M-2).  Thus, Lem. <ref> implies that E_ϕ≥ 2ℰ/(2M(2N+M-1)+1)(4(N+2M-2)+1).

