Anargyros Papageorgiou
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Anargyros Papageorgiou has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Joseph F. Traub
Columbia University
6 shared publications - Chi Zhang
Columbia University
4 shared publications - Henryk Woźniakowski
Department of Computer Science Columbia University 10027 New York NY USA
3 shared publications - Iasonas Petras
Department of Computer Science Columbia University
3 shared publications - Mikhail Lifshits
St.Petersburg State University, St.Petersburg, Russia
2 shared publications - Peter Jaksch
Department of Computer Science, Columbia University, New York, New York 10027-6902, USA
2 shared publications
Latest Publications
- 28 January 2015
- Published by Springer Nature in Quantum Information Processing
- Vol. 14 (4) , 1151-1178
Approximating ground and excited state energies on a quantum computer
- 28 January 2015
- Published by Springer Nature in Quantum Information Processing
- Vol. 14 (4) , 1151-1178
Approximating ground and excited state energies on a quantum computer
- Open Access
Estimating the ground state energy of the Schrödinger equation for convex potentials
In 2011, the fundamental gap conjecture for Schr\"odinger operators was proven. This can be used to estimate the ground state energy of the time-independent Schr\"odinger equation with a convex potential and relative error \epsilon. Classical deterministic algorithms solving this problem have cost exponential in the number of its degrees of freedom d. We show a quantum algorithm, that is based on a perturbation method, for estimating the ground state energy with relative error \epsilon. The cost of the algorithm is polynomial in d and \epsilon^{-1}, while the number of qubits is polynomial in d and \log\epsilon^{-1}. In addition, we present an algorithm for preparing a quantum state that overlaps within 1-\delta, \delta \in (0,1), with the ground state eigenvector of the discretized Hamiltonian. This algorithm also approximates the ground state with relative error \epsilon. The cost of the algorithm is polynomial in d, \epsilon^{-1} and \delta^{-1}, while the number of qubits is polynomial in d, \log\epsilon^{-1} and \log\delta^{-1}.
Open AccessEstimating the ground state energy of the Schrödinger equation for convex potentials
In 2011, the fundamental gap conjecture for Schr\"odinger operators was proven. This can be used to estimate the ground state energy of the time-independent Schr\"odinger equation with a convex potential and relative error \epsilon. Classical deterministic algorithms solving this problem have cost exponential in the number of its degrees of freedom d. We show a quantum algorithm, that is based on a perturbation method, for estimating the ground state energy with relative error \epsilon. The cost of the algorithm is polynomial in d and \epsilon^{-1}, while the number of qubits is polynomial in d and \log\epsilon^{-1}. In addition, we present an algorithm for preparing a quantum state that overlaps within 1-\delta, \delta \in (0,1), with the ground state eigenvector of the discretized Hamiltonian. This algorithm also approximates the ground state with relative error \epsilon. The cost of the algorithm is polynomial in d, \epsilon^{-1} and \delta^{-1}, while the number of qubits is polynomial in d, \log\epsilon^{-1} and \log\delta^{-1}.
- 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$ --> .- 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$. - 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
- Open Access
Average Case Tractability of Non-homogeneous Tensor Product Problems
We study d-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. Our interest is focused on measures having a structure of non-homogeneous linear tensor product, where covariance kernel is a product of univariate kernels. We consider the normalized average error of algorithms that use finitely many evaluations of arbitrary linear functionals. The information complexity is defined as the minimal number n(h,d) of such evaluations for error in the d-variate case to be at most h. The growth of n(h,d) as a function of h^{-1} and d depends on the eigenvalues of the covariance operator and determines whether a problem is tractable or not. Four types of tractability are studied and for each of them we find the necessary and sufficient conditions in terms of the eigenvalues of univariate kernels. We illustrate our results by considering approximation problems related to the product of Korobov kernels characterized by a weights g_k and smoothnesses r_k. We assume that weights are non-increasing and smoothness parameters are non-decreasing. Furthermore they may be related, for instance g_k=g(r_k) for some non-increasing function g. In particular, we show that approximation problem is strongly polynomially tractable, i.e., n(h,d)\le C h^{-p} for all d and 0<h1. For other types of tractability we also show necessary and sufficient conditions in terms of the sequences g_k and r_k.
Open AccessAverage Case Tractability of Non-homogeneous Tensor Product Problems
We study d-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure. Our interest is focused on measures having a structure of non-homogeneous linear tensor product, where covariance kernel is a product of univariate kernels. We consider the normalized average error of algorithms that use finitely many evaluations of arbitrary linear functionals. The information complexity is defined as the minimal number n(h,d) of such evaluations for error in the d-variate case to be at most h. The growth of n(h,d) as a function of h^{-1} and d depends on the eigenvalues of the covariance operator and determines whether a problem is tractable or not. Four types of tractability are studied and for each of them we find the necessary and sufficient conditions in terms of the eigenvalues of univariate kernels. We illustrate our results by considering approximation problems related to the product of Korobov kernels characterized by a weights g_k and smoothnesses r_k. We assume that weights are non-increasing and smoothness parameters are non-decreasing. Furthermore they may be related, for instance g_k=g(r_k) for some non-increasing function g. In particular, we show that approximation problem is strongly polynomially tractable, i.e., n(h,d)\le C h^{-p} for all d and 0<h1. For other types of tractability we also show necessary and sufficient conditions in terms of the sequences g_k and r_k.
- Open Access
Tractability of Multi-Parametric Euler and Wiener Integrated Processes
We study average case approximation of Euler and Wiener integrated processes of d variables which are almost surely r_k-times continuously differentiable with respect to the k-th variable. Let n(h,d) denote the minimal number of continuous linear functionals which is needed to find an algorithm that uses n such functionals and whose average case error improves the average case error of the zero algorithm by a factor h. Strong polynomial tractability means that there are nonnegative numbers C and p such that n(h,d)< C h^{-p} for all d and 0 0 for some s>1/2. Other types of tractability are also studied.
Open AccessTractability of Multi-Parametric Euler and Wiener Integrated Processes
We study average case approximation of Euler and Wiener integrated processes of d variables which are almost surely r_k-times continuously differentiable with respect to the k-th variable. Let n(h,d) denote the minimal number of continuous linear functionals which is needed to find an algorithm that uses n such functionals and whose average case error improves the average case error of the zero algorithm by a factor h. Strong polynomial tractability means that there are nonnegative numbers C and p such that n(h,d)< C h^{-p} for all d and 0 0 for some s>1/2. Other types of tractability are also studied.
- 29 August 2011
- Published by Springer Nature
- p. 1-29
Quantum Algorithms and Complexity for Continuous Problems
- 29 August 2011
- Published by Springer Nature
- p. 1-29
Quantum Algorithms and Complexity for Continuous Problems