Quantum Algorithms Via Linear Algebra
Note: The Second Printing (2016) by MIT Press resolves all of the first group of issues.
Errata, Clarifiers, and Amplifiers from the First Printing
-
Page 12, ex. 2.6: The function f is monotone. Update 9/12/15: still
not enough for the forward direction. See
this GLL post,
and maybe change the problem to that of making a rigorous version of my sketch of
the <== direction given there.
-
Page 21, diagram of 4-cycle: Labels '3' and '4' should be switched.
-
Page 25, ex. 3.12: The commutators are group commutators, not the
ring commutators of the form AB - BA which are fundamental
elsewhere in quantum theory.
-
Page 25, ex. 3.17: Strike the words "and its close relative V"
and change the
next sentence to "T is often called the π/8 gate; ..." That the
Clifford group includes V but not T trumps any other similarity.
-
Page 42: the sentence after the large matrix needs to append the words,
"divided by \sqrt{N}."
-
Page 47, ex. 5.6: The recursive equation does not hold as written (clearly
not for N=4); we are checking a discrepancy between notation for "K_n"
and "D_{N/2}" between our source and our book. A suggested fix is to use
K_n-inverse in place of K_n (or rather, redefine K_n accordingly in problem
4.9 on page 39), and in problem 5.5, to define D_N (not "D_n") as the top
half of the second column of F_{2N}, multiplied by \sqrt{2N}.
-
Pages 59--60: In Section 6.7 we refer to "b(xy)" etc. as a
"vector" when one argument is fixed and the other is not---like saying
"f(x)" or "f(x,y)" to mean the function not a single value.
-
Page 60, ex. 6.6: The reference is to Ch. 3's exercises 3.15--3.16 (where
the R and T letters in the equation for U should
be bold), and the latter two occurrences of CR_x should just be R_x.
-
Page 61, ex. 6.9-6.10: Again, these are group commutators. In 6.10 the
intent was to say here that Hadamard and CS simulate V.
-
Page 72, ex. 7.6: Backward reference to exercises 6.6--6.8 should be noted.
-
Page 81, end of first equation in first proof, "st" should be
tu.
-
Page 84, Figure 8.4: Although a global -1 multiplier doesn't matter to
the measurement, the fourth member for iY should be flipped
upside down, so this case too yields two "Phils" at the exit point 11.
-
Page 101: The first equation is missing ω^{xu} in its
third of four equated terms. Then
starting from the second line of equations in the middle
of the page: the exponent of ω on the right should be xrk
not rk. Next line, denominator should have
ω with exponent xr in place of ωxr,
and likewise on the first equation line after the following text.
-
Page 103: In lemma 11.3 and the last line of its proof,
r^2 should be divided not multiplied.
-
Page 106, line 3: "larger than" should be "smaller than".
-
Page 111, "half the time a will be a QR modulo one of the primes
and not the other": The point is that a is sampled from {1,...,M-1}
not {1,...,p-1} or {1,...,q-1}. Multiples of p or q are filtered out
by the initial gcd(a,M) step. Among the remaining values,
a acts like an independent draw from both {1,...,p-1} and {1,...,q-1}
simultaneously.
-
Page 112: At top, (q-1)/2m parses as ((q-1)/2)m, similarly for p and \ell.
In the paragraph beginning "Let's prove that", the "k" can be the same as
in the previous paragraph or some earlier value.
-
Page 118, sentence beginning "One idea": Clearer is to say the idea
is to maintain t_k computations at once so you always have a spare copy
before any measurement. Anyway this is a "straw man"---it doesn't work.
-
Page 123, bottom: equation (11.2) is in section 11.4 not 11.5.
Remaining Errata
-
Page 30, first paragraph of section 4.2: The final count should be
3x10 + 10 = 40 applications to arguments, not 35. [Evidently the
5 in MAJ(x1,x2,x3,x4,x5) was confused with the 10 in AND(of 10 ORs).]
-
Page 34, line 3: "Once can say..." should be "One can say..."
-
Page 60: exercise 6.2 should come after 6.3 and both should
refer to the group of
transformations generated by a Hadamard gate on any qubit line, as well
as the permutations.
-
Page 61, exercise 10: The "as well as the Toffoli gate" part was
meant to refer to the diagram that was placed in exercise 7.5 on page 72.
-
Page 97, last three lines: "r divides M-1" should be "r divides the Euler
totient of M"---i.e., r divides (p-1)(q-1) where we don't yet know p and q.
-
Page 148 middle of brace for definition of J_0[...] = -1: "B" and "D" should be "Y" and "Z" again.