## 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.