Participants

Joseph F. Traub

Joseph F. Traub is the Edwin Howard Armstrong Professor of Computer Science, Columbia University, and External Professor, Santa Fe Institute. He chairs the Computer Science and Telecommunication Board of the National Academies.

He was Head of the Computer Science Department at Carnegie-Mellon University 1971-1979 and Founding Chairman of the Computer Science Department at Columbia University 1979-1989. He served as Founding Chair of the Computer Science and Telecommunications Board (CSTB) of the National Academies 1986-1992. He is again serving as Chair 2005-.

Traub pioneered the field of information-based complexity starting in 1959. His current focus is on quantum computing. He is the author or editor of ten books and some one hundred and twenty journal articles. His most recent monograph is "Complexity and Information", Cambridge University Press, 1998. He is Editor-in Chief of the Journal of Complexity and Associate Editor of Complexity.

His numerous honors include election to the National Academy of Engineering in 1985, the 1991 Emanuel R. Piore Gold Medal from IEEE, and the 1992 Distinguished Service Award, Computer Research Association. He is a Fellow of the American Association for the Advancement of Science, the Association for Computing Machinery, and the New York Academy of Sciences. 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 Academia Nazionale dei Lincei in Rome to present the 1993 Lezioni Lincee, a cycle of six lectures. 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 May, 2001, he received an honorary Doctorate of Science from the University of Central Florida.

He has served as advisor or consultant to the senior management of numerous organizations including IBM, Hewlett-Packard, Schlumberger, Stanford University, INRIA (Paris), Federal Judiciary Center, DARPA, NSF, and Lucent Technologies.

Abstract

QUBIT COMPLEXITY OF CONTINUOUS PROBLEMS

Abstract For the foreseeable future the number of qubits will be a crucial computational resource on a quantum computer. We show how to lower bound the qubit complexity using the classical query complexity. We use this result to present a simple problem which cannot be solved on a quantum computer in the standard quantum setting with deterministic queries but can be solved on a classical computer using randomized queries (Monte Carlo). This suggests introducing a quantum setting with randomized queries. We apply this setting to high dimensional integration and to path integration. In particular, there is an exponential improvement in the qubit complexity of path integration using the quantum setting with randomized queries. We end by discussing future directions and where to learn more.