M1: Demystifying Quantum Computers

"Quantum" is getting quite a lot of buzz.  It's hard for engineers to get comprehensible information about it.  Either there are very superficial, inaccurate, popular science articles, or incomprehensible theoretical papers that you'd have to be both a recent physics PhD and recent math PhD in order to understand.  Our course is pitched to engineers, who want to have an intuition about these things, but don't need proofs and formalism.

This tutorial gives an overview of various research directions for quantum, but concentrates on the computation model.  What exactly is a quantum computer?  Is it always faster than a classical computer?  What does an algorithm look like on a quantum computer?

The two quantum algorithms that affect cryptography are Grover's algorithm and Shor's algorithm. This tutorial will give the intuition behind how those algorithms will work.

Prerequisites: There are no prerequisites other than intellectual curiosity, and a good night’s sleep in the recent past.

Text: There is no textbook, although the instructors have been working on a 3rd edition of their textbook “Network Security”, and the contents of this tutorial will appear as a chapter in that, although it will not have been published by the time ACSAC occurs.

Outline:

1. Introduction (10 minutes)
   1. Why quantum matters (Grover’s and Shor’s)
   2. What other problems do people think quantum computers would be good at?
   3. What is “quantum cryptography” (also known as “quantum key distribution”)
2. Computation model (50 minutes)
   1. Superposition, entanglement
   2. Gates, Measurement
   3. Hadamard gates
   4. Notation for state of a qubit
   5. Linearity
   6. Unitarity
   7. Ancillas
3. Grover’s algorithm (1 hour)
4. Shor’s algorithm (1 hour)

About the Instructors:

Dr. Radia Perlman is a Fellow at Dell EMC.  Her specialties include network routing protocols, and network security. She developed the technology for making network routing self-stabilizing, largely self-managing, and scalable.  She also invented the spanning tree algorithm, which transformed Ethernet from a technology that supported a few hundred nodes within a single building, to something that could support large networks.  She also has made contributions in network security, including scalable data expiration, distributed algorithms despite malicious participants, DDOS prevention techniques, and user authentication. She is the author of the textbook “Interconnections” (about network layers 2 and 3) and coauthor (with Charlie Kaufman) of “Network Security: Private Communication in a Public World”). She has been recognized with many industry honors including induction into the National Academy of Engineering, the Inventor Hall of Fame, and lifetime achievement awards from Usenix and SIGCOMM.  She has a PhD in computer science from MIT.

Charlie Kaufman, security architect for the Midrange group at Dell/EMC, has been involved with computer networking and security issues for over 25 years, and holds over 50 patents in those fields. At Microsoft, he was the security architect for Windows Azure - Microsoft's Public Cloud offering - where he was involved with all aspects of cloud security from design through responding to ongoing attacks. At Lotus, he was chief security architect for Lotus Notes and Domino and later the entire Lotus product suite. At Digital, he was the Security Architect for their networking group and later for Digital's UNIX offering.

He has contributed to a number of IETF standards efforts including IPsec, S/MIME, and DNSsec and served as a member of the Internet Architecture Board. He is co-author of the popular textbook "Network Security: Private Communication in a Public World" and served on the National Academy of Sciences expert panel that wrote the book "Trust In Cyberspace".