Posted

Brian Barch, Daniel Lidar (Jun 05 2025).
Abstract: We analyze the computational power of non-Hermitian quantum dynamics, i.e., conditional time evolutions that arise when a quantum system is monitored and one postselects on a particular measurement record. We establish an approximate equivalence between post-selection and arbitrary non-Hermitian Hamiltonians. Namely, first we establish hardness in the following sense: Let U=e−iHtU=e^{-iHt} be an NH gate on nn qubits whose smallest and largest singular values differ by at least 2−poly(n)2^{-\text{poly}(n)}. Together with any universal set of unitary gates, the ability to apply such a gate lets one efficiently emulate postselection. The resulting model decides every language in PostBQP; hence, under standard complexity conjectures, fully scalable NH quantum computers are unlikely to be engineered. Second, we establish upper bounds which show that conversely, any non-Hermitian evolution can be written as a unitary on a system-meter pair followed by postselecting the meter. This ``purification'' is compact -- it introduces only O(δ2)O(\delta^{2}) Trotter error per time step δ\delta -- so 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 simulable. Thus, non-Hermitian physics neither guarantees a quantum advantage nor precludes efficient classical simulation: its complexity is controlled by the singular-value radius of the evolution operator and by the structure of its unitary purification.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!