APAnargyros Papageorgiou

Anargyros Papageorgiou

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Anargyros Papageorgiou has a total of 12 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Estimating the ground state energy of the Schrödinger equation for convex potentials

    by Anargyros Papageorgiou, Iasonas Petras

    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}.

  • Measures of quantum computing speedup

    by Anargyros Papageorgiou, Joseph F. Traub

    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

    by Anargyros Papageorgiou, Joseph F. Traub

    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.

  • A fast algorithm for approximating the ground state energy on a quantum computer

    by A. Papageorgiou, I. Petras, J. F. Traub, C. Zhang

    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

    by Anargyros Papageorgiou, Iasonas Petras, Joseph F. Traub, Chi Zhang

    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

    Quantum Algorithms and Complexity for Continuous Problems

    by Anargyros Papageorgiou, Joseph F. Traub


  • Open Access

    Average Case Tractability of Non-homogeneous Tensor Product Problems

    by M. A. Lifshits, A. Papageorgiou, H. Woźniakowski

    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

    by M. A. Lifshits, A. Papageorgiou, H. Woźniakowski

    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.