Non-Hermitian systems offer new opportunities for quantum optimization and computation. Here, we show that non-Hermitian quantum adiabatic algorithms require not only a real, gapped spectrum, but also a stable pseudospectrum. We propose a novel framework by mapping non-unitary quantum circuits to local Hamiltonian paths, thereby preserving their optimization advantages and shallow depth. While a direct non-Hermitian extension of the Feynman-Kitaev construction suffers severe pseudospectral instability, our history-decoupled construction yields both a controlled pseudospectrum and a real, gapped spectrum. Using the CK benchmark family of maximum independent set problems, we demonstrate polynomial-evolution-time non-Hermitian adiabatic computation that remains robust against perturbations. We further discuss a feasible optical implementation using coupled waveguides with an auxiliary lossy channel. Our work establishes pseudospectral stability, alongside real, gapped spectra, as key principles and a practical route for non-Hermitian quantum adiabatic computation.
Non-Hermitian systems offer new opportunities for quantum optimization and computation. Here, we show that non-Hermitian quantum adiabatic algorithms require not only a real, gapped spectrum, but also a stable pseudospectrum. We propose a novel framework by mapping non-unitary quantum circuits to local Hamiltonian paths, thereby preserving their optimization advantages and shallow depth. While a direct non-Hermitian extension of the Feynman-Kitaev construction suffers severe pseudospectral instability, our history-decoupled construction yields both a controlled pseudospectrum and a real, gapped spectrum. Using the CK benchmark family of maximum independent set problems, we demonstrate polynomial-evolution-time non-Hermitian adiabatic computation that remains robust against perturbations. We further discuss a feasible optical implementation using coupled waveguides with an auxiliary lossy channel. Our work establishes pseudospectral stability, alongside real, gapped spectra, as key principles and a practical route for non-Hermitian quantum adiabatic computation.
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∈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 more realistic computational target. We then present a concrete 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.
The eigenspectrum of a non-normal matrix, which does not commute with its Hermitian conjugate, is a central issue of non-Hermitian physics that has been extensively studied in the past few years. There is, however, another characteristic of a non-normal matrix that has often been overlooked: the pseudospectrum, or the set of spectra under small perturbations. In this paper, we study the dynamics driven by the non-normal matrix (Hamiltonian) realized as a continuous quantum trajectory of the Lindblad master equation in open quantum systems and point out that the dynamics can reveal the nature of unconventional pseudospectrum of the non-normal Hamiltonian. In particular, we focus on the transient dynamics of the norm of an unnormalized quantum state evolved with the non-normal Hamiltonian, which is related to the probability for observing the trajectory with no quantum jump. We formulate the transient suppression of the decay rate of the norm due to the pseudospectral behavior and derive a non-Hermitian/non-normal analog of the time-energy uncertainty relation. We also consider two methods to experimentally realize the non-normal dynamics and observe our theoretical findings on quantum computers: one uses a technique to realize nonunitary operations on quantum circuits and the other leverages a quantum-classical hybrid algorithm called variational quantum simulation. Our demonstrations using cloud-based quantum computers provided by IBM Quantum exhibit the frozen dynamics of the norm in transient time, which can be regarded as a non-normal analog of the quantum Zeno effect.
Engineering quantum bath networks through non-Hermitian subsystem Hamiltonians has recently emerged as a promising strategy for qubit cooling, state stabilization, and fault-tolerant quantum computation. However, scaling these systems while maintaining precise control over their complex interconnections, especially in the optical domain, poses significant challenges in both theoretical modeling and physical implementation. In this work, drawing on principles from quantum and mathematical physics, we introduce a systematic framework for constructing non-Hermitian subsystems within entirely Hermitian photonic platforms. In particular, controlled exponential decay without actual absorption loss is realized in finite 1-D waveguide chains through discrete-to-continuum coupling and Lanczos transformations. Using this new methodology, we implement parity-time symmetric quantum systems and experimentally demonstrate that these artificial bath environments accurately replicate the dynamics of non-Hermitian arrangements in both single- and multi-photon excitation regimes. Since the non-Hermitian subsystem response deterministically arises from an artificially built Hermitian bath, the quantum evolution can be monitored via post-selection in this fully conservative configuration. This approach bridges the gap between theoretical models and experimental realizations, thus paving the way for exploiting quantum bath engineering in advanced information processing and emerging quantum technologies.
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Γ such that $γ_\min = Θ\left(\min_sΓ(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(γ_\min^{-1}\right)$ with $O\left(\log(γ_\min^{-1})\right)$ oracle queries, where $γ_\min = \min_s γ(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that ∥dH/ds∥≈γ(s) and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle Γ for the problem of finding the minimum point m=argminuW(u) of the cost function W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I−∣V∣−1∑u,v∈V∣u⟩⟨v∣. Requiring only that W have a constant lower bound on its spectral gap and upper bound κ on its spectral ratio, our QAO algorithm returns m with probability (1−ε)(1−e−1/ε) in time O(ε−1[∣V∣+(κ−1)2/3∣V∣2/3]). This achieves a quantum advantage for all κ, and recovers Grover scaling up to logarithmic factors when κ≈1. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime O(ε−1[∣V∣+(κ−1)2/3∣V∣2/3]) even when κ is not known beforehand.
Non-Hermitian (NH) quantum systems demonstrate striking differences from their Hermitian counterparts, leading to claims of NH advantage in areas ranging from metrology to entanglement generation. We show that in the context of quantum computation, any such NH advantage is unlikely to be scalable as an efficient computational resource: If coherent nonunitary evolution with renormalization could be realized with only polynomial overhead, then the resulting model could implement postselection, implying implausibly strong complexity-theoretic power under standard assumptions. We define NHBQP ( U ) as the computational power of polynomial-size quantum circuits that, in addition to a standard universal unitary gate set, may apply a fixed gate U on O ( 1 ) qubits that is not proportional to a unitary, with the state renormalized after each use of U . We prove that this model is powerful enough to decide every language in PostBQP (equivalently PP ). Moreover, in the standard uniform circuit-family model, this characterization is tight: For any fixed such nonunitary gate U , NHBQP ( U ) = PostBQP = PP . PostBQP is believed intractable, so this suggests that any scalable NH computational advantage must come with a compensating cost limiting its efficiency. Additionally, we study simulation complexity of restricted classes of nonunitary systems by purifying them to postselected unitary evolution in a form preserving system locality. Using this framework, we show that unitary gates with postselection can simulate not only evolution under NH Hamiltonians but arbitrary quantum trajectories. Any NH model whose purification lies in a strongly simulable unitary family (e.g., Clifford, matchgate, or low-bond-dimension tensor-network circuits) remains efficiently classically simulable, provided the relevant postselected events occur with probability Ω ( 2 − poly ( n ) ) . Thus, adding non-Hermiticity to a universal unitary system makes it infeasibly computationally powerful, while adding it to a strongly simulable system adds no computational power in this setting.
Nontrivial spectral properties of non-Hermitian systems can give rise to intriguing effects that lack counterparts in Hermitian systems. For instance, when dynamically varying system parameters along a path enclosing an exceptional point (EP), chiral mode conversion occurs. A recent study [Phys. Rev. Lett. 133, 113802 (2024)] demonstrates the achievability of pure adiabatic state transfer by specifically selecting a trajectory in the system parameter space where the corresponding evolution operator exhibits a real spectrum while winding around an EP. However, the intended adiabatic state transfer becomes fragile when taking into account the effect of the nonadiabatic transition. In this work, we propose a scheme for achieving robust and rapid adiabatic state transfer in time-modulated two-level non-Hermitian systems by appropriately modulating the system Hamiltonian and time-evolution trajectory. Numerical simulations confirm that a complete adiabatic transfer can always be achieved even under nonadiabatic conditions after one period for different initialized adiabatic states, and the scheme remains insensitive to moderate fluctuations in control parameters. Therefore, this scheme offers alternative approaches for quantum-state engineering in non-Hermitian systems.