Quantum Algorithms Via Linear Algebra
Errata, Clarifiers, and Amplifiers

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 4cycle: 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_ninverse 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 5960: In Section 6.7 we refer to "b(xy)" etc. as a
"vector" when one argument is fixed and the other is notlike 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.153.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.96.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.66.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,...,M1}
not {1,...,p1} or {1,...,q1}. 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,...,p1} and {1,...,q1}
simultaneously.

Page 112: At top, (q1)/2m parses as ((q1)/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.