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 |