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

This paper proposes a non-Hermitian quantum computing model capable of solving all NP and $\text{P}^{\sharp\text{P}}$ problems in polynomial time by incorporating a non-unitary gate, demonstrating that its extraordinary computational power stems from the exponentially large physical resources required for implementation.

The Gist

Here is an explanation of the paper "Physics and computation: An insight from non-Hermitian quantum computing," translated into simple, everyday language with creative analogies.

The Big Idea: The "Super-Charged" Computer

Imagine you have a standard quantum computer. It's already incredibly fast at solving certain puzzles (like factoring large numbers) that would take a regular computer millions of years. But there's a huge class of even harder puzzles (called NP problems) that even quantum computers struggle with. They can't solve them quickly.

The authors of this paper asked a bold question: "What if we broke the rules?"

In standard physics, quantum computers must follow a strict rule called unitarity. Think of this like a "Conservation of Probability" law. If you have a bag of marbles representing all possible answers, the total number of marbles must always stay the same. You can shuffle them around, but you can't create new ones or throw any away.

This paper proposes a Non-Hermitian Quantum Computer (NQC). This is a theoretical machine that breaks that rule. It allows us to add or remove marbles from our bag of possibilities at will.

The Magic Tool: The "Volume Knob" Gate

To make this computer work, the authors introduce a special new gate called Gate G.

• Standard Gates: Imagine a standard quantum gate is like a mixer. It takes your ingredients (quantum states) and blends them perfectly, but the total volume of the soup stays the same.
• Gate G: This is like a magical volume knob. If you have a "Yes" answer and a "No" answer, Gate G can turn the volume of the "Yes" answer up to 1,000,000x while turning the "No" answer down to almost zero.

Why is this amazing?
Usually, finding the right answer in a quantum computer is like finding a needle in a haystack. You have to search through millions of possibilities.
With Gate G, you can instantly amplify the needle until it's the size of a skyscraper, and shrink the haystack until it's invisible. Suddenly, finding the answer is trivial. You can solve incredibly hard problems (like the "Maximum Independent Set" problem) in seconds instead of years.

The paper proves that with this tool, the computer becomes so powerful it can solve all problems in a class called P♯P, which includes almost every difficult math problem imaginable.

The Catch: The "Exponential Cost"

So, why don't we have these computers yet? Why isn't this the future of technology?

The paper delivers a harsh reality check: To build this machine, you need an impossible amount of resources.

The authors propose two ways to build this "Volume Knob" (Gate G) using real physics, and both hit a massive wall:

Scheme 1: The "Particle Pump" (Cold Atoms)

Imagine trying to build this gate using a cloud of atoms in a double-well trap.

• The Idea: To amplify the "Yes" answer, you need to pump more atoms into the "Yes" state. To suppress the "No" answer, you need to suck atoms out of the "No" state.
• The Problem: The math shows that to get a clear answer for a problem of size $n$, you need to pump in $2^n$ atoms.
• The Analogy: If you want to solve a problem with just 100 variables, you would need more atoms than there are stars in the observable universe. It's like trying to fill the entire ocean with a single teaspoon of water, but you need to do it instantly. The physical resources required are exponentially huge.

Scheme 2: The "Lucky Coin Flip" (Postselection)

This is a different trick where you try to force the computer to work by only keeping the "lucky" outcomes where the gate worked.

• The Idea: You run the computer, and if it gives the right answer, you keep it. If it fails, you throw it away and try again.
• The Problem: Because the "No" answers are so much stronger than the "Yes" answers initially, the chance of getting a "lucky" result is infinitesimally small.
• The Analogy: It's like trying to win the lottery every single time you buy a ticket. To guarantee a win, you would need to buy $2^n$ tickets simultaneously. Again, for a problem of size 100, you'd need more lottery tickets than there are atoms in the universe.

The Deep Insight: Physics vs. Computation

The most important conclusion of the paper isn't that we can build this computer, but why we can't.

The authors show a profound link between Computational Power and Physical Resources.

• To get a computer that is "too powerful" (solving NP-hard problems instantly), nature demands a price: Exponential physical resources.
• It's as if the universe has a "tax" on intelligence. If you want to solve a problem that is exponentially hard, you must pay with exponentially many particles or energy.

Summary in a Nutshell

1. The Dream: The authors designed a theoretical quantum computer that breaks the rules of standard physics to solve the hardest math problems instantly.
2. The Magic: It uses a special "Volume Knob" to amplify the correct answer and silence the wrong ones.
3. The Reality Check: To build this "Volume Knob" in the real world, you would need to use more atoms or energy than exist in the entire universe.
4. The Lesson: You can't cheat physics. If you want a computer that is exponentially smarter, you have to pay with exponentially more physical stuff. The "magic" of non-Hermitian computing is real, but it's too expensive to buy.

Final Thought: The paper suggests that the reason our current computers aren't solving every problem instantly is that the universe simply doesn't have enough "stuff" (particles/energy) to let us do it without breaking the laws of physics.

Technical Summary

Here is a detailed technical summary of the paper "Physics and computation: An insight from non-Hermitian quantum computing" by Qi Zhang and Biao Wu.

1. Problem Statement

The paper addresses the fundamental limitation of standard quantum computers (BQP), which, despite their power (e.g., Shor's algorithm), cannot efficiently solve NP-complete or $\#P$-complete problems in polynomial time. Previous theoretical proposals to overcome this barrier—such as utilizing closed timelike curves, nonlinear gates, or postselection—often rely on hypothetical physics or unphysical assumptions. The authors aim to explore the relationship between physical realizability and computational power by proposing a Non-Hermitian Quantum Computer (NQC) model. The core question is whether relaxing the unitarity constraint (allowing non-unitary evolution) can yield exponential computational advantages, and if so, what the physical costs are.

2. Methodology

The authors develop a theoretical framework and analyze its physical implementation through the following steps:

• Theoretical Model (NQC):

  • They define a computing model using qubits where the unitarity constraint on gates is relaxed.
  • The model introduces a specific non-unitary single-qubit gate $G$:
    $$G = \begin{pmatrix} g^{-1} & 0 \\ 0 & g \end{pmatrix}$$
    where $g > 0, g \neq 1$.
  • The universal gate set consists of the standard Hadamard ($H$), Phase ($T$), and CNOT gates, plus the non-unitary $G$ gate.
  • They define the complexity class BNQP (Bounded-error Non-Hermitian Quantum Polynomial time) for problems solvable by this model.

• Algorithmic Demonstration:

  • To prove the model's power, they design an algorithm to solve the Maximum Independent Set (MIS) problem, which is NP-hard.
  • The algorithm uses an oracle to distinguish Independent Sets (IS) from non-ISs.
  • Crucially, it employs the $G$ gate (specifically controlled-$G^r$) to exponentially amplify the amplitude of the "correct" solution states (those corresponding to the MIS) while suppressing others.
  • By measuring an auxiliary qubit after $r \propto n$ applications of the gate, the probability of obtaining the correct solution approaches 1.

• Complexity Analysis:

  • The authors prove that BNQP = P$\sharp$P. This equivalence is established by mapping the NQC model to the previously proposed Lorentz Quantum Computer (LQC), showing that both possess the capability for "exponential amplitude amplification" in a state-dependent manner.

• Physical Implementation Schemes:
  The paper investigates two physical schemes to realize the non-unitary gate $G$:

  1. Many-Boson System (Gain/Loss Mechanism): Using a double-well cold atom system (e.g., Rb atoms) where particle numbers are not fixed.
     • Mechanism: Gain is achieved by injecting ions/atoms into one well; loss is achieved by optical excitation and escape from the other well.
     • Realization: The non-unitary evolution is generated via a non-Hermitian Hamiltonian derived from the Gross-Pitaevskii equation, utilizing a purely imaginary geometric (Berry) phase accumulated through adiabatic loops in parameter space.
  2. Postselection: Using an auxiliary qubit and a unitary operation followed by measurement.
     • Mechanism: If the auxiliary qubit is measured in a specific state, the target qubit undergoes an effective non-unitary transformation.

3. Key Contributions

• Definition of BNQP: The formal definition of the complexity class for non-Hermitian quantum computing and the proof that it equals P$\sharp$P, placing it significantly above NP and BQP.
• Explicit Algorithm: A concrete polynomial-time algorithm for the NP-hard Maximum Independent Set problem using non-unitary gates.
• Physical Realization Proposal: A detailed proposal for implementing the non-unitary gate $G$ using cold atom systems with gain and loss, grounded in non-Hermitian physics (PT-symmetry and exceptional points).
• Resource Cost Analysis: A rigorous demonstration that the computational power of NQC is not "free." The paper proves that the exponential speedup comes at the cost of exponentially large physical resources.

4. Key Results

• Computational Power: The NQC model can solve all problems in P$\sharp$P (including NP-complete problems) in polynomial time.
• Physical Constraints:
  • Exponential Particle Requirement: In the many-boson scheme, to distinguish between states with exponentially small amplitudes, the system requires a number of particles ($N$) that scales exponentially with the input size ($N \gg 2^n$).
  • Exponential Postselection Failure: In the postselection scheme, the probability of success decays exponentially with the input size ($P \sim d^{-n}$), requiring an exponentially large number of parallel computers to ensure at least one success.
  • Decoherence: Multi-particle systems suffer from decoherence times that scale inversely with the number of particles ($T_2' = T_2/N$). Since $N$ is exponential, the decoherence time becomes vanishingly small, making the algorithm physically unfeasible.
• Conclusion on Feasibility: While the model is theoretically powerful, it is physically unrealizable in practice because the required resources (particle number or parallel trials) grow exponentially, effectively negating the time complexity advantage.

5. Significance

• Bridging Physics and Computation: The paper provides a profound insight into the relationship between physical laws and computational complexity. It suggests that the limitation of quantum computers to BQP is not just a mathematical artifact but a consequence of physical resource constraints.
• No Free Lunch: It reinforces the principle that to achieve computational power beyond standard quantum mechanics (i.e., solving NP-complete problems efficiently), one must pay an exponential price in physical resources (energy, particles, or time).
• Clarification of Non-Hermitian Physics: The work distinguishes between non-Hermitian systems as effective theories (open systems) versus fundamental theories. It shows that while effective non-Hermitian dynamics can simulate powerful computation, the physical implementation of the necessary gain/loss mechanisms hits a "wall" of resource requirements.
• Comparison to Other Models: Unlike models relying on closed timelike curves (which are hypothetical), this model uses real physical systems (cold atoms, optics) but demonstrates that even "real" physics imposes strict limits on computational supremacy.

In summary, the paper argues that while non-Hermitian quantum mechanics theoretically allows for solving hard problems in polynomial time, the exponential physical resource cost required to implement the necessary non-unitary gates renders such computers practically impossible, thereby preserving the boundary of what is efficiently computable in our physical universe.