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

In 2011, the fundamental gap conjecture for Schrödinger operators was proven. This can be used to estimate the ground state energy of the time-independent Schrödinger 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$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$d$ and ε⁻¹${\epsilon }^{-1}$, while the number of qubits is polynomial in d$d$ and logε⁻¹$log{\epsilon }^{-1}$. In addition, we present an algorithm for preparing a quantum state that overlaps within 1−δ,δ∈(0,1)$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$d$, ε⁻¹${\epsilon }^{-1}$ and δ⁻¹${\delta }^{-1}$, while the number of qubits is polynomial in d$d$, logε⁻¹$log{\epsilon }^{-1}$ and logδ⁻¹$log{\delta }^{-1}$.     

Riemann–Hilbert formulation for the KdV equation on a finite interval

The initial-boundary value problem for the KdV equation on a finite interval is analyzed in terms of a singular Riemann–Hilbert problem for a matrix-valued function in the complex k-plane which depends explicitly on the space–time variables. For an appropriate set of initial and boundary data, we derive the k-dependent “spectral functions” which guarantee the uniqueness of Riemann–Hilbert problem's solution. The latter determines a solution of the initial-boundary value problem for KdV equation, for which an integral representation is given. To cite this article: I. Hitzazis, D. Tsoubelis, C. R. Acad. Sci. Paris, Ser. I 347 (2009).     

A new criterion for tractability of multivariate problems

Tractability of multivariate problems studies their complexity with respect to the number of variables, d$d$, and the accuracy of the solution ε$\epsilon$. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy.     

On the tractability of linear tensor product problems in the worst case

It has been an open problem to derive a necessary and sufficient condition for a linear tensor product problem to be weakly tractable in the worst case. The complexity of linear tensor product problems in the worst case depends on the eigenvalues _{λi}i∈N${\left\{{\lambda }_i\right\}}_{i\in \mathbb{N}}$ of a certain operator. It is known that if _λ1=1${\lambda }_1=1$ and _λ2∈(0,1)${\lambda }_2\in (0,1)$ then _λn=o((lnn)⁻²)${\lambda }_n=o\left({(lnn)}^{-2}\right)$, as n→∞$n\to \infty$, is a necessary condition for a problem to be weakly tractable. We show that this is a sufficient condition as well.