Lecture 26 (quantum computing) changes

[rxu18]

Prof. Barak:

Great chapter! It is very informative. Here are some more subtle changes that I think we should discuss.

• line 142 (Bell's inequality): Do you think ``the'' should be there in "pit intuitive common sense against the quantum mechanics"?
• line 332 (Recap): This is more another section than a recap. The book has only modeled one qubit so far, and this is a very big jump to be considered a recap. Also, I think it might help to explain entanglement a little more, especially with how it leads to the $2^n$-dimensional vector.
• line 405 (last line of the proof): It might be more effective to write `` Taking all four cases together, this strategy wins the game with probability $\ldots =0.8$'', since that is what we have proved. Then we can say that there are strategies that perform better and move the remark here for a more linear reading experience.
• line 410 (Remark on quantum strategy): I think it will help to elaborate on the last sentence, since it is at the heart of why this strategy wins more. Maybe highlighting how this ``negative probability'' is used would be enough.
• line 515 (remark on the obvious exponential fallacy): I am concerned about the wording in ``as far as we know ... with polynomial overhead''. To me, the sentence sounds like we know a way to simulate QNAND-CIRC program with NAND-CIRC program, but it's trying to say that we haven't ruled out this possibility.

[rxu18]

In fact, the recap seems to repeat itself on line 895, when it is more appropriate. Should we remove the recap on line 332 then?

And a couple last things I noticed:

• The alternative characterization of P mentioned in exercise 1.2 (P \subseteq BQP) is missing a reference.
• We have two styles of hints in the book. Is this intentional?
  1. ".^[Hint : text]" (like exercise 1)
  2. ". See footnote for hint.^[text]" (like exercise 2)

[boazbk]

Thanks! Changed all of the above. Made the first "recap" an "executive summary".

The two styles of hints are not intentional - should always be the second one so people that don't want the hint are able to avoid it - made a search and replace now.