Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing

• URL: http://arxiv.org/abs/2605.12656v1
• Date: Tue, 12 May 2026 19:03:36 GMT
• Title: Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
• Abstract summary: We find the anti-Hermitian query complexity $d_I = (betaI T + log/varepsilon)/loglog (1/varepsilon)$ to be tight, established via Chebyshev coefficient, modified Bessel functions, and Lambert$W$ inversion.<n>A constant-access-operator construction achieves intrinsic barrier $e-2T$ on a restricted domain, though extension to the full bitorus remains open.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multivariate quantum signal processing (M-QSP) has recently been shown to be applicable for non-Hermitian Hamiltonian simulation, opening several problems regarding the optimization landscape, angle-finding, and constant-factor analysis. We resolve several of these problems here. We find the anti-Hermitian query complexity $d_I = Θ(\betaI T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ to be tight, established via Chebyshev coefficient bounds, modified Bessel function asymptotics, and Lambert~$W$ inversion. Fast-forwarding to $d_I = \mathcal{O}(\sqrt{\betaI T})$ is impossible in the bivariate polynomial model, though a linear state-dependent improvement to $d_I = \mathcal{O} β_{\mathrm{eff}} T + \log(1/\varepsilon)/\log\log(1/\varepsilon))$ is achievable. The optimization landscape of M-QSP admits spurious local minima, but a warm-start basin guarantee ensures the two-stage algorithm converges. CRC-exploiting block peeling reduces angle-finding from $\mathcal{O}(d^3)$ to $\mathcal{O}(d^2)$ classical operations, and optimized error allocation yields a leading constant of approximately~$2$ relative to the information-theoretic lower bound. A constant-ratio condition extends to non-identical signal operators, enabling time-dependent non-Hermitian simulation with query complexity $\mathcal{O}(\int_0^T(\alphaR(s) + \betaI(s))\,ds + \log(1/\varepsilon)/\log\log(1/\varepsilon))$. Block-encoding overhead $e^{-2\betaI T}$ holds across all function classes within the walk-operator oracle model, and dilational methods (Schrödingerization) achieve the walk-operator barrier. A precisely characterized direct-access construction achieves the intrinsic barrier $e^{-2ωT}$ (with $ω< \betaI$ for non-commuting Hamiltonians) on a restricted domain, though extension to the full bitorus remains open.

Related papers

• Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians [4.914113120082008]
  We study the cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model.<n>Our main technical tool is an ancilla-compression theorem: any block encoding of an $n$-qubit operator with $a$ clean ancillas and at most $s$ $T$ gates can be compressed to use at most $mina,n+2s$ ancillas.
  arXiv  Detail & Related papers  (2026-09-10T07:01:08Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing [0.0]
  We achieve query-optimal quantum simulations of non-Hermitian Hamiltonians $H_mathrmeff = H_R + iH_I$, where $H_R$ is Hermitian and $H_I succeq 0$.
  arXiv  Detail & Related papers  (2026-05-12T17:40:56Z)
• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  We study numerical integration on $[0,1]$ by quantum amplitude estimation (QAE), focusing on the cost of constructing the amplitude oracle.<n>We introduce a hierarchy of grid function classes $mathcalG_n(d)$, defined by requiring the angle map $_g:0,1nto[0,]$ to be multi of degree at most $d$.<n>For $d=1$ this becomes $O(varepsilon-1log(1/varepsilon))$, improving over classical Monte Carlo for $ge
  arXiv  Detail & Related papers  (2026-04-27T10:23:24Z)
• Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties [3.3728077347699497]
  We investigate Lindbladian fast-forwarding and its applications to estimating Gibbs state properties.<n>Fast-forwarding refers to the ability to simulate a system of time $t$ using significantly fewer than $t$ queries or circuit depth.
  arXiv  Detail & Related papers  (2025-09-11T14:57:53Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Arbitrary Boundary Conditions and Constraints in Quantum Algorithms for Differential Equations via Penalty Projections [5.720812431258812]
  Complicated boundary conditions are essential to accurately describe phenomena arising in nature and engineering.<n>We design an efficient quantum algorithms for solving differential equations with arbitrary boundary conditions.
  arXiv  Detail & Related papers  (2025-06-26T20:14:32Z)
• Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla [18.660349597156266]
  We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms.<n>Our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance.
  arXiv  Detail & Related papers  (2025-04-03T08:24:15Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  Decentralized online convex optimization (D-OCO) is designed to minimize a sequence of global loss functions using only local computations and communications.<n>We develop a novel D-OCO algorithm that can reduce the regret bounds for convex and strongly convex functions to $tildeO(nrho-1/4sqrtT)$ and $tildeO(nrho-1/2log T)$.<n>Our analysis reveals that the projection-free variant can achieve $O(nT3/4)$ and $O(n
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso bandit is an algorithm that estimates the vector defining the reward function as well as its sparse support. We establish non-asymptotic regret upper bounds scaling as $mathcalO( log d + sqrtT )$ in general, and as $mathcalO( log d + sqrtT )$ under the so-called margin condition.
  arXiv  Detail & Related papers  (2020-10-22T19:14:37Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.