COMET: Combinatorial Optimization for Multiplex Editing Targets Via Constraint-Preserving QAOA

Sep 21, 2026

Uploaded by Violet

Multiplex CRISPR-Cas9 gene editing selects one guide RNA per target gene while respecting cross-gene interactions, forming a constrained combinatorial optimization problem. The work models the task as a QUBO solved by QAOA, comparing two constraint-enforcement methods: penalty terms in the cost Hamiltonian versus structural enforcement via an XY-mixer that preserves one-hot feasibility. A three-gene, twelve-qubit multiplex instance targeting PDCD1, LAG3, and HAVCR2 is benchmarked in simulation and validated on IBM ibm_kingston.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

AccessFree to download

Introduction

Problem framing: multiplex gRNA selection as constrained combinatorial optimization

QUBO and QAOA formulation

Constraint enforcement: penalty vs XY-mixer

COMET: Combinatorial Optimization for Multiplex Editing Targets Via Constraint-Preserving QAOA Priyansh Singhal Independent Researcher India [priyansh.s21@iiits.in](priyansh.s21@iiits.in) Sumit Maheshwari† Microsoft Boston, USA [sumit.maheshwari@microsoft.com](sumit.maheshwari@microsoft.com) Piyush Joshi Department of Computer Science & Engineering IIIT Sri City, India [piyush.j@iiits.in](piyush.j@iiits.in) arXiv :2607 .02622v1 [ quant-ph] 2 Jul 2026 Abstract—Multiplex CRISPR-Cas9 gene editing requires selecting one guide RNA per target gene subject to cross-gene interactions: a constrained combinatorial problem that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) and solved via the Quantum Approximate Optimization Algorithm (QAOA). The one-hot per-gene constraint is conventionally enforced by adding quadratic penalty terms to the cost Hamiltonian, but penalty coefficient selection is heuristic and penalties amplify hardware noise. An alternative is to enforce the constraint structurally via the XY-mixer, which preserves feasibility by construction. We present COMET, a systematic comparison of penalty-based and XY-mixer QAOAon a three-gene, twelve-qubit multiplex editing instance targeting the immune-checkpoint genes PDCD1, LAG3, and HAVCR2. In simulation, the XY-mixer exceeds 95% probability of the optimum by QAOA depth p=3, while three penalty variants spanning an order of magnitude in penalty coefficient remain below 6% at every depth. On IBM’s ibm_kingston (Heron r2) processor, the XY-mixer’s simulator–hardware energy gap stays within |0.8| across all depths, while the worst-tuned penalty variant’s gap reaches +53 .9. We provide an honest account of where the structural guarantee partially breaks under gate-level noise. The twelve-qubit instance is classically trivial; our contribution is a methodological comparison of constraint-enforcement strategies in a biologically motivated domain, with real-hardware validation. Index Terms—combinatorial optimization, multiplex gene editing, XY-mixer, QAOA, QUBO, constraint enforcement I. INTRODUCTION Multiplex CRISPR-Cas9 [1],[2] editing which is simultaneous disruption of multiple genomic loci in a single experiment has emerged as an essential capability in cell and gene therapies, particularly in cancer immunotherapy [3], where concurrent knockout of redundant immune-checkpoint genes can amplify anti-tumor T-cell activity [4]–[6] A practical bottleneck in such experiments is the selection of guide RNAs (gRNAs): each gene admits many candidate gRNAs, each scored along on-target efficacy and off-target risk [7], and for multiplex experiments these choices interact across genes. AgRNA that is individually strong may be a poor partner to the strong picks for other genes in the panel, owing to synergistic †Work done in personal capacity; does not reflect the views of Microsoft. toxicity, resource competition, or beneficial synergy. The selection problem is therefore combinatorial over the joint space of per-gene candidates. We demonstrate this concretely in a three-gene instance (PDCD1 [8], LAG3 [9], HAVCR2 [10]) with four candidates per gene. The biologist’s natural heuristic (pick the most potent candidate per gene) produces the worst of all 64 feasible selections at rank 64/64, because the three individually-best candidates share the strongest positive pairwise couplings. The true optimum, which differs at every gene from the greedy pick, cannot be obtained by any per-gene ranking. This “greedy trap” motivates formulation of multiplex gRNA selection as a constrained combinatorial optimization problem. Such problems map naturally to Quadratic Unconstrained Binary Optimization (QUBO), and from there to the cost Hamiltonian of the Quantum Approximate Optimization Algorithm (QAOA) [11] . However, QAOA’s canonical formulation cannot directly represent the one-hot constraint (one gRNA per gene): constraints must be absorbed into th

FAQs

What constraint makes multiplex gRNA selection a difficult optimization problem?

Each gene must select exactly one guide RNA (a one-hot per-gene constraint), while choices across genes interact through cross-gene couplings, creating a constrained combinatorial search space.

How does penalty-based QAOA enforce the one-hot constraint?

It absorbs the constraint into the cost Hamiltonian using quadratic penalty terms with a tunable coefficient, which can distort the optimization landscape and amplify hardware noise.

What is the key advantage of using an XY-mixer for constraint enforcement?

The XY-mixer structurally preserves feasibility by construction: starting from a one-hot feasible state, the evolution remains confined to the feasible subspace, removing the need for penalty terms in the cost Hamiltonian.

Sep 21, 2026

Uploaded by Violet