Beyond QAOA: Entanglement as an Optimization Resource

The Honest Pursuit of Quantum Advantage

Let's be direct about something most quantum computing papers avoid: classical solvers are still better at practical optimization problems. Our job isn't to pretend otherwise — it's to understand exactly where and why quantum approaches gain traction, and to push that frontier forward.

QAOA (Quantum Approximate Optimization Algorithm) is the standard quantum approach for combinatorial optimization. But on NISQ devices, QAOA hits a wall: shallow circuits underperform, and deep circuits drown in noise. We developed Entanglement-Driven Optimization (EDO) as an alternative — using structured entanglement patterns as a direct optimization resource rather than a byproduct of generic parameterized circuits.

The Entanglement Hypothesis

Classical optimization navigates the search landscape through local gradient updates. Each parameter changes independently. Quantum entanglement breaks this locality: modifying one qubit's state simultaneously affects all entangled partners. Our hypothesis: carefully structured entanglement can encode problem structure, enabling correlated multi-dimensional search steps.

We tested this on three NP-hard problems:

Max-Cut Results (Graph Partitioning)

• On 12-node random graphs across 100 instances:
• EDO: 94.2% approximation ratio
• QAOA p=3: 87.6% approximation ratio
• Improvement: +6.6 percentage points

EDO uses problem-aware entanglement — qubits representing strongly interacting variables get entangled first, with hierarchical layers (local, regional, global). This lets the circuit "understand" the graph structure rather than exploring blindly.

Traveling Salesman Results (Logistics)

• On 8-city instances across 50 random configurations:
• EDO: Found optimal route in 72% of cases
• QAOA p=5: Found optimal in 41% of cases
• Classical simulated annealing: Found optimal in 89% (10,000 iterations)

Note the honesty here: classical SA still wins at this problem size. But EDO's 72% versus QAOA's 41% shows that structured entanglement provides a real advantage within the quantum regime.

Portfolio Optimization Results (Finance)

• Using 10 real GEL-denominated assets in a Markowitz framework:
• Sharpe ratio: EDO 1.42, QAOA 1.18, classical mean-variance 1.51
• Constraint satisfaction: EDO 100%, QAOA 84% (violated weight constraints)

EDO satisfies all constraints perfectly while QAOA violates them in 16% of runs. For financial applications where constraint violation means regulatory problems, this reliability matters more than the slight Sharpe ratio gap versus classical methods.

The Entanglement Entropy Connection

Our most theoretically interesting finding: there's a strong correlation (r = 0.87) between entanglement entropy and solution quality. Circuits that develop higher entanglement during optimization consistently find better solutions.

Solutions in the top 10% quality bracket had average entanglement entropy of 2.8 bits. Bottom 50% solutions averaged 1.4 bits. This suggests entanglement isn't just a quantum "feature" — it's a direct computational resource for optimization. The more entangled the circuit becomes, the better it searches.

Practical Applications for Georgia

This research has immediate relevance to Georgia's growing tech ecosystem:

• Supply chain routing: Optimizing delivery routes for e-commerce networks (TBC Bank's merchant network has 15,000+ retailers across Georgia's challenging terrain)
• Portfolio allocation: GEL-denominated asset optimization for Georgian pension funds and investment managers
• Network design: Optimizing fiber optic and 5G tower placement across Georgia's mountainous geography

"We don't claim quantum supremacy. We claim quantum progress — measured honestly, with classical baselines."

The Path Forward

EDO outperforms QAOA consistently but doesn't yet compete with state-of-the-art classical solvers at practical sizes. The crossover point appears at 20+ qubits in simulation, where exhaustive classical search becomes expensive. On current NISQ hardware (12 reliable qubits on Wukong), classical remains faster and more reliable.

Practical quantum advantage requires three things we don't yet have: 1. Hardware with 50+ reliable qubits and two-qubit gate fidelity above 99.5% 2. Problem instances large enough that classical heuristics struggle (100+ variables) 3. Error rates low enough that optimization gradients aren't noise-dominated

We're building toward all three. The error mitigation stack from Chapter 2 addresses point 3. The tensor compression work in Chapter 4 addresses computational efficiency. And hardware is improving year over year. The question isn't if quantum optimization will matter — it's when.