Towards End-to-End Quantum Estimation of Non-Hermitian Pseudospectra

• URL: http://arxiv.org/abs/2603.16214v1
• Date: Tue, 17 Mar 2026 07:44:04 GMT
• Title: Towards End-to-End Quantum Estimation of Non-Hermitian Pseudospectra
• Abstract summary: Non-Hermitian many-body systems can be spectrally unstable, so small perturbations may induce large eigenvalue shifts.<n>The pseudospectrum quantifies this instability and provides a perturbation-robust diagnostic.<n>We show that deciding whether a point $zinmathbbC$ is $$-close to the spectrum is PSPACE-hard for $5$-local operators.
• Score: 7.8040425216185225
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Non-Hermitian many-body systems can be spectrally unstable, so small perturbations may induce large eigenvalue shifts. The pseudospectrum quantifies this instability and provides a perturbation-robust diagnostic. For inverse-polynomially small $ε$, we show that deciding whether a point $z\in\mathbb{C}$ is $ε$-close to the spectrum is PSPACE-hard for $5$-local operators, whereas deciding whether $z$ lies in the $ε$-pseudospectrum is QMA-complete for $4$-local operators. This identifies pseudospectrum membership as a natural computational target. We then present a concrete end-to-end quantum framework for deciding pseudospectrum membership, which combines a singular-value estimation step with a dissipative state preparation algorithm. Our Quantum Singular-value Gaussian-filtered Search (QSIGS) combines quantum singular value transformation (QSVT) with classical post-processing to achieve Heisenberg-limited query scaling for singular-value estimation. To prepare suitable input states, we introduce an algorithmic Lindbladian protocol for approximate ground right singular vectors and prove its effectiveness for the Hatano--Nelson model. Finally, we demonstrate the full pipeline on a trapped-ion quantum computer and distinguish points inside and outside the target pseudospectrum near the exceptional point of a minimal non-Hermitian qubit model.

Related papers

• Quantum Decision Theory for Displacement Detection with Finite-Energy GKP States [46.2474896050764]
  We develop a framework for detecting phase-space displacements with finite-energy, $d$-level Gottesman-Kitaev-Preskill (GKP) probes.<n>For single-mode and entanglement-assisted architectures, we derive the Bayesian minimum-error probability.<n>We benchmark the resulting protocols against coherent-state, direction-matched squeezed-vacuum, and twin-beam schemes.
  arXiv  Detail & Related papers  (2026-08-08T10:32:05Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation [3.3636842548621275]
  A central test case for quantum linear system algorithms (QLSA) is elliptic PDEs after a finite element discretization.<n>We present a multilevel framework for this readout problem, motivated by the variance-reduction mechanism of multilevel Monte Carlo.<n>Our algorithm is based on Schur-complement factorization of the corrected Green's operator through a Ritz-complement map.
  arXiv  Detail & Related papers  (2026-05-31T14:47:58Z)
• Adiabatic Quantum Phase Estimation [47.3103723337301]
  Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision $$ in Heisenberg-limited time $T= (1/)$.<n>Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware.<n>We present a simple adiabatic protocol for QPE that achieves the optimal Heisenberg-limited scaling $T = Oleft( frac1 logleft(-1right)right)$ in both the precision $$
  arXiv  Detail & Related papers  (2026-05-21T17:31:36Z)
• Sample-Efficient Estimation of Nonlinear Quantum State Functions [5.641998714611475]
  We introduce the quantum state function (QSF) framework by extending the SWAP test via linear combination of unitaries and parameterized quantum circuits.<n>Our framework enables the implementation of arbitrarily normalized degree-$n$ functions of quantum states with precision.<n>We apply QSF for developing quantum algorithms for fundamental tasks, including entropy, fidelity, and eigenvalue estimations.
  arXiv  Detail & Related papers  (2024-12-02T16:40:17Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Heisenberg-limited adaptive gradient estimation for multiple observables [0.39102514525861415]
  In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty.<n>We provide an adaptive quantum algorithm for estimating the expectation values of $M$ general observables within root mean squared error.<n>Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
  arXiv  Detail & Related papers  (2024-06-05T14:16:47Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
  arXiv  Detail & Related papers  (2023-09-19T22:53:17Z)
• Exponentially improved efficient machine learning for quantum many-body states with provable guarantees [0.0]
  We provide theoretical guarantees for efficient learning of quantum many-body states and their properties, with model-independent applications. Our results provide theoretical guarantees for efficient learning of quantum many-body states and their properties, with model-independent applications.
  arXiv  Detail & Related papers  (2023-04-10T02:22:36Z)
• 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)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Bosonic field digitization for quantum computers [62.997667081978825]
  We address the representation of lattice bosonic fields in a discretized field amplitude basis. We develop methods to predict error scaling and present efficient qubit implementation strategies.
  arXiv  Detail & Related papers  (2021-08-24T15:30:04Z)
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits [1.6328866317851185]
  We show that single-control qubit variants of quantum phase estimation can achieve the Heisenberg limit, em also when one is unable to prepare eigenstates of the system. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well.
  arXiv  Detail & Related papers  (2021-07-09T18:00:10Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

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.