⚛️ quantum physics

Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly

This paper proposes a nonvariational quantum optimization framework using Iterative-QAOA and a novel higher-order binary formulation to efficiently solve the NP-hard pangenome-guided sequence assembly problem, demonstrating that current quantum hardware can identify optimal genome walks with reduced qubit requirements and gate overhead.

Original authors: Josh Cudby, Sergii Strelchuk

Published 2026-04-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Josh Cudby, Sergii Strelchuk

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Solving a Giant Jigsaw Puzzle with a Quantum Computer

Imagine you have a massive, messy pile of puzzle pieces. These pieces are tiny snippets of DNA (called "reads") cut from a person's genome. Your goal is to put them back together to see the full picture of that person's genetic code.

The Problem:
In some parts of the genome, the puzzle pieces look almost identical. It's like having 500 pieces that all look like a patch of blue sky. If you try to assemble this using a standard map (a "reference"), you might force a piece into the wrong spot because it looks similar to where it should go, but isn't actually there. This is called "reference bias."

The Solution (PGSA):
Instead of using a single map, the authors use a Pangenome. Think of this not as a single map, but as a giant, crowded subway system (a graph) that shows every possible route a train could take through a city. The goal is to find the one specific route (the walk) that matches the number of times we saw each station in our puzzle pieces.

The Bottleneck:
Finding the perfect route through this subway system is incredibly hard. It's a math problem so complex that even the world's fastest supercomputers get stuck when the city gets too big. This is where the paper steps in.

The New Approach: Using a Quantum "Magic Compass"

The authors are testing a new way to solve this puzzle using Quantum Computers. Specifically, they are using a method called Iterative-QAOA.

Here is how they explain it using two different "languages" (encodings) to talk to the quantum computer:

1. The "QUBO" Method (The Detailed Map)

The Analogy: Imagine you are trying to find a path through a maze. In this method, you draw a separate line for every single step you could take at every single moment in time.
The Pros: It's easy for the computer to understand the rules (it's a simple "yes/no" for every step).
The Cons: The map gets huge very quickly. If your maze has 100 intersections, you need thousands of lines to draw the map. It's like trying to carry a library of maps in your pocket.

2. The "HUBO" Method (The Compact Code)

The Analogy: Instead of drawing a line for every step, you give every intersection a binary code (like a zip code: 001, 010, 011). Now, instead of drawing thousands of lines, you just write down the sequence of zip codes.
The Pros: It's incredibly efficient. You can fit a massive city map into a tiny notebook. This saves "qubits" (the memory of the quantum computer).
The Cons: The instructions to read this code are much more complex. It's like trying to solve a riddle instead of reading a sign. The quantum computer has to do deeper, more complicated calculations, which makes it more sensitive to "noise" (static or errors).

The Strategy: "Warm-Start" and "Iterative"

The paper introduces a clever trick to make the quantum computer work better on today's imperfect machines.

The Old Way (Variational):
Usually, you tell a quantum computer, "Try a million different settings to find the best answer." This is slow and often gets stuck in a local trap (like a hiker getting stuck in a small valley thinking it's the bottom of the mountain).

The New Way (Iterative-QAOA):
Think of this as hiking with a guide.

Start: You take a guess at the path (a "warm start").
Walk: You take a few steps using a fixed, pre-planned rhythm (the "Linear Ramp"). You don't stop to adjust your strategy every step; you just follow the rhythm.
Check: You look at where you ended up. Did you find a good spot?
Adjust: Based on where you landed, you slightly nudge your starting point for the next hike.
Repeat: You do this a few times. Each time, you get closer to the true bottom of the mountain (the optimal solution).

This avoids the slow, expensive process of re-calculating the whole strategy every time. It's like taking a few steps, checking your compass, and adjusting your direction, rather than trying to calculate the entire route before taking a single step.

The Results: What Did They Find?

The team tested this on both a perfect simulator (no errors) and real quantum hardware (IBM's "Boston" chip, which has some static/noise).

The "QUBO" (Detailed Map) Results:
- On the simulator, it worked beautifully. It found the perfect path very quickly.
- On the real hardware, it worked well for smaller puzzles (24 to 48 pieces). The computer was able to ignore the "static" and find the right answer, especially when they used a trick called CVaR (which is like only listening to the clearest voices in a noisy room and ignoring the rest).
The "HUBO" (Compact Code) Results:
- This was the "high risk, high reward" approach. It used fewer qubits (good!), but the calculations were deeper and noisier.
- On the simulator, it worked great.
- On real hardware, it struggled a bit more because the "riddles" were too complex for the current noisy machines. However, it proved that we can solve bigger problems with fewer resources if we get better at handling the noise.

The Bottom Line

This paper is a proof of concept. It shows that:

Quantum computers can help solve biological puzzles that are too hard for classical computers.
We don't need perfect quantum computers yet. Even with current noisy machines, using smart strategies (like the "warm-start" hiking guide) allows us to find good answers.
There is a trade-off: You can either use a lot of memory with simple rules (QUBO) or save memory with complex rules (HUBO). As quantum computers get better, the "complex rules" approach will likely become the winner because it saves space.

In short: The authors have built a new, smarter compass for navigating the genetic subway system. While the compass isn't perfect yet, it's the first step toward using quantum magic to cure diseases by understanding our DNA better.

1. Problem Statement

The paper addresses a critical bottleneck in Pangenome-Guided Sequence Assembly (PGSA), a method for reconstructing individual genomes from short-read sequencing data using a population-level pangenome graph.

The Challenge: While PGSA reduces reference bias, the core computational task—identifying a walk through the graph where node visitation frequencies match read-derived copy numbers—is NP-hard.
Specific Formulation: The authors formalize this as Oriented Tangle Resolution. Given a vertex-weighted, oriented graph $G$ , the goal is to find a walk $W$ that minimizes the cost function:
$C_G(W) = \sum_{v \in V} (\#W(v^+) + \#W(v^-) - w(v))^2$
where $\#W(v)$ represents the number of visits to a node and $w(v)$ is the target weight (copy number).
Classical Limitations: Existing classical solvers struggle with moderate-scale instances due to the exponential growth of the solution space and the combinatorial complexity of repetitive genomic regions.

2. Methodology

The authors propose a non-variational quantum optimization approach using the Iterative-QAOA framework to solve the Oriented Tangle Resolution problem.

A. Problem Encodings

Two distinct binary optimization formulations are developed:

Quadratic Unconstrained Binary Optimization (QUBO):
- Encoding: Uses binary variables $x_{t,v,b}$ representing a visit to vertex $v$ with orientation $b$ at time step $t$ .
- Complexity: Requires $O(TN)$ variables (where $T$ is walk length and $N$ is graph size), effectively $O(N^2)$ .
- Pros: Shallow circuits, compatible with current hardware constraints.
- Cons: High qubit count limits problem size.
Higher-Order Unconstrained Binary Optimization (HUBO):
- Encoding: Encodes node indices in binary ( $x_{t,k}$ ) rather than enumerating node-time pairs.
- Complexity: Reduces variables to $O(T \log N)$ , effectively $O(N \log N)$ .
- Pros: Significant qubit efficiency, allowing larger graphs to be encoded on current devices.
- Cons: Introduces higher-order interaction terms (multi-qubit Z-rotations), leading to deeper compiled circuits and increased noise sensitivity.

B. The Algorithm: Iterative-QAOA

Instead of standard variational QAOA (which requires a costly classical optimization loop prone to barren plateaus), the authors use Iterative-QAOA:

Fixed Schedule: Uses a Linear-Ramp (LR-QAOA) schedule where parameters $\beta_k$ and $\gamma_k$ follow a fixed linear progression, eliminating the need for variational parameter tuning.
Warm-Start & Bias Updates:
1. Initialize qubits with a prior distribution (biases).
2. Run the fixed-depth QAOA circuit.
3. Measure outcomes and compute energies.
4. Update the initial state biases for the next iteration based on a log-quadratic model of the measured bitstrings, focusing the search on low-energy regions.
Post-Selection: Uses Conditional Value at Risk (CVaR) to filter samples, keeping only the top $\alpha$ fraction of low-energy outcomes to update biases, mitigating noise effects.

C. Circuit Compilation

A custom compilation strategy was developed to handle the specific hardware constraints (IBM Heavy-Hex topology):

Optimization: Utilizes edge-coloring for pairwise interactions and a bespoke MAX-SAT solver to optimize layouts for higher-order terms in HUBO.
Efficiency: Reduces two-qubit gate counts and circuit depth by up to 67% compared to standard Qiskit transpilation, crucial for preserving coherence on NISQ devices.

3. Key Results

The study benchmarks the approach on synthetic pangenome graphs using both noiseless Matrix Product State (MPS) simulations and real hardware (IBM Boston).

QUBO Performance:
- Simulation: Iterative-QAOA reliably finds optimal solutions for instances up to 80 qubits. Optimal solutions were found in as few as 10–17% of the total search space.
- Hardware: On a 24-qubit instance, hardware results with $p=1$ (shallow depth) and CVaR post-selection closely matched noiseless simulations. For a 48-qubit instance, optimal solutions were found by iteration 3 with sufficient sampling.
- Depth Trade-off: While deeper circuits ( $p=3, 5$ ) converged faster in simulation, shallow circuits ( $p=1$ ) were more robust on noisy hardware.
HUBO Performance:
- Qubit Efficiency: Successfully encoded smaller instances (12–20 qubits) with fewer variables, demonstrating the potential to tackle larger graphs than QUBO allows.
- Noise Sensitivity: HUBO circuits were deeper and more sensitive to noise. While optimal solutions were found in simulation, hardware results showed deviations, particularly for larger instances (15+ qubits) with high two-qubit gate counts.
- Convergence: In some cases, deeper HUBO circuits converged to suboptimal modes, highlighting the non-trivial relationship between circuit depth, parameter schedules, and problem structure.
Compilation Gains: The custom transpiler achieved a 43% to 67% reduction in two-qubit gate depth compared to standard tools, directly enabling the execution of these complex circuits on current hardware.

4. Key Contributions

Novel HUBO Formulation: Introduced a new $O(N \log N)$ encoding for genome assembly that drastically reduces qubit requirements, making moderate-sized pangenome graphs feasible for near-term quantum devices.
Non-Variational Framework: Demonstrated the efficacy of Iterative-QAOA (fixed schedule + iterative bias updates) for a biologically motivated NP-hard problem, avoiding the overhead and barren plateaus of full variational optimization.
Hardware Validation: Provided one of the first demonstrations of quantum optimization solving a specific, non-trivial genomics problem on real quantum hardware (IBM Boston), showing that error-mitigated results can match simulation trends.
Compilation Strategy: Developed a specialized transpilation technique that significantly reduces gate overhead for higher-order interactions, a critical step for running HUBO problems on NISQ devices.

5. Significance and Future Directions

Practical Utility: This work establishes pangenome assembly as a concrete problem class where quantum optimization may provide the first practical advantage over classical methods, specifically in the "moderate scale" regime where classical solvers struggle but quantum devices are just becoming capable.
Qubit vs. Depth Trade-off: The paper highlights a fundamental trade-off: QUBO is currently more robust on noisy hardware due to shallower circuits, while HUBO offers necessary qubit efficiency for scaling but requires better error mitigation and deeper circuits.
Path Forward: As hardware fidelity improves (reducing noise) and connectivity increases, the balance is expected to shift toward HUBO formulations. Future work must focus on:
- Systematic studies of instance structures.
- Adaptive CVaR strategies and stopping criteria.
- Integrating these optimizers into full end-to-end assembly pipelines to measure biological impact (contiguity, correctness).

In conclusion, the paper proves that near-term quantum devices, when paired with smart non-variational algorithms and custom compilation, can effectively tackle specific, hard subproblems in genomics, paving the way for "quantum utility" in bioinformatics.