An autocatalytic cycle is a set of chemical reactions that, run together, produces more of one of its own ingredients than it consumes. Such cycles are the leading candidates for how self-sustaining metabolism first appeared. Deciding whether a reaction network contains one is NP-complete. Exact search today means solving one large integer program over the whole network. This proposal asks whether that search can be split into many small, independent subproblems. Each subproblem would be confined to a "window" of a few reactions and could be encoded in about 20–30 binary variables, which is small enough for today's noisy quantum processors with tens of qubits. A classical coordinating program would then combine the answers.
The quantum angle is real, but it is not the main contribution. The main contribution is a measurable structural question: in realistic prebiotic networks, how many reactions does the smallest self-contained certificate of autocatalysis need? If that number is small, near-term quantum solvers have a natural, decomposable job in chemistry, and so do classical solvers. If it is large, quantum cycle search for chemistry is ruled out for the foreseeable future. That negative answer is also worth knowing before anyone builds such a pipeline.
Core Claim
Autocatalysis is hard in the worst case. The NP-completeness proof in Maximizing output and recognizing autocatalysis in chemical reaction networks is NP-complete builds networks from "switch" gadgets that encode 3-partition. Those gadgets couple the whole network globally. Real networks generated by chemical rules may not look like that. We claim that in rule-generated prebiotic networks (formose, the reverse citric-acid cycle supernetwork, HCN chemistry), most minimal autocatalytic cores fit inside a bounded window.
A window is a small, connected subset of reactions in the reaction hypergraph, where each reaction is a "hyperedge" joining a set of reactant molecules to a set of product molecules. If the claim holds, a Dantzig-Wolfe column-generation scheme can recover nearly all cores using only window-sized pricing problems. Column generation keeps a classical "master" program and repeatedly asks a small "pricing" subproblem for a new useful solution. Each pricing problem has a fixed qubit budget $K$ that does not grow with network size.
The decisive quantities are two. The first is the recall of cores as a function of $K$, measured against exact enumeration. The second is how much that recall degrades when the pricing solver is noisy.
Relation to Prior Work
The formulation comes from Andersen and colleagues. Chemical Transformation Motifs - Modelling Pathways as Integer Hyperflows casts pathway and autocatalysis search as an integer linear program over integer hyperflows, meaning integer reaction counts that conserve molecules exactly. They solve it monolithically with commercial solvers. We keep their constraints but restrict them to windows inside a decomposition.
On the Realisability of Chemical Pathways shows that a balanced flow may still be impossible to fire in any valid order. It checks firing order through Petri-net reachability and identifies "borrowed" seed molecules. We use it as a downstream filter, with its acyclic-bipartite-graph sufficient condition as a cheap first pass. We do not try to solve reachability quantumly.
Two earlier studies enumerated cycles with plain directed-graph search: Context-Driven Exploration of Complex Chemical Reaction Networks, which found 10 autocatalytic cycles in C4 formose, and Uncertainty of Prebiotic Scenarios, which found 1,881 candidate cycles in a 175-molecule, 444-reaction network. These counts motivate the project, since they show the solution space is large and degenerate. They also serve as a naive baseline, because graph traversal ignores stoichiometry.
The decomposition method comes from the quantum-optimization literature. Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness shows that Dantzig-Wolfe keeps the quantum pricing problem at a constant 13–17 qubits, whereas Benders decomposition grows from 40 to over 100 qubits within 10 iterations. It also argues that noisy pricing only produces suboptimal columns and never makes the master problem infeasible. Hybrid Quantum-Classical Heuristic to Solve Large-Scale Integer Linear Programs embeds the quantum approximate optimization algorithm (QAOA) in branch-and-price. It warns that penalty weighting and solution degeneracy strongly affect the circuit depth required. This warning constrains our encoding, because autocatalytic manifolds are highly degenerate.
Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems and Decomposition Pipeline for Large-Scale Portfolio Optimization supply the classical partitioners we compare against, namely correlation-based node merging and modularity clustering. Neither has been applied to directed reaction hypergraphs.
On the graph-learning side, DLGNet turns reactions into nodes of a directed line graph. It uses a Hermitian Laplacian, a complex-valued matrix whose imaginary part records reaction direction, to classify single reactions. We test whether the same representation can rank windows. We treat this as a hypothesis that may fail, not as a component the method depends on.
Research Program
The pricing problem is the core object. Given dual prices $\pi$ from the master program, the pricing step searches a window $W$ of reactions for an integer flow $x_r \in \{0,\dots,m\}$ on each reaction $r \in W$. The flow must satisfy three conditions. It must conserve molecules at internal species, so that $Sx = 0$ there, where $S$ is the stoichiometric matrix. It must produce a strictly positive net amount of some designated species $a$ that it also consumes. Among such flows, it should minimize the reduced cost $c^\top x - \pi^\top A x$, where $c$ is the column cost (for example, total reactions used) and $A$ maps the flow onto the master's constraints.
The binary encoding uses $\lceil \log_2(m+1) \rceil$ bits per reaction. Conservation equalities become quadratic penalties with no slack variables. The single autocatalysis inequality needs a few slack bits. With $m = 3$ and windows of 8–12 reactions, the encoding lands in the 20–30 qubit range. Penalty weights are set following the degeneracy analysis of Svensson et al.
The master program serves two tasks. The first is enumeration: repeated pricing collects minimal autocatalytic cores, and no-good cuts in the master exclude cores already found. The second is output maximization, with autocatalytic cores and linear pathways as columns, following the objective of Andersen et al.
Windows are proposed by four methods with a matched number of proposals. The first is random connected subgraphs. The second expands outward from reactions with high dual value. The third is modularity clustering on the line graph, as in Acharya et al. The fourth is a DLGNet-style scorer trained on cores found in other networks.
Every recovered core is passed to LoLA for Petri-net reachability. Cores that require a borrowed seed are reported separately.
The structural study needs no quantum hardware at all. For each network we compute every minimal core exactly, then record the smallest window radius that contains it. The resulting window-size distribution is the paper's main scientific finding.
Baselines
The strongest competitor is exact enumeration with the monolithic integer program of Chemical Transformation Motifs, solved by a commercial branch-and-bound solver on the full network. It defines ground truth and is the method a chemist would actually use. It runs on the same machine as our classical master, with the same time limit per network and default solver tuning. For enumeration, Andersen et al. report only qualitative results ("a complex and dense network of autocatalytic cycles"). I found no reported runtime or cycle count on Lacuna for their solver on formose, so we establish the number ourselves.
We do not expect to beat this method in speed on networks of a few hundred reactions. Beating it means one of two things. Either we match its recall at a pricing size that stays fixed as the network grows, or we retain high recall on the largest generated networks where the monolithic solve hits its time limit.
The naive references are of two kinds. The first is stoichiometry-blind directed-graph cycle search in the style of Zubarev et al., who report 1,881 candidate cycles for reverse-TCA. Our pipeline should show that a quantifiable fraction of these candidates fail to balance or fail to fire. The second is a monolithic quadratic binary encoding of the whole network, which serves as the "send everything to the quantum chip" reference. Its qubit count should explode, consistent with the over-120-qubit instances in Sharma and Lau, who reach optimality gaps as low as 0.21% only after shrinking.
Two ablations isolate the key ingredient. The first sweeps the window budget $K$ and plots recall as a function of $K$. The second swaps the pricing solver among four options: exact brute force within the window, simulated annealing, noiseless QAOA, and noise-modeled QAOA. All four receive the same windows and dual prices, so that recall loss can be attributed to the solver alone.
Why not just…?
Why not just run the integer program on the whole network? At the sizes in hand (hundreds of reactions), this will probably win on wall-clock time, and we say so up front. The proposal does not claim a speedup. It measures whether autocatalytic search decomposes into bounded windows, which is the precondition for any NISQ role. The same decomposition is also a classical scaling route for the far larger networks generated by graph grammars. The $K$-sweep and the comparison on large networks settle this question.
Why not just solve the window pricing problems classically? For 25 binary variables, brute force is trivial. Classical exact pricing is therefore our reference solver, not a straw man. The quantum question is narrower. Franco et al. argue that column generation tolerates noisy pricing; does that hold when the pricing landscape is as degenerate as autocatalytic manifolds are? We answer it by comparing recall under exact pricing with recall under noise-modeled QAOA. If the gap is large even with mitigation, the honest conclusion is that this application does not suit NISQ devices.
Why not just use modularity or dual-guided windows instead of a learned scorer? This is a real threat. Modularity clustering worked well for portfolios in Acharya et al., and dual-guided expansion uses information the scorer lacks. DLGNet's strong result (99.75% F1 against 68.10% on the substitution-versus-elimination benchmark) concerns classifying single reactions, not ranking subnetworks. If the classical proposers match the scorer's recall at equal proposal budgets, we drop the learned component and report that result.
Why not just use directed-graph cycle search, as earlier formose and reverse-TCA studies did? It treats each reaction as a simple edge. It therefore cannot express the requirement that a molecule be produced in excess, and it ignores the firing-order constraints shown by On the Realisability of Chemical Pathways. We measure its false-positive rate directly against balanced, realisable cores.
Proposed Experiments
Networks are generated with the MØD graph-grammar system used in the Andersen papers. We generate C4-restricted formose networks, for which Simm and Reiher report 10 low-barrier autocatalytic cycles from quantum-chemistry exploration; that is a reference count, not directly comparable to our stoichiometric cores. We also reconstruct a reverse-TCA-style supernetwork from seven rule types, with a target of roughly 175 species and 444 reactions. Rebuilding this network is a risk, because the original may not be reproducible. Finally, we build HCN networks expanded over successive generations to produce a size ladder.
The metrics are five: recall of minimal cores against exact enumeration, the window-size distribution of cores, qubits per pricing call, master iterations, and the fraction of recovered cores that LoLA certifies as realisable, with and without a borrowed seed. QAOA runs on noiseless and noise-modeled simulators at 20–30 qubits.
Three outcomes are decisive. The first is whether at least about 90% of exact cores fall within windows of 30 or fewer qubits on every network family, and whether that fraction holds as HCN networks grow. The second is whether recall with noisy QAOA pricing stays within a few points of recall with exact pricing. The third is whether any window proposer clearly beats random windows. A negative result on the first outcome, meaning cores that are inherently global, would close off the quantum route for this problem.
References
- Maximizing output and recognizing autocatalysis in chemical reaction networks is NP-complete
- Chemical Transformation Motifs - Modelling Pathways as Integer Hyperflows
- On the Realisability of Chemical Pathways
- Context-Driven Exploration of Complex Chemical Reaction Networks
- Uncertainty of Prebiotic Scenarios: The Case of the Non-Enzymatic Reverse Tricarboxylic Acid Cycle
- Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness
- Hybrid Quantum-Classical Heuristic to Solve Large-Scale Integer Linear Programs
- Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems
- Decomposition pipeline for large-scale portfolio optimization with applications to near-term quantum computing
- DLGNet: Hyperedge Classification through Directed Line Graphs for Chemical Reactions