Lecture notes from the talk Quantum Computing for Computer Scientists by Andrew Helwer at Microsoft

This talk discards hand-wavy pop-science 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 real-world 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
• Constant-0 and Constant-1 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 2-vectors of Complex numbers
Qubits can be in superposition, and are probabilistically collapsed to cbits by measurement
Multi-qubit systems are tensor products of single-qubit systems, like with cbits
Matrices represent operations on qubits, same as with cbits
The Hadamard gate takes 0- and 1-bit 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 physically-realizable quantum computers Lecture by Scott Aaronson Eleven Objections: Works on paper, not in practice. Violates Extended Church-Turing Thesis. Not enough “real physics.” Small amplitudes are unphysical. Exponentially large states are unphysical. Quantum computers are just souped-up analog computers. Quantum computers aren’t like anything we’ve ever seen before. Quantum mechanics is just an approximation to some deeper theory. Decoherence will always be worse than the fault-tolerance threshold. We don’t need fault-tolerance for classical computers. Errors aren’t independent.
	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