Joseph F. Traub
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Joseph F. Traub has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Henryk Woźniakowski
Department of Computer Science Columbia University 10027 New York NY USA
7 shared publications - Anargyros Papageorgiou
Columbia University
6 shared publications - Erich Novak
Mathematisches Institut Universität Jena Ernst-Abbe-Platz 2 07740 Jena Germany
6 shared publications - Ian H. Sloan
School of Mathematics and Statistics, UNSW Sydney, Sydney, Australia
6 shared publications - Chi Zhang
Columbia University
2 shared publications - Iasonas Petras
Department of Computer Science Columbia University
2 shared publications
Latest Publications
- 1 June 2014
- Published by Elsevier in Journal of Complexity
- Vol. 30 (3)
Shu Tezuka, Joos Heintz, Bart Kuijpers, and Andrés Rojas Paredes Share the 2013 Best Paper Award
- 1 June 2014
- Published by Elsevier in Journal of Complexity
- Vol. 30 (3)
Shu Tezuka, Joos Heintz, Bart Kuijpers, and Andrés Rojas Paredes Share the 2013 Best Paper Award
- 12 August 2013
- Published by American Physical Society (APS) in Physical Review A
- Vol. 88 (2)
Measures of quantum computing speedup
We introduce the concept of strong quantum speedup. We prove that approximating the ground-state energy of an instance of the time-independent Schr\"odinger equation, with $d$ degrees of freedom and large $d$, enjoys strong exponential quantum speedup. It can be easily solved on a quantum computer. Some researchers in discrete complexity theory believe that quantum computation is not effective for eigenvalue problems. One of our goals in this paper is to explain this dissonance.- 12 August 2013
- Published by American Physical Society (APS) in Physical Review A
- Vol. 88 (2)
Measures of quantum computing speedup
We introduce the concept of strong quantum speedup. We prove that approximating the ground-state energy of an instance of the time-independent Schr\"odinger equation, with $d$ degrees of freedom and large $d$, enjoys strong exponential quantum speedup. It can be easily solved on a quantum computer. Some researchers in discrete complexity theory believe that quantum computation is not effective for eigenvalue problems. One of our goals in this paper is to explain this dissonance.- Open Access
Measures of quantum computing speedup
We introduce the concept of strong quantum speedup. We prove that approximating the ground state energy of an instance of the time-independent Schr\"odinger equation, with $d$ degrees of freedom, $d$ large, enjoys strong exponential quantum speedup. It can be easily solved on a quantum computer. Some researchers in discrete complexity theory believe that quantum computation is not effective for eigenvalue problems. One of our goals in this paper is to explain this dissonance.Open AccessMeasures of quantum computing speedup
We introduce the concept of strong quantum speedup. We prove that approximating the ground state energy of an instance of the time-independent Schr\"odinger equation, with $d$ degrees of freedom, $d$ large, enjoys strong exponential quantum speedup. It can be easily solved on a quantum computer. Some researchers in discrete complexity theory believe that quantum computation is not effective for eigenvalue problems. One of our goals in this paper is to explain this dissonance. - 16 May 2013
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 82 (284) , 2293-2304
A fast algorithm for approximating the ground state energy on a quantum computer
Estimating the ground state energy of a multiparticle system with relative error <!-- MATH $\varepsilon$ --> using deterministic classical algorithms has cost that grows exponentially with the number of particles. The problem depends on a number of state variables that is proportional to the number of particles and suffers from the curse of dimensionality. Quantum computers can vanquish this curse. In particular, we study a ground state eigenvalue problem and exhibit a quantum algorithm that achieves relative error <!-- MATH $\varepsilon$ --> using a number of qubits <!-- MATH $C^\prime d\log \varepsilon ^{-1}$ --> with total cost (number of queries plus other quantum operations) <!-- MATH $Cd\varepsilon ^{-(3+\delta )}$ --> , where 0$"> is arbitrarily small and and are independent of and <!-- MATH $\varepsilon$ --> .- 16 May 2013
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 82 (284) , 2293-2304
A fast algorithm for approximating the ground state energy on a quantum computer
Estimating the ground state energy of a multiparticle system with relative error <!-- MATH $\varepsilon$ --> using deterministic classical algorithms has cost that grows exponentially with the number of particles. The problem depends on a number of state variables that is proportional to the number of particles and suffers from the curse of dimensionality. Quantum computers can vanquish this curse. In particular, we study a ground state eigenvalue problem and exhibit a quantum algorithm that achieves relative error <!-- MATH $\varepsilon$ --> using a number of qubits <!-- MATH $C^\prime d\log \varepsilon ^{-1}$ --> with total cost (number of queries plus other quantum operations) <!-- MATH $Cd\varepsilon ^{-(3+\delta )}$ --> , where 0$"> is arbitrarily small and and are independent of and <!-- MATH $\varepsilon$ --> .- 30 April 2013
- Published by Elsevier in Journal of Complexity
- Vol. 29 (2) , 141
Dmitriy Bilyk, Lutz Kämmerer, Stefan Kunis, Daniel Potts, Volodya Temlyakov and Rui Yu share the 2012 Best Paper Award
- 30 April 2013
- Published by Elsevier in Journal of Complexity
- Vol. 29 (2) , 141
Dmitriy Bilyk, Lutz Kämmerer, Stefan Kunis, Daniel Potts, Volodya Temlyakov and Rui Yu share the 2012 Best Paper Award
- Open Access
A fast algorithm for approximating the ground state energy on a quantum computer
Estimating the ground state energy of a multiparticle system with relative error $\e$ using deterministic classical algorithms has cost that grows exponentially with the number of particles. The problem depends on a number of state variables $d$ that is proportional to the number of particles and suffers from the curse of dimensionality. Quantum computers can vanquish this curse. In particular, we study a ground state eigenvalue problem and exhibit a quantum algorithm that achieves relative error $\e$ using a number of qubits $C^\prime d\log \e^{-1}$ with total cost (number of queries plus other quantum operations) $Cd\e^{-(3+\delta)}$, where $\delta>0$ is arbitrarily small and $C$ and $C^\prime$ are independent of $d$ and $\e$.Open AccessA fast algorithm for approximating the ground state energy on a quantum computer
Estimating the ground state energy of a multiparticle system with relative error $\e$ using deterministic classical algorithms has cost that grows exponentially with the number of particles. The problem depends on a number of state variables $d$ that is proportional to the number of particles and suffers from the curse of dimensionality. Quantum computers can vanquish this curse. In particular, we study a ground state eigenvalue problem and exhibit a quantum algorithm that achieves relative error $\e$ using a number of qubits $C^\prime d\log \e^{-1}$ with total cost (number of queries plus other quantum operations) $Cd\e^{-(3+\delta)}$, where $\delta>0$ is arbitrarily small and $C$ and $C^\prime$ are independent of $d$ and $\e$. - 1 January 2013
- Published by Springer Nature
- p. 1-3
Quantum Information Science, Introduction to
- Open Access
- 1 January 2013
- Published by Springer Nature
- p. 1-29
Quantum Algorithms and Complexity for Continuous Problems
- 1 January 2013
- Published by Springer Nature
- p. 1-29
Open AccessQuantum Algorithms and Complexity for Continuous Problems
- 1 October 2012
- Published by Elsevier in Journal of Complexity
- Vol. 28 (5) , 519
Thomas Daun, Leszek Plaskota, Greg W. Wasilkowski Win the 2011 Best Paper Award
- 1 October 2012
- Published by Elsevier in Journal of Complexity
- Vol. 28 (5) , 519
Thomas Daun, Leszek Plaskota, Greg W. Wasilkowski Win the 2011 Best Paper Award
- 29 June 2012
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 55 (7) , 836-837
What is the Right Computational Model for Continuous Scientific Problems?
We address the view about using the Turing Machine model and the real number model for solving continuous scientific problems. Furthermore we will argue that the Turing Machine is the wrong model of computation for the continuous problems of science.
- 29 June 2012
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 55 (7) , 836-837
What is the Right Computational Model for Continuous Scientific Problems?
We address the view about using the Turing Machine model and the real number model for solving continuous scientific problems. Furthermore we will argue that the Turing Machine is the wrong model of computation for the continuous problems of science.