Quantum-Enhanced Agentic Reinforcement Learning for Combinatorial Optimization
This repository contains the reproducible implementation used to study Quantum-Enhanced Agentic Reinforcement Learning (QE-ARL) for the Max-Cut combinatorial optimization problem.
What the Code Does
The code generates small weighted-free Erdős–Rényi graphs and treats Max-Cut as a sequential decision problem. Starting from an initial binary partition of the graph vertices, an autonomous reinforcement-learning agent repeatedly selects a search operator that modifies the current solution. The objective is to increase the cut value until a fixed search budget is exhausted.
For every evaluation graph, the exact Max-Cut optimum is also computed by exhaustive enumeration. This allows the quality of every solution to be measured using an exact approximation ratio rather than an estimated reference value.
Compared Optimization Methods
The implementation evaluates four methods under the same graph instances and search budget.
Random Search
Random Search produces candidate partitions without using learned information. It serves as a simple lower-level baseline for measuring whether structured search provides meaningful improvement.
Greedy Local Search
The greedy method evaluates single-vertex flips and selects the move giving the largest immediate improvement in cut value. When the search reaches a local optimum, a random perturbation is used to continue exploration.
Classical Agentic Reinforcement Learning
Classical-ARL uses a lightweight trainable softmax policy. At every search step, graph and search-state features are provided to the policy, which autonomously selects one of several optimization operators. The policy is trained from episode returns so that operators associated with better search trajectories become more likely.
Quantum-Enhanced Agentic Reinforcement Learning
QE-ARL uses the same autonomous search framework as Classical-ARL, but replaces the classical policy controller with a 4-qubit variational quantum circuit (VQC).
The circuit is simulated directly with NumPy using statevector evolution. Classical search-state features are encoded into qubit rotations, trainable parameterized rotations transform the state, and quantum expectation values are converted into logits for operator selection.
The quantum policy therefore does not solve Max-Cut directly. Instead, it acts as the decision-making controller that determines which classical search operator should be applied next.
Agentic Search Operators
At each decision step, the learned controller selects one of four actions:
- Greedy single flip — flips the vertex giving the strongest immediate gain.
- Gain-biased stochastic flip — probabilistically favors vertices with better estimated gains while maintaining exploration.
- Pair flip — changes two vertices together to escape configurations that cannot be improved by a single flip.
- Structured perturbation — intentionally changes the current partition to help the search leave a local optimum and explore another region.
Because the controller chooses among different optimization strategies according to the current search state, the method is described as agentic reinforcement learning rather than a fixed local-search heuristic.
Reinforcement-Learning Logic
An episode corresponds to solving one Max-Cut graph. During an episode, the controller observes the current search state, samples an operator, applies it, and receives a reward based on the resulting change in solution quality.
The training signal is based on discounted episode returns. The policy parameters are updated using a REINFORCE-style objective so that actions contributing to stronger final solutions receive higher probability in similar states.
For QE-ARL, gradients of the VQC-controlled policy are approximated using a simultaneous-perturbation strategy. This keeps the quantum-policy training lightweight while avoiding dependence on an external quantum-computing SDK.
Quantum Circuit
The QE-ARL controller contains four simulated qubits. Its main stages are:
- encode normalized search-state features through parameterized rotations;
- create feature interactions using entangling gates;
- apply trainable variational rotations;
- calculate expectation values from the final statevector;
- map those expectation values to action logits;
- convert the logits to operator-selection probabilities with softmax.
The circuit is a statevector simulation, so the experiment studies the behavior of a hybrid quantum-classical policy architecture rather than claiming physical quantum-hardware speedup.
Graph Benchmark
The benchmark contains Erdős–Rényi Max-Cut instances with:
- graph sizes of 8, 10, and 12 vertices;
- edge probabilities of 0.3, 0.5, and 0.7;
- multiple independently generated test instances for every size-density combination;
- independent training seeds and repeated evaluations.
These graph sizes are deliberately small because the code computes the exact optimum of every instance for reliable evaluation.
Exact Max-Cut Verification
For each graph, the code enumerates possible binary partitions and calculates the true maximum cut value. Complementary partitions represent the same cut, so one vertex can be fixed to remove this symmetry and reduce redundant enumeration.
The exact optimum is used to calculate
Approximation Ratio = Obtained Cut Value / Exact Optimal Cut Value.
A ratio of 1.0 means that the optimizer found an exact optimal solution.
Evaluation Metrics
The code records several metrics for every method and graph instance, including:
- obtained cut value;
- exact optimal cut value;
- approximation ratio;
- whether the exact optimum was reached;
- graph size and density;
- training seed and evaluation repeat;
- runtime information.
The experiment also aggregates these values into method-level summary statistics.
Main Reproduced Result
The current deterministic experiment produces the following aggregate performance:
| Method | Mean Approximation Ratio | Exact-Hit Rate |
|---|
| Random | 0.8933 | 17.28% |
| Greedy | 0.9906 | 84.57% |
| Classical-ARL | 0.9823 | 76.85% |
| QE-ARL | 0.9891 | 84.72% |
QE-ARL improves the mean approximation ratio over the matched Classical-ARL controller by approximately 0.0068. Its performance is close to the strong greedy baseline on these small instances.
The result therefore supports the interpretation that the variational quantum policy can function as a competitive operator-selection controller in this experimental setting. It does not establish quantum computational advantage.
Generated Outputs
The experiment produces three main result tables:
results.csv — instance-level evaluation results for all methods;training_history.csv — reinforcement-learning progress across training episodes;summary.csv — aggregated performance statistics used for reporting and comparison.
The notebook also generates figures that summarize learning behavior, approximation ratios, and comparative optimizer performance.
Reproducibility Design
The implementation uses fixed random seeds for graph generation, policy initialization, training, and evaluation. The same test graphs are shared across the competing methods so that comparisons are paired rather than based on different problem instances.
The quantum component is implemented directly as matrix-based statevector simulation using NumPy. Consequently, the behavior of the reported experiment is controlled by the repository code itself and is not dependent on an external quantum service, hardware queue, account, or changing quantum-SDK backend.
Scope
This implementation is a small-scale proof-of-concept for combining agentic reinforcement learning, variational quantum policies, and combinatorial optimization. Its purpose is to evaluate the hybrid decision architecture under conditions where every optimization result can be checked against an exact solution.
