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.18012 · Physical Review A

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

Qi Zhang, Biao Wu

Published Feb 25, 2026• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/mywt-m86w

Related papers

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

QUANTUM COMPUTATION

Dorit Aharonov

In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.

arXiv:quant-ph/9812037•WORLD SCIENTIFIC eBooks•Mar 1, 1999•139 citations

Quantum computing: beyond the limits of conventional computation†

Marius Nagy, Selim G. Akl

The quantum model of computation not only offers entirely new ways to manipulate information, but also allows information processing tasks to be formulated in unconventional, genuine quantum mechanical terms. We show that the task of distinguishing among entangled quantum states combines entanglement and non-determinism in a way that makes the quantum solution impossible to simulate on any classical machine (even one equipped with the same measurement capabilities as the quantum computational device). A new class of information processing tasks is thus uncovered whose members are readily carried out by a quantum computer, yet are impossible to perform on any classical machine (whether deterministic or probabilistic). In the broad, unconventional context created by quantum mechanics, the computational power of a quantum computer is therefore strictly greater than that of a classical computer.

International Journal of Parallel Emergent and Distributed Systems•Mar 30, 2007•23 citations

Computational complexity and simulability of non-Hermitian quantum dynamics

Brian Barch, Daniel A. Lidar

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.

arXiv:2506.03435•Physical Review Research•Jun 24, 2026•6 citations

Quantum mechanical computation

James D. Brasher

The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 1, 1994•0 citations

The Power of the Lorentz Quantum Computer

Qi Zhang, Biao Wu

We analyze the power of the recently proposed Lorentz quantum computer (LQC), a theoretical model leveraging hyperbolic bits (hybits) governed by complex Lorentz transformations. We define the complexity class BLQP (bounded-error Lorentz quantum polynomial-time) and demonstrate its equivalence to the complexity class P♯P (the class of problems solvable by a deterministic polynomial-time Turing machine with access to a ♯P oracle). LQC algorithms are shown to solve NP-hard problems, such as the maximum independent set (MIS), in polynomial time, thereby placing NP and co-NP within BLQP. Furthermore, we establish that LQC can efficiently simulate quantum computing with postselection (PostBQP), while the reverse is not possible, highlighting LQC's unique "super-postselection" capability. By proving BLQP =P♯P, we situate the entire polynomial hierarchy (PH) within BLQP and reveal profound connections between computational complexity and physical frameworks like Lorentz quantum mechanics. These results underscore LQC's theoretical superiority over conventional quantum computing models and its potential to redefine boundaries in complexity theory.

arXiv:2403.04170•Entropy•Feb 28, 2026•3 citations
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.
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.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
The quantum model of computation not only offers entirely new ways to manipulate information, but also allows information processing tasks to be formulated in unconventional, genuine quantum mechanical terms. We show that the task of distinguishing among entangled quantum states combines entanglement and non-determinism in a way that makes the quantum solution impossible to simulate on any classical machine (even one equipped with the same measurement capabilities as the quantum computational device). A new class of information processing tasks is thus uncovered whose members are readily carried out by a quantum computer, yet are impossible to perform on any classical machine (whether deterministic or probabilistic). In the broad, unconventional context created by quantum mechanics, the computational power of a quantum computer is therefore strictly greater than that of a classical computer.
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.
The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.
We analyze the power of the recently proposed Lorentz quantum computer (LQC), a theoretical model leveraging hyperbolic bits (hybits) governed by complex Lorentz transformations. We define the complexity class BLQP (bounded-error Lorentz quantum polynomial-time) and demonstrate its equivalence to the complexity class P♯P (the class of problems solvable by a deterministic polynomial-time Turing machine with access to a ♯P oracle). LQC algorithms are shown to solve NP-hard problems, such as the maximum independent set (MIS), in polynomial time, thereby placing NP and co-NP within BLQP. Furthermore, we establish that LQC can efficiently simulate quantum computing with postselection (PostBQP), while the reverse is not possible, highlighting LQC's unique "super-postselection" capability. By proving BLQP =P♯P, we situate the entire polynomial hierarchy (PH) within BLQP and reveal profound connections between computational complexity and physical frameworks like Lorentz quantum mechanics. These results underscore LQC's theoretical superiority over conventional quantum computing models and its potential to redefine boundaries in complexity theory.