Physics and computation: An insight from non-Hermitian quantum computing
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
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.