Quantum circuit evolutionary framework applied on set partitioning problem

This paper proposes a quantum circuit evolutionary framework utilizing variable topology and a pseudo-counterdiabatic evolutionary term to effectively solve set partitioning problems by overcoming convergence stagnation and eliminating the need for classical optimizers.

The Gist

Imagine you are trying to solve a massive, complex puzzle. The goal is to divide a group of people (like airline crews) into teams so that every flight is covered exactly once, without any overlaps or missing shifts, while keeping costs as low as possible. In the world of math, this is called the Set Partitioning Problem. It's a notoriously difficult challenge that gets exponentially harder as you add more people and flights.

This paper introduces a new way for quantum computers to tackle this puzzle. Instead of using the standard "recipe" that most quantum algorithms follow, the authors built a framework that lets the computer evolve its own recipe as it works.

Here is a breakdown of their approach using simple analogies:

1. The Old Way: The "Fixed Blueprint" (VQE)

Most current quantum algorithms, like the Variational Quantum Eigensolver (VQE), work like a chef following a strict, unchangeable recipe book.

• The Setup: The structure of the "circuit" (the steps the computer takes) is fixed. You can't add or remove ingredients; you can only tweak the amounts (the parameters).
• The Problem: As the puzzle gets bigger, the chef often gets stuck in a "flat valley." Imagine walking in a foggy field where the ground is perfectly flat. No matter which way you step, you don't go up or down. You can't tell if you are getting closer to the solution or not. In quantum physics, this is called a Barren Plateau. The computer stops learning because it can't find a direction to improve.

2. The New Way: The "Evolving Sculptor" (QCE)

The authors propose a framework called Quantum Circuit Evolution (QCE). Instead of a fixed recipe, imagine a sculptor who starts with a tiny lump of clay and is allowed to add, remove, or reshape the clay at every step.

• How it works: The computer starts with a very simple circuit (maybe just one gate). It then creates a "family" of slightly different versions of itself by randomly mutating the structure (adding a new step, deleting an old one, or changing a connection).
• The Selection: It tests all these versions. The one that solves the puzzle best survives to be the "parent" for the next round. The others are discarded.
• The Benefit: Because the structure itself is changing, the computer isn't stuck in a flat valley. It can reshape its entire approach to find a path out of the fog.

3. The Two Strategies Tested

The paper tested two specific flavors of this "Evolving Sculptor" approach:

• Strategy A: The Pure Evolutionist (Ansatz-Free)
  This version starts with almost nothing and lets the computer figure out the structure entirely through trial and error, much like natural selection. It doesn't guess what the solution should look like; it just evolves until it works.

• Strategy B: The Physics-Inspired Evolutionist (Pseudo-Counterdiabatic)
  This is the "star" of the paper. The authors gave the computer a hint based on the physics of the problem. They added a special "nudge" (called a pseudo-counterdiabatic term) to the circuit.

  • The Analogy: Imagine you are trying to push a heavy box up a hill. The "Pure Evolutionist" just pushes randomly until it finds a way up. The "Physics-Inspired" version knows the shape of the hill and adds a specific counter-force to keep the box moving smoothly, preventing it from getting stuck in the flat spots.
  • The Result: This strategy performed the best. It avoided the "stuck" feeling (convergence stagnation) much better than the other methods, even when the puzzle was very large.

4. The Results

The authors tested these methods on a simulator (a computer program that acts like a quantum computer) using 35 different versions of the airline scheduling puzzle.

• The Winner: The Physics-Inspired Evolution method (APCD-QCE) consistently found better solutions than the standard "Fixed Blueprint" method (VQE).
• The Sticking Point: While the new methods were much better, they still struggled when the puzzle became extremely large (around 20 qubits). Even the evolving sculptor sometimes ran out of time or complexity to find the perfect solution.
• Noise: They also tested what happens when the computer makes mistakes (simulating real-world "noise"). The new methods held up reasonably well, though performance did drop, which is expected.

The Bottom Line

The paper claims that by letting a quantum circuit change its own shape rather than just tweaking its settings, we can avoid the "dead ends" that trap current algorithms. Specifically, adding a physics-based "nudge" to this evolving process helps the computer find better solutions faster.

While this doesn't solve every problem yet (especially the very biggest ones), it offers a promising new path for using quantum computers to solve complex optimization problems like scheduling and resource management, potentially bypassing the need for classical computers to do the heavy lifting of optimization.

Technical Summary

Technical Summary: Quantum Circuit Evolutionary Framework Applied to the Set Partitioning Problem

Problem Definition
The paper addresses the Set Partitioning Problem (SPP), a well-known NP-hard combinatorial optimization challenge. The SPP involves dividing a set of elements into mutually exclusive and exhaustive subsets to minimize total weight while ensuring every element belongs to exactly one subset. Practical applications include airline crew scheduling. To solve this on quantum hardware, the authors formulate the SPP as a Quadratic Unconstrained Binary Optimization (QUBO) problem, which is subsequently mapped to an Ising Hamiltonian. The study specifically targets the limitations of current Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE), which often suffer from "barren plateaus"—a phenomenon where gradients vanish exponentially as qubit counts increase, leading to convergence stagnation.

Methodology
The authors propose a Quantum Circuit Evolutionary (QCE) framework that departs from the standard VQE approach. Unlike VQE, which utilizes a fixed circuit topology (ansatz) with varying parameters optimized by a classical optimizer, the QCE framework evolves the circuit topology itself. The study evaluates two distinct strategies within this framework:

1. Ansatz-Free Quantum Circuit Evolution (AF-QCE):

   • Inspired by previous literature [13], this approach begins with a minimal circuit (a single random gate) and evolves iteratively without a pre-defined ansatz.
   • The evolution relies on mutation operations: INSERT (add a gate), DELETE (remove a gate), SWAP (replace a gate), and MODIFY (adjust gate parameters).
   • A population of circuits is generated, measured, and the best-performing circuit is selected as the parent for the next generation, ensuring monotonic cost function reduction.

2. Ansatz with Pseudo-Counterdiabatic Evolutionary Term (APCD-QCE):

   • This approach incorporates physics-inspired structure into the ansatz to improve convergence. It utilizes a Hamiltonian $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$, where $H_{ad}$ represents an adiabatic time-evolution Hamiltonian and $H_{pcd}$ is a pseudo-counterdiabatic evolutionary term.
   • The unitary operator is defined as $U = U_{ad}U_{pcd}$. The $U_{ad}$ component is fixed (one Trotter step), while $U_{pcd}$ is evolved using the same evolutionary mutation strategy as AF-QCE.
   • The initial state preparation uses $|+\rangle^{\otimes n}$, and specific parameter settings ($\beta=0, \delta=0.5$) are applied to facilitate exploration of the Hilbert space.

Experimental Setup
Experiments were conducted using the Qiskit library on a high-performance simulator (KUATOMU) under two scenarios:

• Noise-Free: 35 instances of the SPP (ranging from 6 to 20 qubits) were tested.
• Noisy: Simulations included depolarizing error channels ($\epsilon = 0.01$) on specific qubits to mimic NISQ device limitations.
• Comparison: The QCE strategies were benchmarked against the standard VQE (using a two-local linear entanglement ansatz and the COBYLA optimizer).
• Metric: Performance was measured using the Approximation Ratio ($R$), defined as the ratio of a classical reference value (Gurobi solver) to the minimum expectation value found by the quantum algorithm.

Key Results

• Superiority over VQE: In noise-free scenarios, both AF-QCE and APCD-QCE significantly outperformed VQE. VQE performance degraded rapidly as qubit counts increased (often failing to converge for instances $\ge 10$ qubits), whereas the evolutionary approaches maintained better performance.
• APCD-QCE Performance: The APCD-QCE strategy demonstrated the most robust results, achieving an approximation ratio of 1.00 (optimal) in 25 out of 35 instances. It effectively avoided convergence stagnation in most cases where VQE and AF-QCE struggled.
• Scalability Limits: Despite the improvements, scalability challenges persisted. For 20-qubit instances (specifically 20.1, 20.6, and 20.7), all methods, including APCD-QCE, showed signs of convergence stagnation, with approximation ratios dropping significantly.
• Noise Impact: In noisy simulations, performance degraded for all algorithms, particularly in smaller instances. However, the QCE frameworks generally maintained comparable or better performance relative to VQE.

Significance and Claims
The paper claims that the proposed QCE framework offers a promising alternative to fixed-ansatz variational algorithms for integer optimization problems. Key contributions include:

• Mitigation of Stagnation: The framework, particularly the APCD-QCE variant, demonstrates a remarkable ability to avoid the convergence stagnation associated with barren plateaus in standard VQAs.
• Elimination of Classical Optimizers: By evolving the circuit topology directly, the procedure circumvents the need for classical optimizers (like COBYLA) to tune parameters, addressing a bottleneck in current VQA workflows.
• Path to Scalability: While not a complete solution to the 20-qubit stagnation, the results suggest that variable-topology circuits provide an "interesting path" for solving larger-scale optimization problems. The authors note that the APCD-QCE strategy is "almost immune" to convergence stagnation effects given a sufficiently large number of generations, though escaping local minima in the mutation landscape remains a challenge.

The authors conclude that while the method faces scalability hurdles with increasing qubit counts, the integration of physics-inspired terms (pseudo-counterdiabatic) into evolutionary circuit search yields encouraging results for solving combinatorial problems on NISQ devices.