Algorithms and Complexity for Quantum Computing

July 16, 2013
Joseph Traub | Columbia University

Are quantum computers more powerful than classical computers? To answer this question one must know the classical computational complexity. What is it about the problems of quantum chemistry and quantum physics that enables us to get lower bounds on the classical complexity? We also introduce a new classification of quantum speedups.
We then turn to a particular problem, the ground state of the time-independent Schroedinger equation for a system of p particles. The classical deterministic complexity of this problem is exponential in p. We provide an algorithm for solving this problem on a quantum computer whose cost is linear in p. We discuss whether this exponential separation (in our oracle model) proves that quantum computers are exponentially more powerful than classical computers.
We end with a selection of research directions and where to learn more.

Speaker Details

Joseph F. Traub is the Edwin Howard Armstrong Professor at Columbia University and External Professor at the Santa Fe Institute. In 1959 he started his pioneering research on what is now called information-based complexity. He is the author of ten books and some one hundred and twenty research papers in which he has applied complexity theory to fields as diverse as physics, economics, and finance. A major focus of his current work is quantum computing.

From 1971 to 1979 Traub was Head of the Computer Science Department at Carnegie Mellon University and led it from a difficult period to excellence. He served as founding chairman of the Computer Science Department at Columbia University from 1979 to 1989. He started the Journal of Complexity in 1985 and has been Editor-in-Chief since. He was founding Chair of the Computer Science and Telecommunications Board of the National Academies from 1986 to 1992 and served again 2005-2009. He serves on the Division Committee for Engineering and Physical Science (DEPSCOM), National Academies.

Traub has received numerous honors including election to the National Academy of Engineering in 1985, the 1991 Emanuel R. Piore Medal from IEEE, and the 1992 Distinguished Service Award, Computer Research Association. He is a Fellow of the American Mathematical Society, the American Association for the Advancement of Science, the Association of Computing Machinery, the New York Academy of Sciences and SIAM. He has been Sherman Fairchild Distinguished Scholar at the California Institute of Technology and received a Distinguished Senior Scientist Award from the Alexander Von Humboldt Foundation. He was selected by the Accademia Nazionale dei Lincei in Rome to present the 1993 Lezione Lincei. Traub received the 1999 Mayor’s Award for Excellence in Science and Technology. The Award was presented by Mayor Rudy Giuliani at a ceremony in New York City. In 2001 he received an honorary Doctorate of Science from the University of Central Florida.