Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation

• p. 2 Introduction

  efficiently simulated by standard quantum computers [9, 13]

• p. 3 Section 1.1

  one direction of the equivalence is already known [13,9]

• p. 3 Section 1.1

  this extends the result of [9, 14]

• p. 10 Section 3, first paragraph

  the other direction was shown in [14,9]

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: which of the two Farhi papers contains the simulation argument. In the reference list, [13] is Farhi et al., Science 292:472 (random NP-complete instances) and [14] is Farhi, Goldstone, Gutmann, Sipser, quant-ph/0001106. Page 2 cites [9,13], p. 3 cites [13,9], and p. 10 cites [14,9] for the same statement. The p. 3 phrase 'extends the result of [9,14]' concerns sparse Hamiltonians, but it is again attributed to [14]. The inconsistency is internal to the paper; only the authors can say which citation is meant.

Second check: another model agreed

• p. 29 Reference [22]

  Number 47 in Graduate Series in Mathematics. AMS

• p. 29 reference [22]

  Graduate Series in Mathematics

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: Kitaev–Shen–Vyalyi is vol. 47 of the AMS series 'Graduate Studies in Mathematics'. The p.29 image shows 'Graduate Series in Mathematics'.

Second check: another model agreed

• p. 5 Section 1.3, overview

  more specifically, we show it is larger than 1/L2

• p. 14 End of proof of Lemma 3.5

  ∆(HS0) ≥µ/(2 · (6)2L2)

• p. 14 End of proof of Lemma 3.5

  ∆(HS0) ≥µ/(2 · (6)2L2). Finally, notice that µ = 1 −λ ≥1

Judge's note: Page 14: 'By Theorem 2.5 ... larger than 1/(2·(6)²·L²) ... ∆(HS0) ≥ µ/(2·(6)²L²) ... µ = 1−λ ≥ 1/2'. The s<1/3 case gives 1/3. Nowhere is a bound of 1/L² itself proved. The same overview paragraph on p. 5 later says Ω(1/L²), which matches the proof. The specific constant is an overstatement.

Second check: another model agreed

• p. 20 Proof of Theorem 3.15

  evolves according to H′(s) for T = θ(ǫ−δL7+3δ)

• p. 20 Proof of Theorem 3.15, running time

  O(ǫ−(2+δ)L14+3δ)

• p. 20 Proof of Theorem 3.15, paragraph after Lemma 3.19

  T = θ(ǫ−δL7+3δ)

• p. 20 Final running time of Theorem 3.15

  O(ǫ−(16+4δ)L14+3δ)

Only the authors can say what is right here.

Judge's note: Eq. (2) on p. 8 requires T ≥ Ω(‖·‖^{1+δ}/(ǫ^δ ∆^{2+δ})). With norm O(L) (stated on p. 20) and ∆ = Ω(L^-3), the exponent is (1+δ) + 3(2+δ) = 7+4δ. The 5-local check gives 2(2+δ) = 4+2δ, which matches Claim 3.9. The later exponents (ǫ^-(2+δ)L^{14+3δ} and ǫ^-(16+4δ)L^{14+3δ}) are consistent with the printed T. Because δ > 0 is arbitrary, rescaling δ recovers the final 'for any fixed δ' bound, so Theorem 3.15 stands; the intermediate T is faulty as printed.

Second check: another model agreed

• p. 12 Proof of Lemma 3.5, case s < 1/3

  Moreover, for any i̸ = 1, HS0(s)i,i > 5/6 and P j̸=i HS0(s)i,j < 1/6

• p. 12 case s < 1/3 in proof of Lemma 3.5

  Moreover, for any i ̸= 1, HS0(s)i,i > 5/6 and P j̸=i HS0(s)i,j < 1/6.

• p. 12 case s<1/3 in proof of Lemma 3.5

  HS0(s)i,i > 5/6 and P j̸=i HS0(s)i,j < 1/6

Only the authors can say what is right here.

Judge's note: Reworked from Eqs. (7)–(8) on p. 12. HS0(s) = (1−s)HS0,init + s·HS0,final. Each interior row has diagonal (1−s)·1 + s·1 = 1 and two off-diagonal entries −s/2, so Σ|a_ij| = s. Taking s = 0.3 gives radius 0.3 > 1/6, so the radius bound is false as printed (the signed sum −s < 1/6 is trivial and is not what Lemma 3.6 uses). Row 1 (radius s/2) and the last row (diagonal 1−s/2, radius s/2) are fine. Correct discs: [0, s] for row 1 and [1−s, 1+s] for interior rows, with 1−s > 2/3. So the conclusions 'all other eigenvalues > 2/3' and 'gap ≥ 1/3' still hold. Faulty step, stated result stands.

Second check: another model agreed

• p. 14 Section 3.1.3, paragraph after Claim 3.9

  it is much smaller than 1/L, the weight of |α(L)⟩in |η⟩

Judge's note: Eq. (1) on p. 5 has the 1/sqrt(L+1) normalisation over ℓ = 0..L. On p. 14, 1/L appears twice as if exact. This is an approximation that does not affect the O(L) repetition argument.

Second check: another model agreed

• p. 16 Proof of Lemma 3.12

  then HSj,input −M is positive definite

Only the authors can say what is right here.

Judge's note: Page 16: HSj,input is diagonal, with top-left entry equal to the number of 1s in j and all other entries zero, and M = diag(1,0,…,0). The difference has at least L zero eigenvalues, and for j with a single 1 it is the zero matrix, so it is not positive definite. The lower bound on the ground energy needs only semidefiniteness, so the result stands.

Second check: another model agreed

• p. 17 Proof of Lemma 3.12, first paragraph

  the two ground spaces satisfies cos(θ) ≤1 −1/L by the monotonicity property

• p. 17 proof of Lemma 3.12, first paragraph

  the two ground spaces satisfies cos(θ) ≤1 −1/L by the monotonicity property of the ground state

Only the authors can say what is right here.

Judge's note: M = diag(1,0,…,0) (p. 16) has ground space span{γ1..γL}. For a unit ground state α of HS0(s), cos θ = sqrt(1−α0²). Monotonicity (Claim 3.7) gives α0² ≥ 1/(L+1), so cos θ ≤ sqrt(L/(L+1)). At s = 1 every row of matrix (8) sums to 0, so the ground state is uniform and cos θ = sqrt(L/(L+1)) exactly. That exceeds 1 − 1/L for every L ≥ 1 (L = 2: 0.816 > 0.5). Using sin²(θ/2) ≥ 1/(4(L+1)) instead still gives Ω(L^-3), so Lemma 3.12 stands with a different constant.

Second check: another model agreed

• p. 26 definition of H''_ℓ, ℓ=2nr+k (and cases k=n, k=1)

  restriction of this Hamiltonian to the 8 dimensional space spanned by

• p. 27 Claim 4.4

  For any 1 ≤ℓ≤L, H′′ S,ℓ= HS,ℓ.

Only the authors can say what is right here.

Judge's note: p.26: the basis is listed as four (upper ⇕, lower ↕) states, then four (upper ⇕, lower ⇕) states. Taking rows and columns in that order, the lower-left block −U† maps the first group (γ_{ℓ−1}) into the second (γ_ℓ). Reworking it: ⟨γ_ℓ|H|γ_{ℓ−1}⟩ = −⟨Uα|U†α⟩ = −⟨α|U†U†|α⟩. This is not −1 for a general non-Hermitian U, whereas Claim 4.4 (p.27) requires −1, consistent with the earlier H_ℓ, where the forward term is −U_ℓ⊗|110⟩⟨100|^c. The k=n and k=1 matrices have the same layout. The paper never states that the matrix rows follow the listed basis order, and if the order is reversed the matrix is correct. So this is a convention-dependent slip that only the authors can settle. The stated Claim 4.4 holds once U and U† are swapped.

Second check: another model agreed

• p. 1 title block

  February 1, 2008

Judge's note: The page-1 crop shows both the 2008 date and the vertical arXiv stamp '26 Mar 2005'. This is most likely a \today date regenerated when arXiv rebuilt the PDF, not an authorial claim. It is cosmetic.

Second check: none (judge only)

• p. 5 Section 1.3, last paragraph before 'The above scheme'

  if the clock is in the state |1ℓ⟩, the computational qubits carry the result of the circuit

Judge's note: The p. 5 image shows a lowercase ℓ superscript. Eq. (1) gives |α(ℓ)⟩⊗|1^ℓ0^{L−ℓ}⟩ for every ℓ, and Section 3.1.3 (p. 14) correctly says the outcome must be ℓ = L. 'Otherwise, start from scratch' confirms that one specific outcome is meant.

Second check: none (judge only)

• p. 10 Theorem 2.5 heading

  Theorem 2.5 (The conductance bound [34]))

Judge's note: The crop shows one '(' and two ')'. Compare Theorem 2.1 on p. 8, where '(The Adiabatic Theorem (adapted from [29]))' has two opening parentheses and is therefore correct.

Second check: none (judge only)

• p. 17 Section 3.2.1, definition of H′L

  H′ L := I ⊗|10⟩⟨10|c L−1,L −Uℓ⊗|1⟩⟨0|c L

• p. 17 Section 3.2.1

  H′ L

• p. 17 Section 3.2.1, definition of H'_L

  −Uℓ⊗|1⟩⟨0|c

• p. 17 definition of H'_L

  −Uℓ ⊗|1⟩⟨0|c L

Judge's note: The p. 17 image shows subscript ℓ on the first U, but U†_L in the same line. ℓ is unbound in this boundary definition, and H'_1 correctly uses U1.

Second check: none (judge only)

• p. 17 Section 3.2.1

  For the boundary cases l = 1, L we define

Judge's note: The p. 17 image shows an italic 'l', while the surrounding text uses ℓ throughout.

Second check: none (judge only)

• p. 20 Proof of Lemma 3.19

  is at least 1 −δ, with δ = K2 (b−a)(J−2K) = O(L−1ǫ2)

• p. 20 Proof of Theorem 3.15

  T = θ(ǫ−δL7+3δ)

Judge's note: The p. 20 image shows both uses of δ within one paragraph. δ is the fixed exponent from Theorem 2.1 (p. 8). The meaning can be recovered from context, but the symbol clash is a notational ambiguity.

Second check: none (judge only)

• p. 20 Proof of Theorem 3.15

  T = θ(ǫ−δL7+3δ)

Judge's note: The p. 20 image shows a lowercase θ. The same symbol θ denotes the angle between ground spaces in Lemma 3.14 and the proof of Lemma 3.12 (pp. 16–17).

Second check: none (judge only)

• p. 25 Section 4.4.2, after the upward H″ℓ

  The remaining terms in each line correspond to |100⟩⟨110|c and |100⟩⟨110|c in Hℓ

• p. 25 end of text before footnote 8

  correspond to |100⟩⟨110|c and |100⟩⟨110|c in Hℓ

Judge's note: The p.25 image shows the identical term printed twice. The earlier H_ℓ (text line ~561) contains both −U_ℓ⊗|110⟩⟨100|^c and −U_ℓ†⊗|100⟩⟨110|^c.

Second check: none (judge only)

• p. 26 After the definition of H″2nr+1

  where the first term shows the restriction an operator acting on the particle (1, r)

Judge's note: Confirmed on the p.26 page image.

Second check: none (judge only)

• p. 28 Reference [2]

  computation is equaivalent to standard quantum computation

• p. 28 References [2]

  is equaivalent to standard quantum computation

• p. 28

  computation is equaivalent to standard quantum computation, in Proc. 45th FOCS

Judge's note: Confirmed on the p.28 image crop. The paper's own title spells it 'Equivalent'.

Second check: none (judge only)

• p. 28 Acknowledgments

  Leonid Gurvitz

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: the usual published spelling of the researcher's name is 'Leonid Gurvits'. The image shows 'Gurvitz'. Transliteration variants exist, so only the authors can confirm.

Second check: none (judge only)