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

• URL: http://arxiv.org/abs/2607.02622v1
• Date: Thu, 02 Jul 2026 08:37:59 GMT
• Title: COMET: Combinatorial Optimization for Multiplex Editing Targets Via Constraint-Preserving QAOA
• Abstract summary: Multiplex CRISPR-Cas9 gene editing requires selecting one guide RNA per target gene subject to cross-gene interactions.<n>The one-hot per-gene constraint is conventionally enforced by adding penalty terms to the cost Hamiltonian.<n>An alternative is to enforce the constraint structurally via the XY-mixer, which preserves feasibility by construction.
• Score: 0.010923877073891442
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 QAOA on 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.

Related papers

• Quantum Optimisation for Protein-Protein Interaction Network Alignment [0.4763980315619087]
  Protein-protein interaction (PPI) network alignment combines topological and sequence information to identify conserved modules across species.<n>We model the alignment as a weighted maximum common induced subgraph problem and reformulate it through a modular product graph.<n>We develop a hybrid framework combining kernelisation, branch-and-bound, and seven Quantum Approximate optimisation algorithms.
  arXiv  Detail & Related papers  (2026-09-04T15:04:55Z)
• Denoised Variance-Based Pruning with Optimal Brain Bias Compensation [45.88028371034407]
  Variance-Based Pruning (VBP) introduced a promising paradigm by selecting neurons based on activation variance.<n>We introduce Denoised Variance-Based Pruning with Optimal Brain Bias Compensation (DVBP + OB$2$C)<n>It achieves state-of-the-art training-free performance; at 50% pruning, it retains over 90% of the original Top-1 accuracy.
  arXiv  Detail & Related papers  (2026-08-18T11:23:49Z)
• Polynomial Time Quantum Approximation Schemes for Constrained Optimisation [0.2578242050187029]
  We build on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA.<n>We introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical-processing cost by one power of the problem size.<n> Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables or improve every tested QOptlib reference tour.
  arXiv  Detail & Related papers  (2026-08-02T09:35:42Z)
• Hardware-Aware QUBO Reformulation of Constrained Binary Optimization via the Walsh-Fourier Transform [1.3423094548772225]
  We present a novel framework for reformulating constrained binary optimization as Quadratic Unconstrained Binary Optimization (QUBO)<n>We show that this hardware-native surrogate can outperform denser full-pairwise projections, despite being drawn from a strictly smaller approximation space.<n>This advantage widens once the QUBO is embedded and sampled on quantum annealers, yielding samples with the lowest worst-case and mean objective gaps compared to unbalanced penalization and a hardware-blind projection onto all quadratic terms.
  arXiv  Detail & Related papers  (2026-07-28T23:45:18Z)
• Constraint Preserving XY-Mixers under Trotterized Adiabatic Evolution [0.0]
  We investigate the interplay between constraint-preserving XY-mixers and Trotterized Adiabatic Evolution (TAE)<n>We show that the dominant contribution depends on the size and structure of individual constraints rather than on the total problem size.<n>For problems whose constraints decompose into multiple disjoint local blocks, XY-mixers outperform X-mixers by several orders of magnitude even under Trotterized evolution.
  arXiv  Detail & Related papers  (2026-05-04T11:08:34Z)
• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  Existing techniques rely on qubit reduction at the cost of information loss, leading to degraded computational performance.<n>We propose the Equivalence-preserving Qubit Efficient QAOA, which significantly reduces the required number of qubits without degrading performance.<n>We show that it is broadly applicable to large-scale optimization problems, excluding only unconstrained problems with completely independent variables.
  arXiv  Detail & Related papers  (2026-04-20T13:57:49Z)
• Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly [0.42970700836450487]
  We develop near-term quantum optimisation approaches for genome assembly problems.<n>We use the Iterative-QAOA framework, which combines a fixed linear-ramp QAOA schedule with iterative warm-start bias updates.<n>A custom circuit compilation strategy reduces hardware gate overhead by up to 67% compared with standard tools.
  arXiv  Detail & Related papers  (2026-04-07T17:17:34Z)
• BPDQ: Bit-Plane Decomposition Quantization on a Variable Grid for Large Language Models [56.504879072674015]
  We propose Bit-Plane Decomposition Quantization (BPDQ), which constructs a variable quantization grid via bit-planes and scalar coefficients.<n>BPDQ enables serving Qwen2.5-72B on a single GTX 3090 with 83.85% GSM8K accuracy (vs. 90.83% at 16-bit)
  arXiv  Detail & Related papers  (2026-02-04T02:54:37Z)
• Provably Optimal Quantum Circuits with Mixed-Integer Programming [0.0]
  We present a depth-aware optimization framework for quantum circuit compilation.<n>For exact synthesis of a target unitary, we formulate a mixed-integer linear program (MILP) that linearly global-phase equivalence.<n>To scale beyond exact MILP, we propose a novel rolling-Circuit optimization (RHO) that rolls primarily in time, caps the active-qubits, and enforces per-qubit closure.
  arXiv  Detail & Related papers  (2025-10-01T08:25:43Z)
• Stochastic Optimal Control Matching [53.156277491861985]
  Our work introduces Optimal Control Matching (SOCM), a novel Iterative Diffusion Optimization (IDO) technique for optimal control. The control is learned via a least squares problem by trying to fit a matching vector field. Experimentally, our algorithm achieves lower error than all the existing IDO techniques for optimal control.
  arXiv  Detail & Related papers  (2023-12-04T16:49:43Z)
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
  The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum-classical algorithm used to approximately solve optimisation problems. While QAOA can be implemented on NISQ devices, physical limitations can limit circuit depth and decrease performance. This work introduces the eXpressive QAOA (XQAOA) that assigns more classical parameters to the ansatz to improve its performance at low depths.
  arXiv  Detail & Related papers  (2023-02-09T07:47:06Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.