Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics

Abstract

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 normalized non-unitary evolution 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 poly-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 this model is powerful enough to decide PostBQP. In the standard uniform circuit-family model this characterization is tight: for any fixed such U, NHBQP(U)=PostBQP=PP. PostBQP is believed intractable, so this suggests that any scalable NH computational advantage must come with a cost limiting its efficiency. Additionally, we study locality-preserving purifications of restricted classes of non-unitary systems. 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 $\Omega (2^{-\text{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.

16+4 pages, comments welcome; V2: significant edits, results reframed in terms of formally defined complexity class

References in corpus (40)

• Complex Extension of Quantum Mechanics
• Non-Hermitian Physics
• Pseudo-Hermiticity versus PT Symmetry: The necessary condition for the reality of the spectrum of a non-Hermitian Hamiltonian
• Improved Simulation of Stabilizer Circuits
• Probing topological invariants in the bulk of a non-Hermitian optical system
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Quantum Zeno Effect and the Many-body Entanglement Transition
• Measurement-driven entanglement transition in hybrid quantum circuits
• Observation of parity-time symmetry breaking transitions in a dissipative Floquet system of ultracold atoms
• Unitary-projective entanglement dynamics
• Quantum Error Correction in Scrambling Dynamics and Measurement-Induced Phase Transition
• Observation of parity-time symmetry breaking in a single spin system
• Faster than Hermitian Quantum Mechanics
• Quantum state tomography across the exceptional point in a single dissipative qubit
• Dynamical purification phase transitions induced by quantum measurements
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• A simple model of quantum trajectories
• Entanglement phase transitions in measurement-only dynamics
• Matchgates and classical simulation of quantum circuits
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Entanglement and purification transitions in non-Hermitian quantum mechanics
• Continuous Phase Transition without Gap Closing in Non-Hermitian Quantum Many-Body Systems
• Full-Counting Many-Particle Dynamics: Nonlocal and Chiral Propagation of Correlations
• Speeding up entanglement generation by proximity to higher-order exceptional points
• Simulating Open Quantum Systems Using Hamiltonian Simulations
• Delayed sudden death of entanglement at exceptional points
• Eternal life of entropy in non-Hermitian quantum systems
• Is Pseudo-Hermitian Quantum Mechanics an Indefinite-Metric Quantum Theory?
• Non-inertial quantum clock frames lead to non-Hermitian dynamics
• Quantum Adiabatic Computation With a Constant Gap is Not Useful in One Dimension
• Solving search problems by strongly simulating quantum circuits
• Ultrafast Entanglement Dynamics in Monitored Quantum Circuits
• Scrambling and operator entanglement in local non-Hermitian quantum systems
• Observation of a non-Hermitian supersonic mode on a trapped-ion quantum computer
• On the sampling complexity of open quantum systems
• Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
• Locality, Correlations, Information, and non-Hermitian Quantum Systems
• Enhanced quantum sensing in time-modulated non-Hermitian systems
• Recognizing critical lines via entanglement in non-Hermitian systems
• Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics