2025/06/03 by Brian Barch, Daniel Lidar, Barch, Brian +2 · 1 citation
Physics and Astronomy · #Quantum Mechanics and Non-Hermitian Physics #Quantum chaos and dynamical systems #Quantum Mechanics and Applications
paper · pdf · doi:10.1103/lhv6-6t1r
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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"> <a:mrow> <a:mi>NHBQP</a:mi> <a:mo>(</a:mo> <a:mi>U</a:mi> <a:mo>)</a:mo> </a:mrow> </a:math> as the computational power of polynomial-size quantum circuits that, in addition to a standard universal unitary gate set, may apply a fixed gate <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"> <b:mi>U</b:mi> </b:math> on <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"> <c:mrow> <c:mi>O</c:mi> <c:mo>(</c:mo> <c:mn>1</c:mn> <c:mo>)</c:mo> </c:mrow> </c:math> qubits that is not proportional to a unitary, with the state renormalized after each use of <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"> <d:mi>U</d:mi> </d:math> . We prove that this model is powerful enough to decide every language in <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"> <e:mi>PostBQP</e:mi> </e:math> (equivalently <f:math xmlns:f="http://www.w3.org/1998/Math/MathML"> <f:mi>PP</f:mi> </f:math> ). Moreover, in the standard uniform circuit-family model, this characterization is tight: For any fixed such nonunitary gate <g:math xmlns:g="http://www.w3.org/1998/Math/MathML"> <g:mi>U</g:mi> <g:mo>,</g:mo> <g:mo> </g:mo> <g:mrow> <g:mi>NHBQP</g:mi> <g:mo>(</g:mo> <g:mi>U</g:mi> <g:mo>)</g:mo> <g:mo>=</g:mo> <g:mi>PostBQP</g:mi> <g:mo>=</g:mo> <g:mi>PP</g:mi> </g:mrow> </g:math> . <h:math xmlns:h="http://www.w3.org/1998/Math/MathML"> <h:mi>PostBQP</h:mi> </h:math> 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 <i:math xmlns:i="http://www.w3.org/1998/Math/MathML"> <i:mrow> <i:mi mathvariant="normal">Ω</i:mi> <i:mo>(</i:mo> <i:msup> <i:mn>2</i:mn> <i:mrow> <i:mo>−</i:mo> <i:mi>poly</i:mi> <i:mo>(</i:mo> <i:mi>n</i:mi> <i:mo>)</i:mo> </i:mrow> </i:msup> <i:mo>)</i:mo> </i:mrow> </i:math> . 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.