Abstract
We study the approximation of embeddings between finite-dimensional $L_p$ spaces in the quantum model of computation. For the quantum query complexity of this problem, matching (up to logarithmic factors) upper and lower bounds are obtained. The results show that for certain regions of the parameter domain, quantum computation can essentially improve the rate of convergence of classical deterministic or randomized approximation, while there are other regions where the best possible rates coincide for all three settings. These results serve as a crucial building block for analyzing approximation in function spaces in a subsequent paper.
Introduction
In recent years, quantum numerical analysis has demonstrated significant potential for accelerating computational tasks. While much of the existing literature focuses on "integration" problems—where the goal is to compute a single scalar value, such as an average—many real-world engineering and physics problems require the approximation of entire functions. This paper shifts the focus from scalar outputs to function approximation, specifically examining the query complexity of approximating the identity embedding $J^N_{pq} : L^N_p \to L^N_q$.
This problem serves as the theoretical "atomic unit" for understanding how quantum computers will eventually handle complex continuous functions, such as those found in Sobolev spaces. By establishing the fundamental limits of quantum algorithms in finite-dimensional $L_p$ spaces, we lay the groundwork for solving complex differential equations and other high-dimensional approximation challenges.
Problem Formulation
The core of this research involves the identity operator $J^N_{pq}$, which maps an element from a finite-dimensional $L_p$ space to an $L_q$ space. Given a sequence of $N$ numbers whose "size" is bounded in the $L_p$ norm, the goal is to determine how many quantum queries are required to find a new sequence that is "close" to the original in the $L_q$ norm.
The study operates on abstract mathematical objects:
- Finite-dimensional $L_p$ spaces ($L^N_p$): Spaces of $N$-length sequences where the norm is defined by the $p$-norm.
- Unit balls ($B(L^N_p)$): The set of all sequences with a norm less than or equal to 1.
Methodology
The paper establishes matching upper and lower bounds through two primary strategies:
1. Upper Bounds: The Thresholding Algorithm
The author proposes a quantum algorithm based on a sophisticated adaptation of Grover’s quantum search. The strategy utilizes "thresholding": the algorithm identifies all coordinates of the input function that exceed a specific calculated threshold while ignoring the rest. By employing quantum amplitude estimation, the algorithm can locate these "heavy" coordinates significantly faster than any classical scanning method could. This approach leverages the inherent sparsity of functions in the unit ball of $L_p$ when measured against an $L_q$ norm (where $p < q$).
2. Lower Bounds: Multiplicative Inequality
To prove the optimality of the proposed algorithm, the author introduces a multiplicative inequality for the $n$-th minimal query error. This technique, inspired by the theory of $s$-numbers in functional analysis, allows for the "stacking" of lower bounds from simpler problems to cover the complex embedding problem. This ensures that no quantum algorithm can achieve a better convergence rate than the one identified.
Key Insights and Results
The $\sqrt{N}$ Phase Change
A pivotal finding of this research is that quantum advantage is not immediate. For a small number of queries ($n \leq \sqrt{N}$), the quantum convergence rate is identical to the classical rate. The "quantum magic" only begins to outpace classical randomized algorithms once the number of queries exceeds the square root of the dimension $N$.
The Role of Sparsity
The effectiveness of the thresholding algorithm is rooted in the relationship between $p$ and $q$. For $p < q$, a function in the unit ball of $L_p$ cannot contain too many large values in the $L_q$ sense. Quantum computers excel at identifying these few "needles in the haystack," leading to a speedup. Conversely, if $p \geq q$, the target norm is "easier" or equal to the source norm, and the paper proves a "no free lunch" result: quantum computing offers no advantage over classical methods in this regime.
Convergence Rates
The paper provides a complete characterization of quantum query complexity. For the regime where $p < q$ and $n > \sqrt{N}$, the quantum error rate is approximately: $$e_n(J^N_{pq}) \approx \left(\frac{N}{n}\right)^{2/p - 2/q}$$
This represents a significant improvement over the classical deterministic and randomized rate of $N^{1/p - 1/q}$. While previous work on integration showed exponential speedups over deterministic classical methods, this work on approximation demonstrates a polynomial speedup that remains potentially massive—up to a factor of $N^{-1}$ in the rate.
Conclusion and Future Work
While the polynomial components of the bounds are tight, the author notes that logarithmic factors could be further refined in future studies. Additionally, while the primary results focus on the query model, preliminary discussions on the bit model (gate complexity) suggest a need for more exhaustive analysis on specific hardware architectures.
This paper is the first in a series. The finite-dimensional results established here are the necessary building blocks for Part II, which will address the approximation of infinite-dimensional Sobolev embeddings—a critical component for the future of quantum-accelerated partial differential equation (PDE) solvers.
Summary updated