Quantum Computing for Computer Scientists

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

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:

  1. Works on paper, not in practice.
  2. Violates Extended Church-Turing Thesis.
  3. Not enough “real physics.”
  4. Small amplitudes are unphysical.
  5. Exponentially large states are unphysical.
  6. Quantum computers are just souped-up analog computers.
  7. Quantum computers aren’t like anything we’ve ever seen before.
  8. Quantum mechanics is just an approximation to some deeper theory.
  9. Decoherence will always be worse than the fault-tolerance threshold.
  10. We don’t need fault-tolerance for classical computers.
  11. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: