Abstract
A basic problem of approximation theory, the approximation of functions from the Sobolev space $W_p^r([0,1]^d)$ in the norm of $L_q([0,1]^d)$, is considered from the point of view of quantum computation. We determine the quantum query complexity of this problem (up to logarithmic factors). It turns out that in certain regions of the domain of parameters $p,q,r,d$ quantum computation can reach a speedup of roughly squaring the rate of convergence of classical deterministic or randomized approximation methods. There are other regions were the best possible rates coincide for all three settings.
Introduction
In numerical analysis and approximation theory, a fundamental challenge is determining the minimum number of function evaluations (queries) required to approximate a smooth function within a specified error tolerance $\epsilon$. While classical deterministic and randomized (Monte Carlo) methods for this problem are well-understood, the advent of quantum computing introduces new possibilities for speedup. This paper investigates the quantum query complexity of approximating functions within Sobolev spaces $W_p^r([0,1]^d)$ under the $L_q([0,1]^d)$ norm.
Sobolev spaces consist of functions with $r$ derivatives that are integrable to the $p$-th power over a $d$-dimensional unit cube. The goal is to find an approximation such that the error, measured in the $L_q$ norm, is minimized. The core question is whether quantum algorithms, leveraging superposition and interference, can outperform the optimal classical rates of convergence.
Methodology: Discretization and Quantum Summation
Because Sobolev spaces are infinite-dimensional, they present a challenge for direct analysis in a quantum query model. The author employs a multi-step discretization technique to bridge the gap between functional analysis and quantum complexity:
- Reduction to Finite Dimensions: The infinite-dimensional Sobolev embedding is decomposed into a sequence of embeddings between finite-dimensional spaces (specifically, $L_p^N$ into $L_q^N$). This allows the problem to be treated as a series of discrete vector approximations.
- Operator Decomposition: The target function is approximated using a hierarchy of operators $P_l$. A coarse approximation is established classically, while the finer details—the "residuals"—are processed via quantum subroutines.
- Quantum Mean Estimation: The research builds upon established quantum algorithms for integration and summation. By using quantum algorithms designed to estimate the mean of vectors in finite-dimensional spaces, the author achieves a query advantage over classical sampling techniques.
- Establishing Bounds: The paper provides both upper bounds (by constructing a specific algorithm) and lower bounds (by proving fundamental limits), thereby establishing the true quantum query complexity of the problem.
Key Insights: The $p < q$ Threshold
The most significant finding is that the quantum advantage is highly dependent on the relationship between the source space norm ($p$) and the target error norm ($q$).
- The Advantage Region ($p < q$): Quantum computers provide a speedup only when the error norm is "stricter" than the source space norm. In these cases, the quantum rate of convergence can effectively square the classical rate.
- The Classical Parity Region ($p \ge q$): When the source norm is as strict as or stricter than the error norm, the classical deterministic rate is already optimal. In this regime, quantum mechanics offers no improvement in the convergence exponent.
Complexity Regimes for $p < q$
Within the region where quantum speedup is possible, the complexity behaves differently based on the relationship between smoothness ($r$), dimension ($d$), and the norms:
- High Smoothness ($r/d \ge 2/p - 2/q$): The rate is dominated by the smoothness of the function, resulting in a quantum query complexity of $n^{-r/d}$.
- Low Smoothness ($r/d < 2/p - 2/q$): The rate is constrained by the integrability parameters, resulting in a complexity of $n^{-2r/d + 2/p - 2/q}$.
Comparative Results
The following table summarizes the minimal errors ($e_n$) achieved by $n$ queries across different computational settings. Note that the quantum rates represent a significant improvement in the $p < q$ scenarios.
| Scenario | Classical (Det/Rand) Rate | Quantum Rate |
|---|---|---|
| $p < q$, High Smoothness | $n^{-r/d + 1/p - 1/q}$ | $n^{-r/d}$ |
| $p < q$, Low Smoothness | $n^{-r/d + 1/p - 1/q}$ | $n^{-2r/d + 2/p - 2/q}$ |
| $q \le p$ (Any Smoothness) | $n^{-r/d}$ | $n^{-r/d}$ |
For example, if we consider the case where $p=1$ and $q=\infty$ (approximating an $L_1$ function to fit the Supremum norm), the classical rate is $n^{-r/d + 1}$. The quantum rate improves this to $n^{-r/d}$, a substantial gain as the number of queries $n$ increases.
Discussion and Limitations
While this work establishes the theoretical power of quantum approximation, several considerations remain for practical implementation:
- Logarithmic Factors: The results are determined up to logarithmic factors. While the power-law exponents are exact, the precise behavior of $\log(n)$ terms remains an open detail.
- Oracle Assumptions: The study assumes a standard quantum query model where an oracle provides function values in superposition. The actual cost of constructing such an oracle for a specific Sobolev function is not accounted for in the query complexity.
- Smoothness Constraints: The analysis requires $r/d > 1/p$ to ensure that functions are continuous and that point-wise function evaluations (queries) are well-defined.
- Bit Complexity: The author notes that the bit complexity (the number of actual logic gates) stays within a logarithmic factor of the query cost, suggesting that these algorithms are theoretically viable for future quantum hardware.
In conclusion, this research demonstrates that for a wide class of Sobolev embedding problems, quantum computation offers a transformative speedup, effectively doubling the efficiency of the convergence rate compared to classical methods.
Summary updated