Meeting Information

Programming Quantum Computers

October 22, 2014
American Center for Physics
College Park, MD

Date: Wednesday, October 22, 2014

Speaker: Dr. Mark Heiligman, IARPA

Topic: Programming Quantum Computers

Time and Location: 1:00 PM, with Q&A to follow; in a 1st floor conference room at the American Center for Physics (www.acp.org), 1 Physics Ellipse, College Park, MD-- off River Rd., between Kenilworth Ave. and Paint Branch Parkway.

Abstract: Quantum Computing is a radical departure from the usual rules of computing, and reflects a profoundly new understanding of the adage, “All Information is Physical.” The very strangest aspects of quantum mechanics, superposition and entanglement, have suddenly been thrust to the forefront in the quest to achieve quantum computing. This marriage of physics with computer science has ushered in the second revolution of quantum mechanics, with substantial benefits to many fields of physics.

While much work has gone into theoretical analysis of quantum phenomena and supporting laboratory demonstrations of the requisite physical phenomena needed to demonstrate basic feasibility, considerably less attention has been paid to the computer science aspects of quantum computing. Since the discovery of Shor’s quantum factoring algorithm, most of the theoretical computer science has focused on discovery of new quantum algorithms and on understanding their corresponding complexity classes; little time has been spent on the question of how a quantum will actually be programmed if one is ever built.

Taking on the challenge of programming a quantum computer with an unknown architecture in a quantum technology of the future might appear premature. Nevertheless, there are many useful lessons that can be learned from such an exercise. Quantum programming languages and their associated compilers face the unique task of being able to express algorithms in a way that prevents the programmer from attempting to violate the laws of physics. The compilation task is substantially compounded by the need to incorporate quantum error correction at every step of the algorithm, and eventually to turn lowest level logical instructions into signals that control the actual physical system performing the computation.

Shor’s work showed that a quantum computer could (in principle) handily perform a computational task that is completely out of reach for a classical computer, and in so doing could call into question the security of current public key cryptography. This talk thus will begin with some of the history and motivation for quantum computing by explaining the basic principles of public key cryptography and how its security depends on the computational intractability of factoring large integers. With this background, the question of how a quantum computer might be built and programmed can then be addressed.