Constrained minimax approximation for quantum signal processing

Yulong Dong; James B. Larsen; Lin Lin; Rahul Sarkar

Source-linked AI summary

Constrained minimax approximation for quantum signal processing

Yulong Dong, James B. Larsen, Lin Lin, Rahul Sarkar

arXiv:2608.30937v1Aug 31, 2026quant-phmath.NA

TL;DR

The paper studies constrained minimax approximation for QSP when finite-grid solutions can violate global magnitude bounds near the fully-coherent regime. It combines a Remez active-set heuristic with nonlinear Fourier retraction, finding that retraction robustly restores feasibility while largely preserving approximation accuracy, despite stability limitations in some components.

Problem
QSP approximation requires parity-constrained polynomials to approximate a target on a fitting set while satisfying magnitude bounds on the full domain, but discretized solutions need not be globally feasible near the fully-coherent boundary.
Method
The paper combines a Remez exchange method with active-set constraint enforcement and uses nonlinear Fourier retraction to map nearly feasible polynomials to feasible QSP phase representations.
Results
Retraction robustly enforced feasibility across tested problems and parameter regimes while largely preserving approximation accuracy; it also produced smaller fitting-set error than rescaling in a reported problem.
Takeaways & Limitations
An adaptive workflow can combine moderately discretized LSIP solving, global-extrema certification, and nonlinear Fourier retraction when the candidate remains infeasible.
Takeaways & Limitations
The Remez active-set heuristic can become suboptimal or highly unstable, while numerical-stability guarantees for the inverse nonlinear Fourier steps may fail and extended precision may be needed.

Abstract

from arXiv · show

Quantum signal processing (QSP) provides a simple and efficient framework for implementing polynomial transformations using quantum circuits. Its classical design stage leads to a constrained minimax approximation problem: find a polynomial of prescribed parity that approximates a target function uniformly on a fitting set while remaining bounded in magnitude by one on the domain $[0,1]$, which can be viewed as a semi-infinite constraint. Discretization converts the problem into a linear program, but feasibility at a set of finitely many sampled points does not ensure feasibility on the whole domain, especially when an optimal approximant reaches the boundary of the feasible set. We investigate two approaches to address this difficulty. A Remez exchange method combined with active-set constraint enforcement is efficient on many tested instances, but its stability depends on the target and problem geometry. We then introduce nonlinear Fourier retraction, which uses QSP completion and phase synthesis to turn a nearly feasible polynomial into phase factors for a feasible QSP polynomial without increasing the degree. Across representative problems, retraction largely preserves approximation accuracy and remains effective on instances where the Remez heuristic is unstable. The resulting workflow connects classical minimax approximation and semi-infinite optimization with nonlinear Fourier analysis, and is implemented in the qsppack software package.

1. Introduction.

The paper formulates QSP design as constrained polynomial minimax approximation and develops two numerical strategies for enforcing feasibility near the fully-coherent regime.

Problem formulation: QSP applications require a parity-constrained polynomial that approximates a continuous target on a fitting set while remaining bounded by one on [0, 1].The fitting set may be an interval or a finite union of closed intervals.
Numerical challenge: Finite-grid discretization can produce an approximant that violates the bound constraints on the full domain, especially near the fully-coherent regime.The issue arises because optimal approximants approach the feasible-set boundary as β converges to one.
Numerical challenge: Existing approaches do not guarantee that successive iterates remain feasible, making residual-infeasibility correction necessary for downstream QSP workflows.This motivates post-processing methods that convert nearly feasible numerical solutions into feasible ones.
Remez strategy: Algorithm 3.1 combines Remez exchange with active-set enforcement to handle feasibility outside the fitting set.The method is designed to reduce reliance on dense discretization.
Retraction strategy: Nonlinear Fourier retraction converts an infeasible approximate solution into QSP phase factors corresponding to a feasible approximate solution.The algorithm is based on the correspondence between QSP and nonlinear Fourier analysis.
Implementation: Both algorithms are implemented in the Python version of qsppack.The package provides documentation and example usage online.

On LLM use.

This section describes the paper’s organization and introduces notation used throughout the later discussion of discretization, nonlinear Fourier analysis, and QSP applications.

Organization: The paper first introduces terminology for optimal solutions, then discusses linear-programming discretization strategies.It subsequently connects QSP with nonlinear Fourier analysis and presents application problems for numerical experiments.

2. Preliminaries.

The preliminaries define the constrained polynomial problem, its discretized LSIP formulation, and the QSP–nonlinear Fourier setting that motivates feasibility correction.

Constrained approximation: The coefficient-to-polynomial map sends parity-restricted coefficient vectors to polynomials of maximum degree d.The feasible coefficient set is closed, convex, and has nonempty interior.
Constrained approximation: The best approximation minimizes the supremum error on Y subject to a magnitude bound on X=[0,1].An optimal solution exists, although the best approximating polynomial need not be unique.
Discretization: Discretization replaces the infinite constraint sets with finite subsets and converts the LSIP into a linear program.The resulting optimal error is a lower bound for the original best error and is expected to converge as the grids become denser.
Discretization: Finite support sets with total size at most d̃+1 can attain the original best error, but prior existence results do not provide a way to compute them or ensure polynomial feasibility.Practical computations therefore use large, sufficiently dense discretizations, which can still yield small global constraint violations.
Feasibility checking: Feasibility can be tested by locating derivative roots in X and checking the polynomial at extrema and endpoints.This procedure identifies violations of the bound constraints across the full domain rather than only at sampled points.
QSP and nonlinear Fourier analysis: QSP completion and inverse nonlinear Fourier methods are numerically stable under a strict margin condition, but that guarantee may fail in the fully-coherent regime.When a nearly feasible polynomial slightly exceeds the bound, the paper motivates a modified treatment for nonlinear Fourier retraction.

3. A Remez and active-set based algorithm.

The proposed heuristic combines Remez exchange with active-set enforcement to approximate on the fitting set while controlling global boundedness. It performs well in many cases but can become suboptimal or unstable when constraints interact unfavorably with the approximation structure.

Algorithm: The algorithm maintains equioscillation points on the target set and active violation points on the constraint set.It updates the polynomial using Remez-like error control on Ω0 and active-set enforcement on Ωc.
Algorithm: Constraint violations are detected at extrema and boundary points, then pinned to the nearest bound ±1.The active set contains candidate extrema satisfying f̃′(ω)=0 or lying on ∂Ωc with |f̃(ω)|>1.
Algorithm: The raw polynomial is scaled by Araw=max{1,∥f̃raw∥∞} after its maximal amplitude is computed.This final scaling step ensures boundedness, but its effect on approximation depends on the overshoot error.
Algorithm: The scaled output preserves raw approximation quality only when the overshoot error is smaller than or comparable to the raw approximation error.Otherwise, enforcing boundedness through scaling can materially degrade the approximation.
Numerical demonstrations: The method agrees well with reference results for gTP except at d=256, where missing equioscillation indicates suboptimality.Other tested degrees show equioscillating error patterns, while numerical-trick parameter changes did not substantially improve the d=256 result.
Numerical demonstrations: For gMI, agreement holds for d≤257, but at d=513 a boundary-transition buffer breaks equioscillation and causes endpoint suboptimality.The polynomial must transition from the upper bound one to smaller values near the endpoint, producing a reflection-like effect.

4. Nonlinear Fourier retraction.

Nonlinear Fourier retraction modifies the Weiss completion procedure to handle nearly feasible polynomials, producing a feasible QSP polynomial without increasing degree. Numerical demonstrations show that retraction generally preserves or improves approximation error, while stability safeguards remain relevant.

Modified Weiss: MWeiss extends the Weiss algorithm to nearly feasible polynomials whose boundary values may satisfy |b(z)| > 1.It partitions the unit circle into regions where |b(z)| is below, above, or equal to one and uses the principal logarithm branch on the region above one.
Modified Weiss: The modified completion yields a holomorphic outer polynomial a* even when the input polynomial exceeds the unit bound.Theorem 4.1 establishes holomorphicity, absence of zeros in the disk, and integrability properties of a*.
Retraction algorithm: Layer stripping or INFFT converts the completed polynomial into a retracted polynomial R(P) satisfying ||R(P)||X ≤ 1.Combining MWeiss with phase recovery gives the nonlinear Fourier retraction algorithm, whose output includes phase data and Chebyshev coefficients.
Stability: Retraction can encounter numerical instability when 1 − |b(z)|^2 is near zero or when INFFT stability conditions fail.The proposed safeguards are slight grid rotation for the logarithm computation and extended-precision arithmetic for INFFT or layer stripping.
Numerical demonstrations: Across the numerical demonstrations, retraction does not increase approximation error and can outperform direct rescaling or a higher-degree windowed polynomial.For gSV, the retracted polynomial has smaller fitting-set error than rescaling; for gMI, degree-101 retraction outperforms the degree-203 windowed polynomial on x ≤ 0.4.
Numerical demonstrations: For finite-grid LSIP solutions, retraction can reduce error over npts = 2^7 through 2^17, while tighter constraints eventually make the original polynomial feasible.In the (1 − ϵ)gSV case with ϵ = 10^-4, feasibility occurs for npts ≥ 2^13 and retraction then leaves the polynomial unchanged.

5. Discussions.

The paper combines global feasibility certification with nonlinear Fourier retraction to address constraint violations in QSP polynomial approximation. Retraction robustly enforces feasibility while largely preserving approximation accuracy, although a semidefinite alternative remains unexplored.

5. Discussions.: Discretized semi-infinite programs can satisfy sampled constraints yet violate global boundedness, which QSP representations require.Residual violations therefore need certification and correction on the full interval.
5. Discussions.: An adaptive workflow solves a moderately discretized problem, certifies global extrema, and retracts only infeasible candidates.Retraction preserves degree and adds modest classical post-processing.
5. Discussions.: The Remez and active-set heuristic performs well on many tested instances but can become numerically unstable.The paper presents nonlinear Fourier retraction as an alternative feasibility-enforcement mechanism.
5. Discussions.: Retraction robustly enforced feasibility while largely preserving approximation accuracy across tested problems and parameter regimes.The implementation is available in the Python version of qsppack.
5. Discussions.: A Fejér–Riesz semidefinite formulation represents the bound constraints, but its performance—especially in the fully-coherent regime—is left for future study.This alternative is not evaluated in the paper.

Appendix A. Omitted proofs and other supporting results.

The appendix establishes that the parity-restricted Chebyshev basis forms a Chebyshev set on the relevant domain, supporting the paper’s approximation-theoretic analysis.

Appendix A. Omitted proofs and other supporting results.: The basis functions form a Chebyshev set on (X, {0}) for odd d and on (X, ∅) for even d.The definition excludes nontrivial linear combinations vanishing on d̃ distinct points outside the specified vanishing set.

A.1. Best approximation examples and existence proof.

The appendix discusses uniqueness, non-uniqueness, and existence of best constrained approximations, then connects an input polynomial to the Laurent polynomial used for QSP phase synthesis.

A.1. Best approximation examples and existence proof.: For a quadratic target with odd degree d = 1, the best approximant has the form c*_1x with 0 ≤ c*_1 ≤ min{1, κ}, and c*_1 is unique.The appendix supports uniqueness by analyzing the objective over the admissible coefficient interval.
A.1. Best approximation examples and existence proof.: Best approximations can be unique or non-unique, depending on the fitting set, target function, and maximum degree.Examples include infinitely many best approximations when the fitting set is {0}.
A.1. Best approximation examples and existence proof.: The existence proof reduces the LSIP to minimizing the fitting-set error over a closed feasible coefficient set.A compact truncation argument yields an attained optimal solution in one case, while interpolation handles the finite-set case.
A.1. Best approximation examples and existence proof.: The appendix defines a function on the combined constraint and fitting points so that a coefficient vector interpolating it gives an optimal LSIP solution.The construction clips target values where bound constraints and fitting constraints overlap.
A.1. Best approximation examples and existence proof.: Given a feasible polynomial P of degree d and parity d mod 2, the construction forms a Laurent polynomial b for subsequent QSP phase-factor synthesis.The definition uses b(e^{2iθ}) := e^{idθ}P(cos θ), with parity-specific Chebyshev expansions.

A.3. Proof of Theorem 4.1.

The proof analyzes the logarithmic and Hilbert-transform construction underlying nonlinear Fourier retraction. It shows continuity of the resulting modulus by exploiting the interval structure of the set where the input polynomial exceeds unit magnitude.

A.3. Proof of Theorem 4.1.: The value a∗(0) is obtained from the zeroth Fourier coefficient through a∗(0) = e^{G(0)} = e^{R̂0}.The proof uses this identity to derive the real and imaginary parts stated in equation (4.4).
A.3. Proof of Theorem 4.1.: The logarithmic construction is integrable, and the set T+ where |b| exceeds one is a finite union of disjoint open intervals.This interval decomposition permits an explicit Hilbert-transform treatment of its indicator function.
A.3. Proof of Theorem 4.1.: The proof establishes continuity of |a∗| on the unit circle by locally canceling singular factors at the interval endpoints.The endpoint argument is repeated for every endpoint appearing in the product representation.

Appendix B. Details for the Remez- and active-set-based method.

The appendix details numerical-stability modifications to the Remez and active-set method and reports that their effectiveness depends on the problem.

Numerical implementation: Target amplitude rescaling replaces g(x) with (1 − ξ)g(x) to stabilize Algorithm 3.1 and prevent the active set from dominating iterations.Approximation subinterval shrinkage is the second stabilization strategy.
Numerical implementation: These two stabilization tricks improve numerical stability in some cases but lack a problem-agnostic parameter choice that consistently ensures convergence for uniform singular value amplification.The reported experiments use ξ = 10−6, η = 0 for matrix inversion and ξ = 0, η = 1.33 × 10−4 for uniform singular value amplification.
Experimental scope: Retraction experiments are repeated for matrix inversion and threshold projector targets to assess reliability across QSP use cases.The appendix describes these experiments as analogous to earlier figures.

C.1. Matrix inversion (extra results).

The matrix-inversion experiments show that retraction preserves the approximation error while restoring feasibility for discretized solutions that violate continuous constraints.

Setup: The experiment uses degree d = 101, npts = 219, and ϵ = 10−4, replacing the earlier target gSV with gMI.The optimal LSIP coefficients are computed in the same way after this target substitution.
Error and feasibility: The LSIP solution can be feasible or infeasible, and the experiment tracks both feasibility and the supremum-norm error on Y.The comparison is between ⟨ĉ∗, Φ⟩ and its retraction R(⟨ĉ∗, Φ⟩).
Error and feasibility: Figure 10 plots the approximation error ||P − gMI||Y for the optimal LSIP polynomial and its retraction.The figure accompanies the feasibility comparison described in the text.
Error and feasibility: Retraction does not increase the approximation error for d ≤ 364, where the LSIP polynomials are infeasible.For d > 364, retraction leaves the polynomial unchanged because the LSIP solution is already feasible.

C.2. Threshold projector.

Threshold-projector experiments show that nonlinear retraction enforces feasibility while retaining nearly the LSIP approximation quality, including in the fully coherent regime.

Degree-128 example: A degree-128 LSIP approximation to gTP exhibits numerous constraint violations, while its nonlinear retraction remains close to the target and enforces the constraints.The comparison is illustrated in Figure 11 with a zoomed-in inset.
Convergence: The convergence experiment for gTP uses degree d = 128 and repeats the earlier retraction procedure with modified parameters.The passage specifies N = 215 as an additional parameter.
Fully coherent regime: Figure 13 reports the threshold-projector approximation-error experiment for the fully coherent regime.The plotted quantity is ||P − gTP||Y.
Fully coherent regime: For fixed npts = 219 and even degrees, LSIP polynomials are infeasible except at d = 256, whereas their retractions are feasible with almost the same supremum-norm error on Y.This comparison concerns the fully coherent regime and the target gTP.
Fully coherent regime: The threshold-projector error displays super-polynomial scaling, unlike the behavior observed in the corresponding matrix-inversion experiments.The passage explicitly contrasts this scaling with Figures 7 and 10.