Nearly optimal polynomial approximations for the quantum singular value transform

• URL: http://arxiv.org/abs/2607.12190v1
• Date: Mon, 13 Jul 2026 22:18:53 GMT
• Title: Nearly optimal polynomial approximations for the quantum singular value transform
• Abstract summary: We introduce approximations of the even and odd step functions on the interval $[-1,$] with simple Chebyshev coefficients.<n>We derive rigorous error bounds that are nearly optimal in the sense that their error deviates from the theoretically optimal error by a multiplicative factor.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce polynomial approximations of the even and odd step functions on the interval $[-1,1]$ with simple Chebyshev coefficients, making their numerical implementation straightforward. We derive rigorous error bounds and demonstrate that these polynomials are nearly optimal in the sense that their error deviates from the theoretically optimal error by a multiplicative factor that grows logarithmically with the polynomial order. From these polynomials, we derive related nearly optimal polynomial approximations that can be used to perform quantum phase estimation, linear amplitude amplification, eigenvalue thresholding, and other quantum algorithms using the quantum singular value transform.

Related papers

• Quantum estimates for classical polynomial optimization [0.0]
  The problem of finding bounds on tensors is both difficult and important given its applications to questions ranging from dynamical stability in complex landscapes to data analysis.<n>From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and largest eigenvalues of the coefficient corresponding to the given amount.<n>In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on Stricharts.
  arXiv  Detail & Related papers  (2026-07-28T08:34:11Z)
• The Complexity of Min-Max Optimization for Quadratic Polynomials [71.85811744604827]
  We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratics.<n>As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix.
  arXiv  Detail & Related papers  (2026-06-15T17:37:13Z)
• Constrained Optimal Polynomials for Quantum Linear System Solvers [0.0]
  We introduce constrained optimal approximations as a framework for solving Krylov subspace theory.<n>We develop two classes of solvers: Constrained Uniform Polynomial solvers and Adaptive Polynomial solvers.
  arXiv  Detail & Related papers  (2026-04-22T12:55:15Z)
• Scalable quantum circuit generation for iterative ground state approximation using Majorana Propagation [0.2419826154435114]
  ADAPT-VMPE produces circuits for approximating the ground state of molecular Hamiltonians.<n>We construct up to 100-qubit anstze for a strongly correlated photosensitizer undergoing human clinical trials for cancer treatment.
  arXiv  Detail & Related papers  (2026-03-24T17:14:37Z)
• Quadratically Shallow Quantum Circuits for Hamiltonian Functions [3.218714138503326]
  Many quantum algorithms for ground-state preparation and energy estimation require the implementation of high-degrees of a Hamiltonian to achieve better convergence rates.<n>We show that various Hamiltonian functions for ground-state preparation and energy estimation can be implemented with quadratically shallow circuits.
  arXiv  Detail & Related papers  (2025-10-05T06:43:18Z)
• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  We present a new method for calculating expectation values of operators that can be expressed as a linear combination of unitary (LCU) operators.<n>This method is general for any quantum algorithm and is of particular interest in the acceleration of variational quantum algorithms.
  arXiv  Detail & Related papers  (2025-03-03T17:15:23Z)
• EHands: Quantum Protocol for Polynomial Computation on Real-Valued Encoded States [0.08209843760716957]
  We present EHands, a quantum-native protocol for implementing multivariable transformations on quantum processors.<n>EHands operates directly on vectorized real-valued inputs prepared in the initial state.<n>The protocol's effectiveness is demonstrated through experimental validation on IBM's Heron-class quantum processors.
  arXiv  Detail & Related papers  (2025-02-21T20:52:16Z)
• Nonlinear quantum computation by amplified encodings [0.0]
  We present a novel framework for high-dimensional nonlinear quantum computation.<n>We show that a quantum advantage, characterized by a logarithmic scaling of complexity with the dimension of the problem, is preserved.<n>While Newton's method attains near-optimal theoretical complexity, the fixed-point iteration may be better suited to near-term noisy hardware.
  arXiv  Detail & Related papers  (2024-11-25T14:37:57Z)
• Complementary polynomials in quantum signal processing [0.0]
  To implement a given $P$, one must first construct a corresponding complementary $Q$.<n>Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis.<n>We present a new approach to complementarys using complex analysis.
  arXiv  Detail & Related papers  (2024-06-06T16:47:11Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Structural aspects of FRG in quantum tunnelling computations [68.8204255655161]
  We probe both the unidimensional quartic harmonic oscillator and the double well potential. Two partial differential equations for the potential V_k(varphi) and the wave function renormalization Z_k(varphi) are studied.
  arXiv  Detail & Related papers  (2022-06-14T15:23:25Z)
• Direct Optimal Control Approach to Laser-Driven Quantum Particle Dynamics [77.34726150561087]
  We propose direct optimal control as a robust and flexible alternative to indirect control theory. The method is illustrated for the case of laser-driven wavepacket dynamics in a bistable potential.
  arXiv  Detail & Related papers  (2020-10-08T07:59:29Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.