Algorithms and Complexity for Quantum Computing

SANTA FE INSTITUTE News
 
 
Joe Traub, Edwin Howard Armstrong Professor of Computer Science, Columbia University; External Professor, Santa Fe Institute will present “Algorithms and Complexity for Quantum Computing” on Wednesday, June 6th at 12:15 p.m in the Medium Conference Room.
 
Abstract:  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 proves that quantum computers are exponentially more powerful than classical computers.
 
We end with a selection of research directions and where to learn more.
 
 
The Santa Fe Institute’s mission is to foster a transdisciplinary research community that endeavors to expand the boundaries of scientific understanding. Its aim is to discover and comprehend the common fundamental principles in physical, computational, biological, and social systems that underlie many of the most profound problems facing science and society today.

Joseph F. Traub 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 served again as chair 2005-2009. He has been appointed as a member of the Division Committee on Engineering and Physical Sciences (DEPS) of the National Academies.

Traub is author or editor of ten books and some one hundred twenty journal articles. 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. In 2008 he was elected to the Board of Directors of the Marconi Society.

 

LOS ALAMOS

ladailypost.com website support locally by OviNuppi Systems

Subscribe to your choice of breaking and/or daily news headlines.

Copyright © 2012-2023 The Los Alamos Daily Post is the Official Newspaper of Record in Los Alamos County. This Site and all information contained here including, but not limited to news stories, photographs, videos, charts, graphs and graphics is the property of the Los Alamos Daily Post, unless otherwise noted. Permission to reprint in whole or in part is hereby granted, provided that the Los Alamos Daily Post and the author/photographer are properly cited. Opinions expressed by readers, columnists and other contributors do not necessarily reflect the views of the Los Alamos Daily Post. The Los Alamos Daily Post newspaper was founded by Carol A. Clark on Feb. 7, 2012.

CSTsiteisloaded