Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2506.03435 · Physical Review Research

Computational complexity and simulability of non-Hermitian quantum dynamics

Brian Barch, Daniel A. Lidar

Published Jun 24, 2026• 6 citations
arXivHTMLPDF

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 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.

DOI
10.1103/lhv6-6t1r

Related papers

Nonunitary quantum computation in the ground space of local Hamiltonians

Naïri Usher, Matty J. Hoban, Dan E. Browne

A central result in the study of quantum Hamiltonian complexity is that the $k$-local Hamiltonian problem is quantum-Merlin-Arthur--complete. In that problem, we must decide if the lowest eigenvalue of a Hamiltonian is bounded below some value, or above another, promised one of these is true. Given the ground state of the Hamiltonian, a quantum computer can determine this question, even if the ground state itself may not be efficiently quantum preparable. Kitaev's proof of QMA-completeness encodes a unitary quantum circuit in QMA into the ground space of a Hamiltonian. However, we now have quantum computing models based on measurement instead of unitary evolution; furthermore, we can use postselected measurement as an additional computational tool. In this work, we generalize Kitaev's construction to allow for nonunitary evolution including postselection. Furthermore, we consider a type of postselection under which the construction is consistent, which we call tame postselection. We consider the computational complexity consequences of this construction and then consider how the probability of an event upon which we are postselecting affects the gap between the ground-state energy and the energy of the first excited state of its corresponding Hamiltonian. We provide numerical evidence that the two are not immediately related by giving a family of circuits where the probability of an event upon which we postselect is exponentially small, but the gap in the energy levels of the Hamiltonian decreases as a polynomial.

arXiv:1703.08118•Physical Review A•Sep 12, 2017•15 citations

Non-Hermitian Computers Need No Complex Numbers

Qi Zhang

In traditional quantum computing, it has been established that real quantum computation augmented with non-Clifford gates is as powerful as universal quantum computation. Here we investigate this phenomenon in the non-Hermitian setting. We show that a non-Hermitian quantum computer equipped with the real gate set ${H, \text{CCNOT}, G}$, where $G = \operatorname{diag}(g^{-1}, g)$ with $g > 0$ and $g \neq 1$, can solve problems in $\text{P}^{\sharp\text{P}}$ in polynomial time, matching the capability of its universal non-Hermitian counterpart ${H, T, \text{CNOT}, G}$. This demonstrates that non-unitarity, rather than universality, is the essential resource, and that complex numbers are unnecessary.

quant-pharXiv:2605.28152•May 28, 2026•0 citations

Physics and computation: An insight from non-Hermitian quantum computing

Qi Zhang, Biao Wu

We elucidate the profound connection between physics and computation by proposing and examining the model of the non-Hermitian quantum computer (NQC). In addition to conventional quantum gates such as the Hadamard, phase, and CNOT gates, this model incorporates a non-unitary quantum gate $G$. We show that NQC is extraordinarily powerful, capable of solving not only all NP problems but also all problems within the complexity class $\text{P}^{\sharp\text{P}}$ in polynomial time. We investigate two physical schemes for implementing the non-unitary gate $G$ and find that the remarkable computational power of NQC originates from the exponentially large physical resources required.

arXiv:2506.18012•Physical Review A•Feb 25, 2026•4 citations

Quantum computers that can be simulated classically in polynomial time

Leslie Gabriel Valiant

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•90 citations

Quantum Circuits That Can Be Simulated Classically in Polynomial Time

Leslie Gabriel Valiant

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 × 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. Therefore, it is possible that, The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent with one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

SIAM Journal on Computing•Jan 1, 2002•318 citations

Probabilistic imaginary-time evolution algorithm based on nonunitary quantum circuits

Hao-Nan Xie, Shi-Jie Wei, Fan Yang +4 more

Imaginary-time evolution is a powerful tool in the study of quantum physics. However, existing classical algorithms for simulating imaginary-time evolution suffer from high computational complexity as the dimension of the quantum system increases. In this study we propose a quantum algorithm for implementing imaginary-time evolution using nonunitary quantum circuits with one ancillary qubit. The success probability of our algorithm is a polynomial function of the output error and can be enhanced by reorganizing the terms of the Hamiltonian. To illustrate the practicality of our algorithm on current quantum devices, we conduct a demonstration on superconducting and trapped-ion quantum processors to calculate the ground-state energy and determine the most stable molecular structure of ${\mathrm{H}}_{2}$. Additionally, we validate the feasibility of our algorithm by numerically simulating the ground-state energies of LiH molecules and the quantum Ising chain. In contrast to existing algorithms, our method provides a systematic approach to construct the required nonunitary circuits using universal quantum gates, making it suitable for experimental implementation. Our algorithm opens up possibilities for exploring other physical phenomena such as finite-temperature properties and non-Hermitian systems.

arXiv:2210.05293•Physical Review A•May 9, 2024•19 citations
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.
A central result in the study of quantum Hamiltonian complexity is that the kkk-local Hamiltonian problem is quantum-Merlin-Arthur--complete. In that problem, we must decide if the lowest eigenvalue of a Hamiltonian is bounded below some value, or above another, promised one of these is true. Given the ground state of the Hamiltonian, a quantum computer can determine this question, even if the ground state itself may not be efficiently quantum preparable. Kitaev's proof of QMA-completeness encodes a unitary quantum circuit in QMA into the ground space of a Hamiltonian. However, we now have quantum computing models based on measurement instead of unitary evolution; furthermore, we can use postselected measurement as an additional computational tool. In this work, we generalize Kitaev's construction to allow for nonunitary evolution including postselection. Furthermore, we consider a type of postselection under which the construction is consistent, which we call tame postselection. We consider the computational complexity consequences of this construction and then consider how the probability of an event upon which we are postselecting affects the gap between the ground-state energy and the energy of the first excited state of its corresponding Hamiltonian. We provide numerical evidence that the two are not immediately related by giving a family of circuits where the probability of an event upon which we postselect is exponentially small, but the gap in the energy levels of the Hamiltonian decreases as a polynomial.
In traditional quantum computing, it has been established that real quantum computation augmented with non-Clifford gates is as powerful as universal quantum computation. Here we investigate this phenomenon in the non-Hermitian setting. We show that a non-Hermitian quantum computer equipped with the real gate set H,CCNOT,G{H, \text{CCNOT}, G}H,CCNOT,G, where G=diag⁡(g−1,g)G = \operatorname{diag}(g^{-1}, g)G=diag(g−1,g) with g>0g > 0g>0 and g≠1g \neq 1g=1, can solve problems in P♯P\text{P}^{\sharp\text{P}}P♯P in polynomial time, matching the capability of its universal non-Hermitian counterpart H,T,CNOT,G{H, T, \text{CNOT}, G}H,T,CNOT,G. This demonstrates that non-unitarity, rather than universality, is the essential resource, and that complex numbers are unnecessary.
We elucidate the profound connection between physics and computation by proposing and examining the model of the non-Hermitian quantum computer (NQC). In addition to conventional quantum gates such as the Hadamard, phase, and CNOT gates, this model incorporates a non-unitary quantum gate GGG. We show that NQC is extraordinarily powerful, capable of solving not only all NP problems but also all problems within the complexity class P♯P\text{P}^{\sharp\text{P}}P♯P in polynomial time. We investigate two physical schemes for implementing the non-unitary gate GGG and find that the remarkable computational power of NQC originates from the exponentially large physical resources required.
A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.
A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 × 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. Therefore, it is possible that, The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent with one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.
Imaginary-time evolution is a powerful tool in the study of quantum physics. However, existing classical algorithms for simulating imaginary-time evolution suffer from high computational complexity as the dimension of the quantum system increases. In this study we propose a quantum algorithm for implementing imaginary-time evolution using nonunitary quantum circuits with one ancillary qubit. The success probability of our algorithm is a polynomial function of the output error and can be enhanced by reorganizing the terms of the Hamiltonian. To illustrate the practicality of our algorithm on current quantum devices, we conduct a demonstration on superconducting and trapped-ion quantum processors to calculate the ground-state energy and determine the most stable molecular structure of H2{\mathrm{H}}_{2}H2​. Additionally, we validate the feasibility of our algorithm by numerically simulating the ground-state energies of LiH molecules and the quantum Ising chain. In contrast to existing algorithms, our method provides a systematic approach to construct the required nonunitary circuits using universal quantum gates, making it suitable for experimental implementation. Our algorithm opens up possibilities for exploring other physical phenomena such as finite-temperature properties and non-Hermitian systems.