Volkher Scholz, Institute for Theoretical Physics ETH Zurich
Joseph F. Traub, Columbia University
We introduce the notion of strong quantum speedup. To compute this
speedup one must know the classical computational complexity. What is it about the problems of quantum physics and quantum chemistry that enable us to get lower bounds on the classical complexity?