2006): The quantum query complexity of elliptic PDE

The complexity of the following numerical problem is studied in the quantum model of computation: Consider a general elliptic partial differential equation of order 2m in a smooth, bounded domain Q\subset \R^d with smooth coefficients and homogeneous boundary conditions. We seek to approximate the solution on a smooth submanifold M\subseteq Q of dimension 0\le d_1 \le d. With the right hand side belonging to C^r(Q), and the error being measured in the L_\infty(M) norm, we prove that the n-th minimal quantum error is (up to logarithmic factors) of order n^{-min((r+2m)/d_1,r/d+1)}. For comparison, in the classical deterministic setting the n-th minimal error is known to be of order n^{-r/d}, for all d_1, while in the classical randomized setting it is (up to logarithmic factors) n^{-min((r+2m)/d_1,r/d+1/2)}.The complexity of the following numerical problem is studied in the quantum model of computation: Consider a general elliptic partial differential equation of order 2m in a smooth, bounded domain Q\subset \R^d with smooth coefficients and homogeneous boundary conditions. We seek to approximate the solution on a smooth submanifold M\subseteq Q of dimension 0\le d_1 \le d. With the right hand side belonging to C^r(Q), and the error being measured in the L_\infty(M) norm, we prove that the n-th minimal quantum error is (up to logarithmic factors) of order n^{-min((r+2m)/d_1,r/d+1)}. For comparison, in the classical deterministic setting the n-th minimal error is known to be of order n^{-r/d}, for all d_1, while in the classical randomized setting it is (up to logarithmic factors) n^{-min((r+2m)/d_1,r/d+1/2)}.

arXiv:quant-ph/0512241Dec 27, 20050 citations

High-precision quantum algorithms for partial differential equations

Andrew M. Childs, Jin-Peng Liu, Aaron Ostrander

Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ⁡ ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ⁡ ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

arXiv:2002.07868QuantumNov 10, 2021154 citations

Quantum Algorithms for Multiscale Partial Differential Equations

Junpeng Hu, Shi Jin, Lei Zhang

Abstract. Partial differential equation (PDE) models with multiple temporal/spatial scales are prevalent in several disciplines such as physics, engineering, and many others. These models are of great practical importance but notoriously difficult to solve due to prohibitively small mesh and time step sizes limited by the scaling parameter and CFL condition. Another challenge in scientific computing could come from curse-of-dimensionality. In this paper, we aim to provide a quantum algorithm, based on either direct approximations of the original PDEs or their homogenized models, for prototypical multiscale problems inPDEs, including elliptic, parabolic, and hyperbolic PDEs. To achieve this, we will lift these problems to higher dimensions and leverage the recently developed Schrödingerization based quantum simulation algorithms to efficiently reduce the computational cost of the resulting high-dimensional and multiscale problems. We will examine the error contributions arising from discretization, homogenization, and relaxation, and analyze and compare the complexities of these algorithms in order to identify the best algorithms in terms of complexities for different equations in different regimes.Abstract. Partial differential equation (PDE) models with multiple temporal/spatial scales are prevalent in several disciplines such as physics, engineering, and many others. These models are of great practical importance but notoriously difficult to solve due to prohibitively small mesh and time step sizes limited by the scaling parameter and CFL condition. Another challenge in scientific computing could come from curse-of-dimensionality. In this paper, we aim to provide a quantum algorithm, based on either direct approximations of the original PDEs or their homogenized models, for prototypical multiscale problems inPDEs, including elliptic, parabolic, and hyperbolic PDEs. To achieve this, we will lift these problems to higher dimensions and leverage the recently developed Schrödingerization based quantum simulation algorithms to efficiently reduce the computational cost of the resulting high-dimensional and multiscale problems. We will examine the error contributions arising from discretization, homogenization, and relaxation, and analyze and compare the complexities of these algorithms in order to identify the best algorithms in terms of complexities for different equations in different regimes.

arXiv:2304.06902Multiscale Modeling and SimulationJul 30, 20246 citations

Quantum Submodular Maximization

Yonggang Jiang, Xiaoming Sun, Penghui Yao +3 more

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$ -element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$ -approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$ -approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$ , our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$ , the query complexity reduces to $O_{\varepsilon,c}(\log n)$ , yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$ . These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$-approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$-approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$, the query complexity reduces to $O_{\varepsilon,c}(\log n)$, yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

quant-pharXiv:2610.04560Oct 6, 20260 citations

Quantum Complexity of the Integration Problem for Anisotropic Classes

Xiao-Fei Hu, Pei-Xin Ye

We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes $W_{\infty}^{\bf r}([0,1]^d)$ and Hölder Nikolskii classes $H_{\infty}^{\bf r}([0,1]^d)$ . It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor $n^{-1}$ and over randomized classical methods due to factor $n^{-1/2}$ . Moreover, we give an estimation for optimal query complexity in the class $H_{\infty}^{\Lambda}(D)$ whose smoothness index is the boundary of some complete set in $\mathbb{Z}_+^d$ .We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes $W_{\infty}^{\bf r}([0,1]^d)$ and Hölder Nikolskii classes $H_{\infty}^{\bf r}([0,1]^d)$. It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor $n^{-1}$ and over randomized classical methods due to factor $n^{-1/2}$. Moreover, we give an estimation for optimal query complexity in the class $H_{\infty}^{\Lambda}(D)$ whose smoothness index is the boundary of some complete set in $\mathbb{Z}_+^d$.

Journal of Computational MathematicsJun 2, 20050 citations

Quantum query complexity of Hurwitz stability testing

Maxwell Fitzsimmons, Mohamed Serry, Meenu Kumari +1 more

Determining whether every trajectory of the linear system $\dot{x}=Ax$ converges to zero (or, equivalently, whether $A$ is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix $A\in\mathbb{C}^{n\times n}$ is Hurwitz stable, given an exact normalized block-encoding of $A$ . The query complexity is characterized in terms of the system dimension $n$ and a supplied lower bound $0<ν\leq ω_A$ on the imaginary-axis distance $ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)$ , where $σ_{\min}(A)$ is the smallest singular value of $A$ . We prove a query-complexity lower bound of $Ω(\sqrt{n}/ν)$ , which holds even when $A$ is restricted to be real and diagonal. For general matrices with nonzero $ω_A$ , we encode an approximation of the right-half-plane spectral projector $\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2$ as a block of a matrix inverse, where $A$ is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a $(β,b,1/(4\sqrt{n}))$ -block-encoded projector matrix (like $\operatorname{sign}^+(A)$ ) is zero or not; for constant success probability, it has complexity $Θ(β\sqrt{n})$ . When the zero test is applied to specific approximations of $\operatorname{sign}^+(A)$ , this yields an upper bound of $O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))$ queries in the general case, and $O(\sqrt{n}ν^{-1}\log n)$ when $A$ is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.Determining whether every trajectory of the linear system $\dot{x}=Ax$ converges to zero (or, equivalently, whether $A$ is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix $A\in\mathbb{C}^{n\times n}$ is Hurwitz stable, given an exact normalized block-encoding of $A$. The query complexity is characterized in terms of the system dimension $n$ and a supplied lower bound $0<ν\leq ω_A$ on the imaginary-axis distance $ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)$, where $σ_{\min}(A)$ is the smallest singular value of $A$. We prove a query-complexity lower bound of $Ω(\sqrt{n}/ν)$, which holds even when $A$ is restricted to be real and diagonal. For general matrices with nonzero $ω_A$, we encode an approximation of the right-half-plane spectral projector $\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2$ as a block of a matrix inverse, where $A$ is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a $(β,b,1/(4\sqrt{n}))$-block-encoded projector matrix (like $\operatorname{sign}^+(A)$) is zero or not; for constant success probability, it has complexity $Θ(β\sqrt{n})$. When the zero test is applied to specific approximations of $\operatorname{sign}^+(A)$, this yields an upper bound of $O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))$ queries in the general case, and $O(\sqrt{n}ν^{-1}\log n)$ when $A$ is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.

quant-pharXiv:2610.41180Nov 2, 2026

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint

k

on an

n

-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected

(1/2-\varepsilon)

-approximation using only

O_\varepsilon(\log n)

queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above

1/4

requires

Ω(n/\log n)

queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a

(1-1/e-\varepsilon)

-approximation using

\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})

queries. When

k=o(n)

, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when

k=cn

for any fixed rational

c<1-1/e-\varepsilon

, the query complexity reduces to

O_{\varepsilon,c}(\log n)

, yielding an exponential separation from the classical

Ω(n/\log n)

lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of

\exp(Ω(\varepsilon^2n))

queries for achieving a ratio beyond

1/2+\varepsilon

without constraints, and

\exp(Ω(\varepsilon^2k))

queries for exceeding

1-1/e+\varepsilon

when

k/n\le\varepsilon

. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes

W_{\infty}^{\bf r}([0,1]^d)

and Hölder Nikolskii classes

H_{\infty}^{\bf r}([0,1]^d)

. It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor

n^{-1}

and over randomized classical methods due to factor

n^{-1/2}

. Moreover, we give an estimation for optimal query complexity in the class

H_{\infty}^{\Lambda}(D)

whose smoothness index is the boundary of some complete set in

\mathbb{Z}_+^d

Determining whether every trajectory of the linear system

\dot{x}=Ax

converges to zero (or, equivalently, whether

A

is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix

A\in\mathbb{C}^{n\times n}

is Hurwitz stable, given an exact normalized block-encoding of

A

. The query complexity is characterized in terms of the system dimension

n

and a supplied lower bound

0<ν\leq ω_A

on the imaginary-axis distance

ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)

, where

σ_{\min}(A)

is the smallest singular value of

A

. We prove a query-complexity lower bound of

Ω(\sqrt{n}/ν)

, which holds even when

A

is restricted to be real and diagonal. For general matrices with nonzero

ω_A

, we encode an approximation of the right-half-plane spectral projector

\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2

as a block of a matrix inverse, where

A

is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a

(β,b,1/(4\sqrt{n}))

-block-encoded projector matrix (like

\operatorname{sign}^+(A)

) is zero or not; for constant success probability, it has complexity

Θ(β\sqrt{n})

. When the zero test is applied to specific approximations of

\operatorname{sign}^+(A)

, this yields an upper bound of

O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))

queries in the general case, and

O(\sqrt{n}ν^{-1}\log n)

when

A

is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.