Technical Summary: Approximating Korobov Functions via Quantum Circuits

Problem Statement

This work addresses the theoretical challenge of characterizing the expressive capacity and computational complexity of quantum circuits in approximating high-dimensional functions. While universal approximation theorems exist for parameterized quantum circuits (PQCs), explicit circuit constructions and rigorous bounds on their complexity (width and depth) for specific function spaces remain largely unexplored. The authors focus on the Korobov function space, a subspace of certain Sobolev spaces well-suited for high-dimensional problems due to its compatibility with sparse grid decomposition, which mitigates the curse of dimensionality inherent in traditional grid-based methods. The goal is to design unparameterized quantum circuits that approximate functions in these spaces with guaranteed error rates and to derive the corresponding computational complexity.

Methodology

The authors construct quantum circuits by combining two primary algorithmic frameworks: Quantum Signal Processing (QSP) and the Linear Combination of Unitaries (LCU) method.

1. Chebyshev Polynomial Implementation via QSP:
   The authors leverage the observation that functions in the Korobov space can be approximated by linear combinations of products of Chebyshev polynomials of degrees 0 and 1. They utilize QSP to implement univariate Chebyshev polynomials ($T_r(x)$) as unitary operators. Specifically, they demonstrate that for a specific set of predetermined parameters, a QSP circuit can output the expected value of a Chebyshev polynomial $T_r(x)$ when measured in the $\sigma_z$ basis.

2. Linear Combination via LCU:
   To approximate multivariate functions, the authors employ the LCU technique. This allows the implementation of a linear combination of the unitary operators generated by the QSP circuits. By preparing a superposition of indices corresponding to different terms in the Chebyshev expansion and applying controlled unitaries, the LCU algorithm constructs a single unitary operator whose expectation value corresponds to the desired linear combination of Chebyshev products.

3. Sparse Grid Decomposition:
   The approximation strategy relies on the hierarchical basis construction of sparse grids. Functions in the Korobov space $X_{2,p}([0, 1]^d)$ are expanded into a series of hierarchical basis functions (hat functions). The authors show that these hat functions can be expressed as linear combinations of Chebyshev polynomials of degree 0 and 1. The sparse grid decomposition reduces the number of degrees of freedom required for a given accuracy compared to full tensor-product grids.

4. Circuit Construction:
   The final quantum circuit, $U_{f,\epsilon}$, is constructed by:

   • Encoding the input $x$ into the quantum state.
   • Using QSP to generate unitaries for individual Chebyshev terms.
   • Using LCU to sum these terms with appropriate coefficients derived from the sparse grid expansion.
   • Employing a Hadamard test to estimate the expectation value, which yields the function approximation.

Key Contributions

The paper makes three primary contributions to the emerging field of quantum neural network approximation theory:

1. Extension to Korobov Spaces: The work extends the framework of quantum approximation theory (previously applied to polynomials and smooth functions) to the Korobov function space. This space is a subspace of Sobolev spaces and is particularly relevant for high-dimensional problems where sparse grids are effective.
2. Explicit Unparameterized Circuit Constructions: Unlike previous works that established the existence of approximating circuits, this paper provides explicit, unparameterized quantum circuit designs. These circuits utilize predetermined parameters within the QSP algorithm, avoiding the need for training or optimization of circuit parameters during the approximation phase.
3. Complexity Analysis: The authors derive rigorous worst-case bounds on the circuit depth and width required to achieve a prescribed approximation error $\epsilon$ for functions in $X_{2,p}([0, 1]^d)$. They contrast these findings with classical neural networks, noting that while classical networks often trade width for depth, the proposed quantum constructions feature reduced width but increased depth.

Main Results

The paper establishes the existence of quantum circuits capable of approximating functions $f \in X_{2,p}([0, 1]^d)$ within an error $\epsilon$ in the $L^p$ norm.

• Case $p \in \{2, \infty\}$:
  For functions in $X_{2,p}$ where $p=2$ or $p=\infty$, the authors derive specific complexity bounds.

  • Depth: The circuit depth is bounded by $O\left(d 2^d \epsilon^{-(\frac{1}{2} + \frac{1}{d})} (\log_2 \frac{1}{\epsilon})^{d} \right)$ (simplified from the precise Lambert W function formulation).
  • Width: The circuit width is bounded by $O\left(2^d + \epsilon^{-\frac{1}{d}} \log_2 \frac{1}{\epsilon} \right)$.
    These results rely on the optimal sparse grid decomposition for these specific norms.

• Case $2 < p < \infty$:
  For intermediate $p$, the optimal sparse grid decomposition is not explicitly derived in the paper. However, the authors show that the same decomposition can be used to approximate functions, yielding slightly more complex bounds involving parameters $\alpha = (3p-1)/(2p-1)$ and $\beta = \alpha(d-1)$. The depth and width scale with $\epsilon^{-\frac{p}{d(2p-1)}}$ and logarithmic factors of $1/\epsilon$.

• Approximation Error:
  The constructed function $g$ (output by the circuit) satisfies $\|f - g\|_{L^p} \le \epsilon$. The error rates are shown to be comparable to or exceeding those of classical deep ReLU networks in terms of circuit depth and parameter count under appropriate smoothness conditions.

Significance and Claims

The authors position this work as a foundational step in quantum neural network approximation theory. Their primary significance claims are:

• Theoretical Foundation: The results provide a rigorous theoretical basis for approximating a broad class of high-dimensional functions on quantum computers, moving beyond abstract existence theorems to concrete circuit constructions.
• Complementarity to Classical Methods: The work highlights a complementary relationship between quantum and classical architectures. While classical neural networks often utilize greater width with limited depth, the proposed quantum circuits achieve approximation with reduced width but increased depth, suggesting a different trade-off in architectural design for function approximation.
• Scope of Application: By targeting Korobov spaces, the work addresses high-dimensional problems (such as PDEs) where the curse of dimensionality is a major bottleneck, leveraging sparse grid techniques to maintain efficiency.

The authors explicitly state that their focus is on the fundamental capabilities and limitations of quantum circuits in function approximation, independent of training algorithms or data availability. They acknowledge that practical implementation would require addressing additional factors such as state initialization, training dynamics, and measurement fidelity, which are outside the scope of this theoretical analysis.