## typo expo

Quantum computing has been my latest passion since I converted to data science a few months ago. This was partly due to my thirst of quick energy like Mike Sipser’s wonderful theory of computation book, and partly to my heroic friend Yan Zhang’s encouragement through our informal reading group of the Feynman reincarnate Scott Aaronson’s lecture notes on quantum computing since Democritus. While it is truly remarkable that Democritus was able philosophically to intuit the existence of atoms, well ahead of its scientific discovery, it was put in the title perhaps mainly for theatrical effect. But to be fair, the book/lecture set stands out among the mundane crowd to a good extent for its excellent mix of philosophical discussion with actual formulas/proofs.
But my point today is to help the readers discover a supplementary but independent text for understanding later chapters of Aaronson. It’s possible that Scott mentioned it in his required reading list, but I am too lazy to check. The name of the book is Classical and Quantum Computations, written beautifully by three Russian guys, and faithfully translated into English (with occasional lapse of ambiguity detailed below).
The main advantage of the said text is that it’s short, but not terse as is typical of GTM series. From reading Part II of the book on quantum computing (part I is all on classical computation theory), I was able to instantly pick out the important topics I want to learn, mainly consisting of the following four: Grover’s, Simon’s, and Shor’s algorithm, then an embedded 3! exercise on quantum teleportation. If I want to impress someone with my knowledge of QC, my best bet would be to give a demo of Simon’s algorithm for the case of one dimensional subgroup $\{0,s\} \subset \mathbb{Z}_2^n$. However since all but Shor’s algorithm require some super-polynomially powerful oracle, this might still not be convincing enough but rather feel like a handicapped game against classical machines.
My goal today is to expose two subtle points of inaccuracies in the text, not to disparage the authors, but merely for my own record and for those perfectionists like me who desire continuity of their reading experience undeterred by glitches.
The first typo is at page 109 where an appropriate choice of superoperator norm is being examined with outstanding motivation. The Example 11.1 is meant to show that the naive definition of the norm of a super operator T given by
$\|T\|_{s.op} = \sup_X \|T X\|_{tr} / \|X\|_{tr}$ is not invariant under augmentation of the quantum registry, i.e., the inclusion of knowledge about the outside system.
The example given is to take $T: |j \rangle \langle k| \mapsto |k \rangle \langle j|$ for $j,k = 0,1$. Then it’s easy to see $\|T\|_{s.op} = 1$, by examining its effect on all basis $2 \times 2$ matrices and using linearity. Next consider $T \otimes I_{\mathcal{B}}$ where $\mathcal{B}$ is the space spanned by $|0\rangle, |1 \rangle$, i.e., one qubit space. The authors then consider the operator $X = \sum_{j,k} |j,j\rangle \langle k,k|$, and claim the following
1. $\|X\|_{tr} = 2$, which is true
2. $\|TX\|_{tr} = 4$, which is patently false! In fact the latter is again 2.
So this is not a counterexamplary witness to the non-invariance of $\|\bullet \|_{s.op}$ under ancillary augmentation.
Well what’s a real counterexample?
Consider $X = \sum_{j,k} | j,k\rangle \langle k,j|$. Here again we have $\|X \|_{tr} = \langle 0,0|0,0\rangle + \langle 1,1|1,1\rangle = 2$. But $T \otimes I_{\mathcal{B}}X = \sum_{j,k} |j,k\rangle \langle j,k|$, hence $\|TX\|_{tr} = 4$. So this shows $\|T\otimes I_{\mathcal{B}}\|_{s.op}\ge 2$. The authors also claim 2 is the exact norm in this case, which I haven’t checked but I can easily believe that.

The second typo occurs at page 112 and is much subtler. At the end of the generalized measurement operation, in order to retrieve useful classical measurement, a decoherence procedure is required. But the author or perhaps the translator called the operation synonymously matrix diagonalization. These two are far from the same of course. Decoherence refers to the extraction of only the diagonal elements of a matrix under the standard basis ($|0,1,0,0,\ldots, 1\rangle$ etc). Diagonalization on the other hand, would require typically superposed states like $|0,0\rangle + |1,1\rangle$ as basis vectors.