Skip to content

Constrained minimax approximation for quantum signal processing

Aug 2026 · 1 citation · 53 references
Physics Computer Science Mathematics

TL;DR

This work introduces 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.

Abstract

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.

View source

Similar papers

Weighted Quantum Signal Processing: Low-Depth Polynomial Approximation with Applications to Kolmogorov-Arnold Networks

Weighted Quantum Signal Processing is introduced, an extension of QSP in which a weight function is assigned to the central rotation operator, which provides a deeper understanding of QSP and yields expressive and parameter-efficient neural architectures, highlighting the potential of WQSP as a scalable primitive for q...

Rohit Sarma Sarkar, Rupayan Bhattacharjee, E. F. Combarro et al. · 0 citations
Sep 2026

Complexity Barriers to State Preparation in Quantum Approximate Optimization

This work proves that the barrier to reaching the classical threshold does not arise from a need for entanglement, and separates the effects of relaxation tightness and energy approximation from operational accessibility.

Stuart Hadfield · 5 citations
Preprint Aug 2026

Linearised quantum signal processing

This work shows that UHET can be interpreted as a (randomised) linearisation of Generalised QSP (GQSP), and introduces a linearised variant of (Hamiltonian-based) QSVT, which is called Universal Hamiltonian Singular Value Transformation (UHSVT).

Marek Arsenault, Hlér Kristjánsson · 0 citations
Preprint Aug 2026

Improved constant factors for qubitized Hamiltonian simulation

This work treats the Bessel tail in the Jacobi-Anger series using Kapteyn's and Watson's inequalities, thereby reducing the overhead estimates for all Hamiltonian simulation tasks on quantum computers by a factor of $\approx e/2$.

Matthew Pocrnic, Danial Motlagh · 0 citations
Preprint Aug 2026

Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

Heavy-Hitter QAOA is introduced, which preserves finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA and preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size.

Chinonso Onah, K. Michielsen · 0 citations
Preprint Aug 2026

Exact and Efficient Circuit Construction for Block Encoding Matrix Polynomials

The resulting algorithm achieves a computational cost of $\mathcal{O}(d\log d)$ for explicitly constructing block encodings of matrix polynomials, improving upon the best-known theoretical bounds of previous methods.

Taehee Ko · 0 citations

Related blog posts

Microsoft Research Blog Nov 12, 2026

Microsoft Research Focus – Edition #98

What's new in research at Microsoft? Host Anson Ho explores the latest, including AI-powered universal translation, a breakthrough in a 31-year-old mathematics challenge, and advances making AI coding agents faster and more efficient.  The post Microsoft Research Focus – Edition #98 appeared first on Microsoft Research.

Microsoft Research Blog Nov 5, 2026

Formally verifying agent-written full-stack web apps with PDD Kit

AI agents can generate code at a scale that’s hard for humans to review line-by-line. PDD Kit helps ensure the code is doing what the developer intended by creating formal specifications and testing against them. It converts developer intent into a Verus specification, proves AI-generated code meets it for every input, and uses tests where proofs aren't practical. Developers review intent, not every line. The post Formally verifying agent-written full-stack web apps with PDD Kit appeared first o…

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.