Warm-Started Quantum Proposals for Multi-Objective Protein Sequence Search

Designing a protein means satisfying several conflicting demands at once: it should be stable, it should fold and express, it should bind its target without sticking to everything else. Optimizing any one of these objectives alone reliably breaks the others — models that maximize binding affinity, for example, place hydrophobic patches at interfaces that cause aggregation, a documented failure mode of single-objective reward maximization (Makowski et al.). The practical target is therefore the Pareto frontier: the set of variants where no objective can be improved without sacrificing another. Classical search for this frontier struggles on real proteins because the sequence-to-fitness mapping is rugged — mutations interact non-additively (epistasis), littering the landscape with local optima that trap greedy and short-step search (Improving protein optimization with smoothed fitness landscapes, Epistatic Net allows the sparse spectral regularization of deep neural networks for inferring fitness functions).

Meanwhile, hybrid quantum-classical optimization has produced one genuinely encouraging result: shallow quantum circuits used as proposal generators inside a classical Markov Chain Monte Carlo (MCMC) loop helped recover global optima on rugged 117-variable combinatorial landscapes on real IBM hardware, with convergence iterations growing at roughly 86% the rate of purely classical chains (Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization). The mechanism — quantum circuits produce correlated, non-local jumps that classical single-site proposals cannot — is exactly what epistatic protein landscapes demand. But that work is strictly single-objective, and the only multi-objective variational quantum algorithm (Variational Quantum Multi-Objective Optimization) has been tested only on synthetic spin models. This proposal brings the two together, with an honest experimental design that treats quantum advantage as a hypothesis to be tested, not assumed.

Core Claim

The claim is specific and falsifiable: a shallow variational quantum circuit, used as the move generator inside a parallel-tempered, multi-objective classical stochastic search over protein sequence space — not as the solution generator — can produce correlated multi-position mutation proposals that escape epistatic local optima on real, learned protein fitness landscapes, provided the circuit is warm-started from protein language model marginals. This differs from the closest existing work in three ways. First, Variational Quantum Multi-Objective Optimization (QMOO) reads the candidate population directly off the measured quantum state and was validated only on synthetic linear and spin-model benchmarks; here the quantum state only proposes moves, which makes the method tolerant to shot noise and hardware error — a critical practical property, since QMOO itself needed only $L=1$ depth and 128 shots per iteration to match classical evolutionary algorithms on those toys, and we inherit that frugality. Second, the objective Hamiltonians are not synthetic spin glasses but learned epistatic coupling matrices fit to large real datasets, mapping pairwise mutation interactions onto two-body Ising terms — a natural algebraic correspondence that, to our knowledge, no quantum protein work has exploited (Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing and Investigating the potential for a limited quantum speedup on protein lattice problems encode only spatial lattice folding, not epistasis). Third, initialization is warm-started from foundation-model sequence distributions, because both quantum studies in the file show performance is dominated by initialization quality: the MCMC work calls warm-starting critical for scaling (Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization), and the VQE benchmarking study found performance strongly correlated with the initial point (Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice).

The Hybrid Split: Encoding and Objectives

The 20-letter amino acid alphabet is a known qubit-mapping obstacle. Rather than fight it, we partition the problem along a line that suits both sides. The quantum processor owns a small contiguous design patch of 4–8 positions, each encoded one-hot over a reduced 4–5 letter alphabet obtained by physicochemical grouping — roughly 20–40 binary variables, comfortably within the 117-variable scale already demonstrated on hardware (Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization). The single-hot constraint per position is enforced by the mixer Hamiltonian and post-selection of valid bitstrings. Everything outside the patch — the rest of the protein — is handled classically: a surrogate model trained on real data scores full-length sequences, so the quantum device proposes patch mutations while the classical loop evaluates whole-protein consequences. This decomposition also keeps the surrogate honest against the known failure where optimizers drift into non-natural, non-expressible sequence space (Cho et al.); we additionally adopt the proximal regularization from Proximal Exploration for Model-guided Protein Sequence Design, penalizing distance from wild type:

$$\tilde f_k(s) = \hat f_k(s) + \lambda\, d(s, s^{\text{wt}})$$

where $\hat f_k$ is surrogate-estimated objective $k$, $d$ is Hamming distance from the wild-type sequence, and $\lambda$ trades off fitness against mutational caution.

Multi-objectivity enters through replica decomposition, in the spirit of MOEA/D. Each of $R$ tempered replicas minimizes a different scalarization

$$f_r(s) = \sum_{k=1}^{K} w_{r,k}\, \tilde f_k(s), \qquad w_{r,k} \ge 0,\ \sum_k w_{r,k} = 1,$$

with weight vectors $w_r$ spread over the simplex so that the replica ensemble collectively covers the Pareto front, and replica exchange (parallel tempering) letting proposals flow across trade-off regimes — exactly the machinery that made the quantum MCMC work, generalized from one energy function to $R$ scalarized ones.

The objectives themselves come from data. Pairwise (Potts-style) epistatic models fit to the roughly 1.8 million variants in Megascale give a stability objective whose coupling matrix maps directly onto two-body Ising terms under one-hot encoding (Mutation effects predicted from sequence co-variation establishes that pairwise co-variation captures much of mutational interaction); low-order spectral truncation in the spirit of Epistatic Net (Epistatic Net allows the sparse spectral regularization of deep neural networks for inferring fitness functions) handles the residual higher-order terms. A second objective is functional fitness from the 56,806-variant GFP dataset; a third, in a separate task, is developability (solubility-style predictors of the kind used in Property-Driven Protein Inverse Folding with Multi-Objective Preference Alignment). Warm-starting uses ESM-2 or ProteinMPNN marginal distributions at the patch positions to set both the initial classical state and the initial circuit parameters, testing the unexploited observation that foundation-model logits are strong priors while quantum circuits are initialization-sensitive.

Research Program

The work has five components. First, fit and validate the surrogate objectives on held-out data, including the out-of-distribution splits pioneered by FLIP2: Expanding Protein Fitness Landscape Benchmarks for Real-World Machine Learning Applications — this matters because FLIP2 found that across 16 splits, fine-tuned protein language models topped only 7, while ridge regression augmented with zero-shot likelihoods topped 4 and pure zero-shot scores topped another 4; if our surrogate collapses under distribution shift, everything downstream is meaningless. Second, construct the patch Hamiltonians from the learned couplings and verify, in a noiseless simulator, that measured low-energy bitstrings correspond to high-surrogate patches. Third, build the hybrid loop: quantum proposal kernel (a shallow $p\le 2$ QAOA-like circuit whose phase operator mixes the replica's scalarized Hamiltonian with neighboring replicas' objectives, encouraging cross-regime jumps) inside the parallel-tempered classical search. Fourth, run matched classical controls in the identical loop (described under Baselines). Fifth, move to noise-model simulation and, for the flagship runs, real hardware at the 20–117 qubit scale.

Proposed Experiments

The primary benchmark is the two-objective task: stability (Megascale-trained surrogate) versus functional fitness (GFP), over design patches in the avGFP region, evaluated in silico with the TAPE model as ground-truth oracle where applicable, following the protocol of Proximal Exploration for Model-guided Protein Sequence Design. The second task is a triple-objective setting mirroring Multi-Objective Protein Design via Memory-Aware Test-Time Scaling in Diffusion Models — hydrophobicity, surface exposure, and predicted structural confidence (pLDDT) — so we can compare directly against its reported diffusion-based result and its RERD baseline. The third task tests affinity versus developability on the antibody-antigen complexes of the AffinityDesign benchmark (47 complexes) used by Advancing Protein Design via Multi-Agent Reinforcement Learning with Pareto-Based Collaborative Optimization. Metrics are hypervolume of the attained Pareto approximation, number of surrogate evaluations to reach a reference hypervolume, and mean Hamming distance from wild type at matched quality. All comparisons are run at matched evaluation budget and matched wall-clock, because surrogate evaluations are cheap while hardware shots are not — we report both, and we are explicit that the classical loop on a GPU may win on wall-clock even when the quantum loop wins per evaluation; both facts matter.

Baselines

The naive reference point is random search over the patch alphabet plus AdaLead, a standard greedy classical baseline, which on the TAPE-guided suite reported by Proximal Exploration for Model-guided Protein Sequence Design achieves an overall normalized score of 0.43. The strongest direct competitor is PEX itself, the proximal search method that reported an overall normalized score of 0.98 with MuFacNet surrogate (0.89 with a CNN surrogate) on the same suite, reaching high avGFP fitness in fewer than 10 mutations where baselines needed 20–50 — it is the strongest existing method on exactly our primary in-silico benchmark, and we will run it on the same surrogates, same objectives, same evaluation budget, and same tuning effort, with hypervolume and evaluations-to-threshold as the comparison. For the multi-objective population question, the strongest classical counterpart is NSGA-II (and MOEA/D, which our replica decomposition deliberately mirrors), since Variational Quantum Multi-Objective Optimization found classical evolutionary algorithms comparable to the quantum approach on synthetic problems; we run them with equal evaluation budgets. Where comparisons to trained multi-objective systems are meaningful we quote their published numbers on shared benchmarks — MAProt reports a +14.1% success-rate improvement over its DRAKES baseline on Megascale — rather than re-running them under different conditions. Finally, the decisive ablation isolates the quantum ingredient: the identical parallel-tempered multi-objective loop, with the quantum proposal kernel swapped for (a) single-position Gibbs mutations and (b) uniform random multi-position jumps of matched size, everything else unchanged. Beating the ablation in hypervolume per evaluation at statistical significance across task instances is what counts as the quantum proposal mechanism earning its place; beating AdaLead alone proves nothing.

Why not just…?

Why not just run NSGA-II or MOEA/D classically on the same surrogates? This is the most serious objection, and it is supported by the file: on synthetic multi-objective problems, QMOO's hypervolume was only comparable to NSGA-II, IBEA, and MOEA/D (Variational Quantum Multi-Objective Optimization), and the VQE benchmarking study showed shallow variational circuits rarely separate meaningfully from classical greedy search initialized at the same point, with the gap already shrinking by $N=61$ (Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice). We do not argue around this; we test it. The counter-evidence is that the one regime where hybrid quantum search did demonstrably help was rugged landscapes with non-local traps, where quantum jumps cut convergence iterations to 86% of classical MCMC on 117-variable instances (Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization) — and epistatic protein landscapes are precisely that regime. Our experiments are designed so that if NSGA-II matches us, that is a publishable, rigorous negative result on real landscapes, and we commit to reporting it as such.

Why not just use the existing classical test-time search frameworks (PEX, RosettaSearch, MOMST)? These are mature and strong: PEX reaches 0.98 normalized score with a strong surrogate, and RosettaSearch lifted design success from 7.9% to 20.5% on hard PDB monomer redesigns within a strict 75-structure-prediction budget (RosettaSearch: Multi-Objective Inference-Time Search for Protein Sequence Design). But they navigate by local or memory-guided moves: PEX explicitly constrains search to a proximal region, and MOMST's memory banks recycle previously seen elites. None of them can take a coordinated five-position leap to a distant basin in one step; that is exactly the move class a quantum superposition over patch states provides. Our comparison against PEX on the identical task and surrogate is the decisive test of whether that extra move class is worth anything in practice — and if it is not, we will say so.

Why not just warm-start a classical search well and skip the quantum hardware? Since we concede that initialization dominates performance, the skeptic will say the foundation-model warm start is doing all the work. This is a real threat, and the matched ablation above is designed to answer it directly: the classical control kernels receive the same warm start, the same surrogate, and the same replica structure, differing only in the proposal mechanism. Any advantage must therefore be attributable to the non-local quantum proposals and nothing else. We will additionally report a decomposition of attained solutions by their distance from the warm-started initialization, since quantum proposals should disproportionately contribute far jumps.

Why not just use simple linear surrogates instead of learned epistatic Hamiltonians? FLIP2 shows augmented ridge regression is a brutally tough baseline under distribution shift (FLIP2: Expanding Protein Fitness Landscape Benchmarks for Real-World Machine Learning Applications), so we validate every surrogate against it on OOD splits before using it inside the loop; where ridge wins, we use ridge. Note, though, that a purely additive surrogate produces a smooth landscape with no need for non-local jumps at all — the epistatic couplings are what create the traps our mechanism targets, so surrogate choice and proposal mechanism must be studied together.

Decisive Checks

Three results would settle the question. First, on the two-objective GFP task, quantum-proposal runs must reach the reference hypervolume in fewer surrogate evaluations than the matched classical ablation, across patch definitions, with significance over at least ten random seeds per condition. Second, the advantage must grow with measured landscape ruggedness (estimated epistatic variance of the surrogate), since that is the mechanism we claim; an advantage that appears equally on smooth additive surrogates would indicate a confound. Third, a hardware demonstration at 40–117 qubits on the flagship instance must degrade gracefully under noise — the proposal-engine architecture predicts robustness because bad proposals are simply rejected by the classical accept/reject step, unlike QMOO-style readout where noise corrupts the final population. If the first check fails everywhere, the deliverable becomes the first controlled negative result for quantum multi-objective search on real biophysical landscapes, together with the reusable infrastructure of epistatic patch Hamiltonians and warm-started hybrid loops — evidence the field currently lacks, since every quantum multi-objective result to date sits on synthetic spin models.