Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
This work clarifies the computational limits of non-Hermitian quantum advantage for quantum computing researchers, showing that scalable advantage is unlikely under standard complexity assumptions.
The authors prove that non-Hermitian quantum dynamics, if efficiently realizable, would enable postselection and thus imply implausible computational power (PostBQP = PP). They also show that non-Hermiticity adds no computational power to classically simulable systems like Clifford or matchgate circuits.
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 $Ω(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.