A Fast Quantum Mechanical Algorithm for Database Search

• p. 6 Corollary 2.1 statement and proof

  then for N ≥ 9 the condition

• p. 6 Statement of Corollary 2.1 (left column)

  Then after applying the diffusion transform both k1 and l1 are positive numbers.

Only the authors can say what is right here.

Judge's note: Page 6. Theorem 2 gives l1 = (2/N)k + ((N−2)/N)l. Counterexample, which I checked: N = 4 (= 2², allowed by Section 2), k = −1.5, l = 1, so |k/l| = 1.5 < 2 = √N and the hypotheses hold. Then l1 = 0.5·(−1.5) + 0.5·1 = −0.25 < 0, which contradicts the stated conclusion. The proof itself adds the restriction "for N ≥ 9", which the statement leaves out. Theorem 3 uses the corollary only for "non-trivial N", so adding N ≥ 9 to the hypotheses repairs it.

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 4, first paragraph

  sion transform D as used in step (ii)(a) of the algorithm..

• p. 3 Section 3, step (ii)(b)

  (b) Apply the diffusion transform D which

• p. 4 Section 4, paragraph before Figure 1

  equivalent to the diffu-sion transform D as used in step (ii)(a) of the algorithm

• p. 4 Section 4, first paragraph

  diffusion transform D as used in step (ii)(a) of the algorithm

Judge's note: Page 3, Section 3: (ii)(a) is "In case C(S)=1, rotate the phase by π radians" and (ii)(b) is "Apply the diffusion transform D". Page 3 also says "step (ii) (a) is a phase rotation transformation". So the pointer on page 4 names the wrong sub-step. The doubled full stop is handled separately in C003.

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. 5 Section 5, paragraph before Theorem 1

  R as defined in theorem 2 is a phase rotation matrix

• p. 5 Section 5, paragraph before Theorem 1

  as defined in theorem 2 is a phase rotation matrix

Judge's note: Page 5: the statement of Theorem 1 defines R_ij = 0 for i≠j, R_ii = 1 for i = 0 and R_ii = -1 for i≠0. Theorem 2 (page 6) concerns the amplitudes after D is applied and does not mention R.

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. 8 References, [DH96]

  lanl preprint, quant-ph/9602016.

• p. 8 References, [BCDP96]

  quant-ph/9602016).

• p. 8 References, [BCDP96]

  quant-ph/9602016

• p. 8 References, [DH96]

  lanl preprint, quant-ph/9602016

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: which of the two entries is wrong (reviewers say Durr–Hoyer is quant-ph/9607014). The page 8 image confirms that both entries print the same identifier for two different papers, so at least one is wrong within the reference list itself.

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. 8 References, [DJ92]

  Proceedings Royal Society of London, A400, 1992, pp. 73-90.

• p. 8 References, [Deutsch85]

  Society London Ser. A, 400, 1985,

• p. 8 Reference [DJ92]

  A400, 1992, pp. 73-90.

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: the correct citation of Deutsch–Jozsa 1992 (reviewers give Proc. R. Soc. Lond. A 439, 553–558). Within the page 8 reference list, one volume number assigned to two years seven years apart is inconsistent, so the [DJ92] volume and pages are queried.

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 4, definition of inversion about average

  amplitude in each state increases (decreases) so that after this operation it is as much below (above) α as it was above (below) α before the operation.

Judge's note: Page 4, left column. Under v -> 2α - v (the paper's own form, A + (A - v_i), right column), the amplitude increases exactly when v < α, and it then ends α - v above α. As printed, the main clause says an increasing amplitude ends below α after having been above it, which cannot happen. Figure 1 shows the correct behaviour. The fix is to read "as much above (below) α as it was below (above) α".

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 Corollary 2.2, proof, second displayed equation

  (N − 1)l1² = 4(N − 1)²/N² k²

• p. 6 Corollary 2.2, proof, 'Similarly' equation

  (N − 1)l_1^2 = 4(N − 1)^2/N^2 k^2

• p. 6 Proof of Corollary 2.2, second displayed equation (right column)

  (N−1)l1^2 = 4(N−1)^2/N^2 k^2

Only the authors can say what is right here.

Judge's note: Checked on the page 6 image: the k² term carries (N−1)². My own working: l1 = (2/N)k + ((N−2)/N)l, so (N−1)l1² has k² coefficient (N−1)·4/N², l² coefficient (N−1)(N−2)²/N², and kl coefficient 4(N−1)(N−2)/N². The printed l² and kl terms match this; the k² term has an extra factor (N−1). With the corrected coefficient, the k² coefficients add to [(N−2)² + 4(N−1)]/N² = 1 and the kl terms cancel, so the corollary holds. With the printed coefficient the sum is not 1 (for N = 4 it is 40/16). This is a faulty intermediate step; the stated corollary stands.

Second check: another model agreed · checked by hand

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