⚛️ quantum physics

EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization

The paper proposes EQE-QAOA, an equivalence-preserving framework that significantly reduces qubit requirements for large-scale combinatorial optimization by mapping QAOA dynamics to a smaller invariant subspace via isometric encoding, thereby achieving exact performance without information loss.

Original authors: Xiaoyu Ma, Fang Fang, Ximing Xie, Xianbin Wang, Lajos Hanzo

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiaoyu Ma, Fang Fang, Ximing Xie, Xianbin Wang, Lajos Hanzo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Quantum Backpack" is Too Heavy

Imagine you are trying to solve a massive, incredibly difficult puzzle (like finding the best route for a delivery truck or splitting a group of people into two teams to maximize arguments). In the world of quantum computing, this is called Combinatorial Optimization.

To solve this, scientists use an algorithm called QAOA. Think of QAOA as a very smart, super-fast explorer trying to find the best path through a giant, dark forest.

The Bottleneck:
To explore this forest, the explorer needs a "backpack" (qubits). The bigger the forest (the more complex the problem), the bigger the backpack needs to be.

The Reality: Current quantum computers are like hikers with tiny, broken backpacks. They can only carry a few items (about 10–20 qubits).
The Consequence: If you try to solve a big problem, the backpack is too small. You have to throw things away (simplify the problem) to fit it in. But when you throw things away, you lose information, and your solution becomes worse. It's like trying to navigate a city using a map that only shows the main roads but misses all the shortcuts; you might get there, but it will take longer and be less efficient.

The Solution: EQE-QAOA (The "Magic Map" Trick)

The authors of this paper, Xiaoyu Ma and his team, came up with a brilliant trick called EQE-QAOA.

Instead of throwing things away to make the backpack smaller, they realized that you don't need the whole backpack in the first place.

Here is how it works, using a few analogies:

1. The "Symmetry" Secret (The Invariant Subspace)

Imagine you are in a giant, 100-room mansion (the full quantum world). You are looking for a specific hidden treasure.

Old Way: You have to check every single room, even the ones that are clearly empty or locked. This takes forever and requires a huge map.
The Discovery: The authors realized that because of the rules of the game (the math behind the problem), the treasure cannot be in certain rooms. The rules create "invisible walls" that keep the explorer in a specific, smaller hallway.
The Analogy: It's like realizing that in a game of chess, a pawn can never move to the back row immediately. You don't need to calculate the probability of a pawn being in the back row; it's mathematically impossible.
The Result: The "Quantum Explorer" doesn't need to check the whole mansion. It only needs to check the specific hallway where the treasure actually is. This hallway is called the Invariant Subspace.

2. The "Shrink Ray" (Isometric Mapping)

Once they know the explorer only needs to be in that one specific hallway, they use a "Shrink Ray" (mathematically called an Isometric Mapping).

They take the complex, 100-room mansion and compress it down into a tiny, 3-room apartment that contains exactly the same information as the hallway.
Crucial Point: This isn't like squashing a photo and losing the pixels (which is what other methods do). It's like translating a book from English to French. The language changes (fewer qubits), but the story, the plot, and the ending remain 100% identical.

3. The Result: Same Performance, Smaller Backpack

By using this new framework:

Before: You needed a backpack with 12 items to solve a puzzle.
After: You only need a backpack with 3 or 4 items.
The Magic: The solution you get is exactly the same as if you had used the giant backpack. You didn't lose any accuracy. You just stopped carrying the empty space.

Why Does This Matter?

The paper tested this on a classic puzzle called Max-Cut (splitting a network of connections).

Symmetric Problems: If the problem has a lot of patterns (like a perfect circle of friends), the "hallway" is very small. The authors showed they could shrink a 12-item backpack down to just 3 or 4 items. That's a 70% reduction!
Random Problems: If the problem is chaotic and has no patterns (like a random mess of connections), the hallway is almost as big as the whole mansion. In this case, the trick doesn't help much. But, most real-world engineering problems (like traffic lights, power grids, or scheduling) do have patterns and rules, so this trick works for them.

The Bottom Line

Think of EQE-QAOA as a master chef who realizes they don't need a 100-ingredient recipe to make a great soup. They realize that 90 of those ingredients are just water and salt that cancel each other out. By removing the unnecessary bulk, they can cook the exact same delicious soup in a tiny pot, using less fuel and less time.

In short:

Current Tech: We are limited by how many "quantum bits" (qubits) we have.
Old Fixes: We tried to squeeze the problem in, but it broke the solution.
EQE-QAOA: We found a way to mathematically prove that the problem only lives in a tiny corner of the universe. We shrink the universe down to fit that corner, keeping the solution perfect.

This allows us to solve much bigger, more important problems on today's small, noisy quantum computers without losing any quality.

1. Problem Statement

The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid quantum-classical algorithm for solving combinatorial optimization problems. However, its practical application in the Noisy Intermediate-Scale Quantum (NISQ) era is severely bottlenecked by the scarcity of high-quality qubits.

Current Limitations: Standard QAOA implementations typically use a variable-level encoding where the number of qubits scales linearly with the problem size ( $n$ ). Simulating or running these algorithms requires $n$ qubits, but current hardware can only reliably support $\sim10\text{--}20$ qubits due to noise and coherence limits.
Flaws in Existing Solutions: Previous attempts to reduce qubit counts (e.g., compact encoding, problem partitioning, circuit compression) suffer from significant drawbacks:
- Information Loss: They often rely on heuristic approximations or lossy compression, degrading optimization accuracy.
- Noise: Techniques like mid-circuit measurements introduce additional noise.
- Lack of Equivalence: They do not guarantee mathematical equivalence to the original full-scale system dynamics.

2. Methodology: The EQE-QAOA Framework

The authors propose EQE-QAOA (Equivalence-preserving Qubit Efficient QAOA), a framework that reduces qubit requirements without sacrificing optimization performance or mathematical equivalence. The core methodology relies on exploiting the intrinsic symmetries and conserved quantities of the quantum system.

A. Invariant Subspace Decomposition

The authors utilize Dynamical Lie Algebra theory to analyze QAOA dynamics:

Lie Algebra Generation: They define the dynamical Lie algebra $\mathfrak{g} = \text{Lie}(iH_C, iH_M)$ generated by the Cost Hamiltonian ( $H_C$ ) and Mixer Hamiltonian ( $H_M$ ).
Commutant Identification: They identify the commutant $\mathfrak{g}'$ , which consists of operators $Q$ that commute with both $H_C$ and $H_M$ ( $[Q, H_C] = 0, [Q, H_M] = 0$ ). These operators represent conserved quantities (symmetries) of the system.
Subspace Confinement: The existence of non-trivial conserved quantities implies that the Hilbert space decomposes into invariant subspaces. If the initial state $|\psi_0\rangle$ lies within a specific subspace $\mathcal{H}_{\text{eff}}$ , the QAOA evolution remains strictly confined to this subspace for all layers and parameters.

B. Isometric Mapping to Reduced Space

Once the effective invariant subspace $\mathcal{H}_{\text{eff}}$ is identified:

Dimension Reduction: If the dimension of $\mathcal{H}_{\text{eff}}$ is $M$ , it can be represented by $m = \lceil \log_2 M \rceil$ qubits, where $m < n$ .
Isometric Embedding: The authors construct an isometric mapping $V: \tilde{\mathcal{H}}_{\text{eff}} \to \mathcal{H}_{\text{eff}}$ . This maps the reduced $m$ -qubit space back to the effective subspace of the original $n$ -qubit space.
Induced Hamiltonians: The original Hamiltonians are projected onto the reduced space to create induced Hamiltonians ( $\tilde{H}_C, \tilde{H}_M$ ).
Execution: The QAOA circuit is executed entirely on the reduced $m$ -qubit system using these induced Hamiltonians. The final state is mapped back via $V$ to recover the solution in the original space.

3. Key Contributions

Theoretical Proof of Equivalence: The paper rigorously proves (via Theorem 1 and 2) that the evolution within the reduced invariant subspace is exactly equivalent to the full-scale QAOA evolution. This guarantees that the reduced system produces identical state trajectories, expectation values, and measurement statistics as the original system.
Qubit Reduction via Symmetry: The framework provides a systematic method to reduce qubits from $n$ to $m$ by exploiting problem symmetries (e.g., permutation symmetry) and constraints (e.g., fixed Hamming weight), rather than using heuristic approximations.
Applicability Conditions: The authors derive formal conditions for reducibility. EQE-QAOA is applicable to any problem where the commutant of the Hamiltonians is non-trivial (i.e., problems with constraints or symmetries). It is not applicable only to unconstrained problems with completely independent variables.
Complexity Reduction: By reducing the state space dimension from $2^n$ to $M$ (where $M \ll 2^n$ ), the computational complexity of classical simulation drops from $O(2^n)$ to $O(M)$ , and the qubit requirement drops from $n$ to $\lceil \log_2 M \rceil$ .

4. Results

The authors validated EQE-QAOA using numerical simulations on Max-Cut problems across various graph families:

Qubit Reduction:
- Complete Graphs ( $K_n$ ): Exhibited the strongest reduction. Due to high permutation symmetry, the qubit count remained nearly constant (e.g., $\sim4$ qubits) even as $n$ increased to 12, achieving up to 70% reduction.
- Cycle Graphs: Showed moderate reduction due to partial symmetry.
- Random Graphs: Showed minimal reduction, as they lack structural symmetry, confirming the method's dependence on problem structure.
Equivalence Validation:
- State Fidelity: The difference between the full-space and reduced-space states was zero (within machine precision, $10^{-15}$ ).
- Observable Difference: The error in the Max-Cut expectation value ( $|\Delta E|$ ) and Total Variation Distance (TVD) of measurement distributions were negligible ( $10^{-14} \sim 10^{-15}$ ).
Memory Efficiency: Classical simulation memory usage for EQE-QAOA grew logarithmically with problem size for symmetric graphs, whereas standard QAOA grew exponentially.
Benchmarking: Compared against minimal encoding, problem partitioning (DC-QAOA), and qubit-reuse strategies, EQE-QAOA achieved the highest approximation ratios and lowest accuracy gaps, proving that it preserves optimization quality while reducing resources.

5. Significance

Overcoming the Qubit Bottleneck: EQE-QAOA offers a path to solve larger combinatorial optimization problems on near-term quantum devices by drastically lowering the qubit count without requiring error correction or massive hardware upgrades.
Lossless Optimization: Unlike previous "lossy" compression techniques, this framework guarantees mathematical equivalence, ensuring that the solution quality is not compromised by the reduction process.
Broad Applicability: Since most real-world engineering problems (resource allocation, scheduling, network routing) involve constraints and symmetries, EQE-QAOA is broadly applicable to practical scenarios.
Simulation Scalability: The method significantly accelerates classical simulations of QAOA, enabling researchers to test larger problem instances that were previously intractable due to exponential memory requirements.

In summary, EQE-QAOA transforms the qubit reduction problem from a heuristic trade-off into a rigorous, symmetry-based mathematical reduction, enabling high-fidelity quantum optimization on resource-constrained hardware.