Quantum Algorithm for Linear Systems of Equations

• p. 4 Section IV, displayed state after 'we transform it to a state which is close to'

  j,λj<1/κ

• p. 5 Appendix A, third paragraph

  eigenvalues ≥ 1/κ and the ill-conditioned part to be the rest

• p. 5 Appendix A, third paragraph

  to eigenvalues ≥ 1/κ and the ill-conditioned part to be the rest

• p. 4 Discussion, displayed state for ill-conditioned matrices

  j,λj<1/κ λ_j^{-1} β_j |u_j⟩|well⟩ + Σ_{j,λj≥1/κ} β_j |u_j⟩|ill⟩

Judge's note: Page 4 image shows the conditions as quoted. Appendix A (p5) defines the well-conditioned part as "eigenvalues ≥ 1/κ and the ill-conditioned part to be the rest", and filter functions (A3a)/(A3b) on p6 give f = 1/(2κλ) for λ ≥ 1/κ (well) and g = 1/2 for small λ (ill). The sentence before the display says only the well-conditioned part is inverted. No alternative convention is stated anywhere.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 4 Eq. (4)

  U†3T+1−t

• p. 4 Sec. III, Eq. (4)

  |t+2T+1 mod 3T⟩⟨t+2T| ⊗ U†_{3T+1−t}

• p. 4 Eq. (4)

  |t+2T+1 mod 3T⟩⟨t+2T| ⊗ U†3T+1−t

Only the authors can say what is right here.

Judge's note: Page 4 image checked: the sum is Σ_{t=1}^{T} and the subscript is 3T+1−t. The circuit is defined as U_1,…,U_T. With t=1 the printed index is 3T and with t=T it is 2T+1, so no defined gate is named. To uncompute U_T⋯U_1 (the text uses U^{3T}=I just below), the t-th factor must be U†_{T+1−t}, which gives the cycle product (U_1†⋯U_T†)(U_T⋯U_1)=I. The same t is the relative index in the ket/bra of this term, so reading it as an absolute clock value does not work. The formula is wrong as printed, but the construction holds once the index is corrected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 4 Section IV, preconditioner paragraph

  (AB)⃗c = B⃗b

Only the authors can say what is right here.

Judge's note: Page 4 image shows "(AB)c⃗ = Bb⃗" and κ(AB). Reworked: (AB)c = Bb gives c = B^{-1}A^{-1}Bb and Bc = A^{-1}Bb, which equals A^{-1}b only if A and B commute. Scalar-free counterexample: A = diag(1,2), B = [[0,1],[1,0]], b = (1,0): x = A^{-1}b = (1,0), but A^{-1}Bb = (0,1/2). No commutation assumption or relation between c and x is given. The next sentence (preparing B|b⟩) fits the left-preconditioned form with BA.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 6 Section A1, amplitude amplification paragraph

  is a constant fraction of π/4p̃

• p. 6 same paragraph, one sentence earlier

  would ideally be π/4√p̃

• p. 6 Appendix A.1, amplitude amplification paragraph

  is a constant fraction of π/4˜p

• p. 6 Appendix A.1, same paragraph

  would ideally be π/4√˜p

Judge's note: Page 6 image shows π/4√p̃ with a radical in one sentence and π/4p̃ without one in the next. The paragraph states O(1/√p̃) repetitions and O(κ) overall with p̃ = Ω(1/κ²); π/4p̃ would be O(κ²). It is not an extraction artefact.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Statement of Lemma 3

  where c = π2/2.

• p. 10 Proof of Lemma 3, case λ < 1/κ

  max |f ′|2 = π2/4 δ2/t2 0 κ2

Only the authors can say what is right here.

Judge's note: Pages 9–10 images checked. I reworked the counterexample with κ=1, κ'=2, λ=0.75, λ̃=0.74, so κ²δ²/t0² = 1e-4. θ=π/4 gives f=g=0.353553. θ̃=0.24π gives f̃=0.5·sin(43.2°)=0.342276 and g̃=0.5·cos(43.2°)=0.364487. The left side is 2.467e-4 and the right side is (π²/2)·1e-4·0.25 = 1.234e-4, so the inequality fails. The proof bounds the left side by (π²/2)κ²δ²/t0² and then needs f²+g²; even with the paper's 1/2 that gives c=π², and with the true 1/4 it gives c=2π². The lemma as stated is false. A larger O(1) constant repairs it, so the O(κ/t0) conclusions of (A20)–(A22) keep their form.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Proof of Lemma 3, case λ ≥ 1/κ, (A18)

  In this case g = 0, and we need to show that

Only the authors can say what is right here.

Judge's note: Pages 9–10 images checked. The sub-cases (λ̃≥1/κ; λ=1/κ with λ̃<1/κ; λ̃<1/κ<λ with either order of f, f̃) bound only |f−f̃|. Counterexample: κ=1, κ'=2, λ=1 (f=1/2, g=0), λ̃=0.49 < 1/κ' (f̃=0, g̃=1/2). The left side is 1/4+1/4 = 0.5. The right side is (π²/2)(0.51)²(1/4) ≈ 0.321. This is a different gap from C022, which concerns the constant in the λ<1/κ case. A larger O(1) constant repairs the bound, so Theorem 1's O(κ/t0) form survives, but the stated lemma does not follow as written.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 7 Paragraph after Theorem 1

  To prove (A5 assuming (A4)

• p. 7 same paragraph

  By (A4), the first post-selection leaves us with error O(κ/t0)

• p. 7 Appendix A.2, paragraph after Theorem 1

  To prove (A5 assuming (A4), observe

• p. 7 Appendix A.2, same paragraph

  By (A4), the first post-selection leaves us with error O(κ/t0).

Judge's note: Viewed page 7. The preceding sentence says the third claim is a corollary of the second, and the paragraph ends "as claimed in (A6)". (A4) is the no-post-selection bound, while the sentence concerns post-selection onto span{|well>,|ill>}, which is (A5). Both pointers are off by one and "(A5" lacks its closing parenthesis.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 7 Proof of Lemma 2, first display

  2κ2λ3√1 − 1/2κ2λ2

• p. 6 Eq. (A3a)

  1 2κλ when λ ≥ 1/κ

• p. 7 Appendix A.2, proof of Lemma 2, displayed derivative

  2κ2λ3p 1 −1/2κ2λ2

• p. 7 Proof of Lemma 2, derivative for λ>1/κ

  1/(2κ²λ³√(1−1/2κ²λ²)) |nothing⟩ − 1/(2κλ²) |well⟩

Only the authors can say what is right here.

Judge's note: Pages 6–7 images checked. For λ≥1/κ, (A3) gives f=1/(2κλ) and g=0, so the |nothing⟩ amplitude is √(1−1/(4κ²λ²)). Reworking: the derivative of −1/(4κ²λ²) is 1/(2κ²λ³). Multiplying by 1/(2√(1−1/(4κ²λ²))) gives 1/(4κ²λ³√(1−1/(4κ²λ²))). The printed expression is the derivative for f=1/(√2κλ). The printed squared norm 1/(2κ²λ⁴(2κ²λ²−1)) carries the same error. The correct squared norm is 1/(4κ²λ⁴(4κ²λ²−1))+1/(4κ²λ⁴). At λ=1/κ this is κ²/12+κ²/4 = κ²/3, and it decreases in λ, so the bound ≤κ² and Lemma 2 still hold.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 10 End of proof of Lemma 3

  Finally f(λ)2 + g(λ)2 = 1/2 for any λ ≤ 1/κ

• p. 6 Eqs. (A3a), (A3b)

  1 2 sin

• p. 10 Appendix A.2, end of proof of Lemma 3

  Finally f(λ)2 + g(λ)2 = 1/2 for any λ ≤1/κ, implying the result.

• p. 9 Lemma 3

  where c = π2/2.

Only the authors can say what is right here.

Judge's note: Pages 6, 9 and 10 images checked. (A3a)/(A3b) use the prefactor 1/2: for 1/κ'≤λ<1/κ, f²+g² = (1/4)(sin²+cos²) = 1/4. For λ<1/κ', f=0 and g=1/2, giving 1/4. At λ=1/κ, f=1/2 and g=0, giving 1/4. The two displayed bounds sum to (π²/2)κ²δ²/t0², which divided by 1/2 gives π² and divided by 1/4 gives 2π². This false step is the one that produces the wrong constant reported in C022, where the counterexample to the lemma statement is given.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 11 Sentence after (A32)

  Thus |αk|j|2 ≤ 64π2/δ2 whenever

• p. 8 Proof of (A4)

  |αk|j|2 ≤ 64π2/(λjt0 − 2πk)4 (proved in Section A 3)

• p. 11 Line after (A32)

  Thus |αk|j|2 ≤ 64π2/δ2 whenever |k − λjt0/2π| ≥ 1.

• p. 8 Proof of (A4)

  |αk|j|2 ≤ 64π2/(λjt0 − 2πk)4

Judge's note: Pages 8 and 11 images checked. Page 11 prints the exponent δ², and page 8 prints 64π²/(λjt0 − 2πk)⁴ and sums 64π²/δ⁴ · δ². Since δ ≥ 2π, the printed δ² bound is true but weaker, and it is not the δ⁴ bound that p.8 relies on, so the cross-reference is inconsistent. The evident fix is δ⁴.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Eq. (A19)

  = 1/2 − κ(λ̃ − 1/2) = κ(1/κ − λ̃)

• p. 9 (A19)

  = 1/2 − κ(˜λ − 1/2) = κ(1/κ − ˜λ)

• p. 9 (A19)

  = 1 2 −κ( ˜λ −1 2) = κ( 1 κ −˜λ)

Only the authors can say what is right here.

Judge's note: Page 9 image checked: the bracket shows 1/2, not 1/(2κ). With κ'=2κ, 1/κ−1/κ' = 1/(2κ), so (1/2)(λ̃−1/κ')/(1/κ−1/κ') = κλ̃−1/2. The expression is then 1/2−κλ̃+1/2 = 1−κλ̃ = κ(1/κ−λ̃). The printed middle term equals 1/2+κ/2−κλ̃, which matches only when κ=1. Numeric check with κ=2, λ̃=0.4: printed middle 0.7, right side 0.2. The final expression is correct.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Paragraph before (A12)

  f̃ := f̃(λ), g := g(λ) and g̃ = g̃(λ)

• p. 9 Proof of Lemma 3

  Remember that f̃ = f(λ − δ/t0)

Judge's note: Viewed page 9. The tilde is on the function, with plain λ as argument, so the definition is circular. (A10)–(A11) use f(λ̃_k), g(λ̃_k), and the Lemma 3 proof says "f̃ = f(λ − δ/t0)", which is f(λ̃). No separate function f̃ is defined anywhere.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 11 Eqs. (A28)–(A29)

  = −e i δ 2 (1− 1 T ) √2 cos( δ 2 ) T

• p. 11 (A29)–(A32)

  −e^{iδ/2(1−1/T)} √2 cos(δ/2) / T

Only the authors can say what is right here.

Judge's note: Page 11 image checked. Reworking: 1+e^{iδ} = 2cos(δ/2)e^{iδ/2}, and 1/(i√2T)·1/(−2i) = 1/(2√2T), since i·(−2i)=2. The prefactor is therefore cos(δ/2)e^{iδ(1−1/T)/2}/(√2T). Sanity check at δ=0: (A28) gives 2√2/π ≈ 0.90, matching the direct sum (√2/T)Σsin(π(τ+½)/T). The printed (A29) gives ≈ 4√2/π ≈ 1.80, which exceeds 1 for an amplitude. The sign is a global phase. The factor 2 only loosens the upper bound, so |α| ≤ 8π/δ² in (A32) still holds.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 13 Proof of Theorem 4

  let m = 2/δ log(2n)/log(log(n)) and ǫ = 1/100m

• p. 13 Proof of Theorem 4

  ≤ 2(1−δ/2)i2n0, implying that Tm ≤ n0.

Only the authors can say what is right here.

Judge's note: Page 13 image checked: m is printed as (2/δ)·log(2n)/log(log(n)). Reworking: (1−δ/2)^m ≥ exp(−(δ/2)m/(1−δ/2)) = (2n)^{−O(1/loglog n)}, so (1−δ/2)^m·2n0 = (2n0)^{1−o(1)}, which is far larger than log n0. Example with δ=1, n0=2^16 and base-2 logs: m=8.5 and 2^{−8.5}·2^{17} ≈ 362, against log2 n0 = 16. A repair with m = Θ((1/δ)log n) keeps 1/ε = O(log n), so the polynomial bound and Theorem 4 survive. As written, though, the 'implying' step does not follow, and the claim ε ≥ 1/log(n) would also need revisiting.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 14 Paragraph before Theorem 6

  taking 1/3ǫ2 samples gives us a ≥ 2/3 probability of obtaining an estimate within ǫ/2 of µ

• p. 14 matrix inversion estimation paragraph

  taking 1/3ǫ2 samples gives us a

• p. 14 paragraph before Theorem 6

  taking 1/3ǫ2 samples gives us a ≥2/3 probability

Only the authors can say what is right here.

Judge's note: Page 14 image checked: the text reads 1/3ǫ². Reworking: the variance of the mean is ≤ 1/(4n), so Pr(|mean−µ| ≥ ǫ/2) ≤ (1/(4n))/(ǫ²/4) = 1/(nǫ²). This is 3 at n = 1/(3ǫ²) and 1/3 at n = 3/ǫ². At µ=1/2 the standard deviation is √3ǫ/2, so ǫ/2 is about 0.58 SD, and the normal approximation gives a success probability of about 0.44 < 2/3. The stated count does not give the stated probability. The Õ(log(N)κ²s²/ǫ³) scaling is unaffected.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send