Lecture notes from the talk Quantum Computing for Computer Scientists by Andrew Helwer at Microsoft
This talk discards handwavy popscience metaphors and answers a simple question: from a computer science perspective, how can a quantum computer outperform a classical computer? Attendees will learn the following:
 Representing computation with basic linear algebra (matrices and vectors)
 The computational workings of qbits, superposition, and quantum logic gates
 Solving the Deutsch oracle problem: the simplest problem where a quantum computer outperforms classical methods
 Bonus topics: quantum entanglement and teleportation
The talk concludes with a live demonstration of quantum entanglement on a realworld quantum computer, and a demo of the Deutsch oracle problem implemented in Q# with the Microsoft Quantum Development Kit. This talk assumes no prerequisite knowledge, although comfort with basic linear algebra (matrices, vectors, matrix multiplication) will ease understanding.
Operations on one classical bit (cbit)
Reversible Computing
Reversible means given the operation and output value, you can find the input value: for Ax=b, given b and A, you can uniquely find x.
Operations which permute are reversible; operations which erase & overwrite are not:
 Identity and Negation are reversible
 Constant0 and Constant1 are not reversible
Quantum computers use only reversible operations, so we will only care about those. In fact, all quantum operators are their own inverses.
Qubits and Superposition
Operations on Qubits
The Hadamard Gate
The Unit Circle State Machine
Recap
Cbits are just a special case of qubits, which are 2vectors of Complex numbers
Qubits can be in superposition, and are probabilistically collapsed to cbits by measurement
Multiqubit systems are tensor products of singlequbit systems, like with cbits
Matrices represent operations on qubits, same as with cbits
The Hadamard gate takes 0 and 1bit to equal superposition, and back
We can think of qubits and their operations as forming a state machine on the unit circle (actually the unit sphere if we use complex numbers)
The Deutsch Oracle
Further Reading
1. 
Quantum computing for Computer Scientists by Noson S. Yanofsky, Brooklyn College, City University of New York , Mirco A. Mannucci, HoloMathics, LLC, Virginia 

2. 
Quantum Computing: A Gentle Introduction by Eleanor G. Rieffel and Wolfgang H. Polak 

3. 
Quantum Computer Science: An Introduction by N. David Mermin, Cornell University, New York 

4. 
The Microsoft Quantum Development Kit The kit contains a quantum computer simulator 

5. 
Some skepticism and discussion about physicallyrealizable quantum computers Lecture by Scott Aaronson Eleven Objections:


6. 
More skepticism: noise might increase exponentially with the number of physical qubits Why Quantum Computers Cannot Work by Gil Kalai The Argument Against Quantum Computers 