Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF)

This paper demonstrates that parallelizing the Hamiltonian Auto Decomposition Optimisation Framework (HADOF) across single and multiple IBM quantum processors significantly reduces wall-clock time for solving large-scale combinatorial optimization problems, including real-world genome assembly instances, while maintaining solution quality and advancing toward high-performance quantum computing.

The Gist

Imagine you are trying to solve a massive, incredibly complex jigsaw puzzle. This isn't just any puzzle; it's a "Quantum Puzzle" that represents a real-world problem, like figuring out the correct order of DNA strands to assemble a genome.

The problem is that the puzzle is too big for any single person (or a single quantum computer) to hold in their hands. The pieces are too numerous, and the "noise" in the room (hardware errors) makes it hard to see the picture clearly. If you try to force the whole puzzle onto one small table, it won't fit, and you'll likely make mistakes.

This paper introduces a new strategy called HADOF (Hamiltonian Auto Decomposition Optimisation Framework) to solve this. Here is how it works, using simple analogies:

1. The Problem: The "Too-Big-to-Hold" Puzzle

Current quantum computers are like tiny, noisy workbenches. They can only hold a few puzzle pieces at a time. If you try to solve a huge problem (like a genome with thousands of DNA fragments) all at once on one of these workbenches, the computer gets overwhelmed, the pieces get jumbled by "noise," and the solution fails.

2. The Solution: Breaking it into "Mini-Puzzles"

Instead of trying to solve the giant puzzle in one go, HADOF acts like a master organizer. It breaks the massive puzzle down into hundreds of tiny, manageable "mini-puzzles" (sub-problems).

• The Magic Trick: It doesn't just chop the puzzle randomly. It uses a smart system to look at the pieces you've already placed and uses that information to help solve the next mini-puzzle.
• The Iteration: It solves a mini-puzzle, learns from it, updates its understanding of the whole picture, and then solves the next one. It repeats this until the whole image is clear.

3. The New Twist: The "Assembly Line" (Parallelization)

Previously, this method worked like a single worker on an assembly line: solve mini-puzzle #1, then #2, then #3. This takes a long time.

The authors of this paper upgraded the system to run like a busy factory with multiple assembly lines.

• Single Worker vs. Team: Instead of one person solving the mini-puzzles one by one, they used a team of workers (multiple Quantum Computers, or QPUs) to solve different mini-puzzles at the exact same time.
• The Result: They found that by using a team of four quantum computers, they could finish the job 3 to 4 times faster than using just one. Even using just one computer but organizing the work in parallel made it 3 times faster.

4. The Real-World Test: Reassembling a DNA "Story"

To prove this works in the real world, the team tested it on a specific biological problem: Genome Assembly.

• The Analogy: Imagine you have shredded a book into thousands of tiny strips of paper (DNA reads). Your job is to tape them back together in the right order to read the story.
• The Test: They took a real biological dataset (a virus called $\phi$X174) and tried to reassemble it using their new "team of quantum computers."
• The Outcome:
  • Speed: The parallel approach was much faster at getting a result.
  • Quality: While the noisy quantum computers didn't get a perfect 100% score (due to the hardware "noise"), they still found very good solutions. In fact, over 50% of the solutions they generated were correct enough to be fixed into the perfect answer using standard post-processing tools.
  • Comparison: When they tried to solve the whole DNA puzzle on a single quantum computer without breaking it down, the computer failed to find a good solution. The "break-it-down" method (HADOF) succeeded where the "all-at-once" method failed.

5. The Big Picture: "High Performance Quantum" (HPQ)

The authors call this approach High Performance Quantum (HPQ) computing.

• Think of it like the difference between a single person trying to move a mountain of sand with a spoon versus a fleet of trucks working together.
• The paper argues that to make quantum computers truly useful for big problems, we can't just wait for them to get bigger and quieter. We have to change how we use them: by breaking problems into small pieces and solving them in parallel across many machines.

Summary of Claims

• Speed: Using multiple quantum computers in parallel makes solving these problems 3–4 times faster.
• Scalability: This method allows us to solve problems (like 500 variables) that are currently too big for a single quantum computer to handle.
• Accuracy: Even with noisy, imperfect hardware, this method finds better solutions than trying to solve the whole problem at once.
• Real Application: It successfully demonstrated this on a real-world genome assembly task, showing it's not just a theory but a working tool.

In short, the paper says: "Don't try to eat the whole elephant in one bite. Break it into small pieces, and have a team of quantum computers eat them all at the same time. It's faster, and it works better."

Technical Summary

1. Problem Statement

The practical application of quantum optimization for combinatorial problems (formulated as Quadratic Unconstrained Binary Optimization, or QUBO) is currently bottlenecked by the limitations of Noisy Intermediate-Scale Quantum (NISQ) devices. Key constraints include:

• Limited Qubit Counts: Current hardware cannot host large QUBO problems requiring hundreds of variables.
• Hardware Noise: Noise accumulation in deep circuits degrades solution quality.
• Scalability: Existing decomposition methods (like HADOF) are predominantly sequential, failing to exploit the parallelism available in distributed quantum architectures or High Performance Computing (HPC) resources.
• Simulation Limits: Simulating large quantum circuits classically is computationally expensive and memory-intensive.

The paper addresses these issues by extending the Hamiltonian Auto Decomposition Optimisation Framework (HADOF) to support parallel execution across single and multiple Quantum Processing Units (QPUs), aiming to achieve High Performance Quantum (HPQ) computing.

2. Methodology

Core Framework: HADOF

HADOF decomposes a global QUBO Hamiltonian into smaller, manageable sub-Hamiltonians that can be solved iteratively.

1. Decomposition: The global problem is split into sub-problems (subsets of variables).
2. Iterative Solving: Each sub-problem is solved using a quantum optimizer (QAOA).
3. Context Integration: The expected values ($E[x_i]$) of variables from solved sub-problems are used to approximate the context for subsequent sub-problems.
4. Aggregation: Solutions are recombined to form a global solution.

The Parallel Extension

The authors introduce a parallelized version of HADOF that differs from the sequential baseline in two key ways:

• Independent Generation: In each iteration, all sub-Hamiltonians are generated simultaneously using expected values from the previous iteration (rather than updating values sequentially within the current iteration).
• Asynchronous Execution: Sub-circuits are solved concurrently. This allows for:
  • Intra-QPU Parallelism: Running multiple jobs on a single QPU (leveraging the scheduler).
  • Inter-QPU Parallelism: Distributing jobs across multiple distinct QPUs (e.g., IBM Kingston, Pittsburgh, Fez, Marrakesh).

Implementation Details

• Optimizer: Uses a digitized QAOA approach with Trotterized Annealing Parametrization to avoid classical optimization loops for parameters $\beta$ and $\gamma$.
• Circuit Depth: Circuits are built layer-by-layer (up to 5 layers). In each iteration, one layer is added to all sub-circuits.
• Sub-problem Size: Fixed at 5 qubits ($k=5$) to maintain high fidelity on current hardware.
• Target Application: Genome Assembly, modeled as a Travelling Salesman Problem (TSP) on an overlap graph. The problem is encoded into a QUBO where the goal is to find the Hamiltonian path.

3. Key Contributions

1. First Real-Device HADOF Implementation: The study moves HADOF from theoretical simulation to execution on real IBM QPUs (Kingston, Pittsburgh, Fez, Marrakesh).
2. Parallelization Strategy: Demonstrates a framework for concurrent execution of decomposed subproblems, achieving significant speedups in wall-clock time without compromising solution quality.
3. HPQ Paradigm Validation: Positions HADOF as a viable pathway toward High Performance Quantum computing by integrating algorithmic decomposition with system-level parallelism.
4. Real-World Application: Successfully applies the framework to a genome assembly problem (ϕX174 bacteriophage), demonstrating its utility in computational biology.
5. Benchmarking: Provides a comprehensive comparison between Sequential HADOF, Parallel HADOF (Single and Multi-QPU), Standard Full-Circuit QAOA, and Classical Simulated Annealing.

4. Key Results

Speed and Efficiency

• Wall Clock Time:
  • Multi-QPU Parallel: Achieved a 3–4× reduction in wall-clock time compared to sequential execution on real hardware.
  • Single-QPU Parallel: Achieved up to a 3× speedup even on a single device due to efficient job orchestration.
  • Simulation: Predicted >5× speedup in parallel simulation modes.
• QPU Usage: While total QPU usage time remains proportional to the number of circuits, the makespan (total time to solution) is drastically reduced, making the approach practical for time-sensitive applications.

Accuracy and Robustness

• vs. Standard QAOA: HADOF significantly outperforms full-circuit QAOA on real hardware.
  • Standard QAOA accuracy dropped to near zero (e.g., 0.02) for 50-variable problems on noisy hardware due to noise accumulation.
  • HADOF maintained >0.80 accuracy on real hardware for similar sizes.
• Noise Resilience: Decomposition limits circuit depth, preventing the exponential degradation of accuracy seen in monolithic circuits.
• Genome Assembly Case Study:
  • Ideal Simulation: Both sequential and parallel HADOF achieved 100% best accuracy (matching Simulated Annealing).
  • Real Hardware: Best accuracy remained competitive (0.88–0.91), though the frequency of finding the exact ground state dropped to zero due to noise. However, >52% of sampled solutions could be post-processed to recover the correct sequence using standard bioinformatics tools (GFAtools).

Scalability

• HADOF successfully solved QUBO problems with up to 500 variables in simulation and 300 variables on real hardware using only 5-qubit circuits.
• Standard full-circuit QAOA is limited to ~50 variables on the same hardware due to connectivity and embedding constraints.

5. Significance and Conclusion

This research demonstrates that decomposition and parallelism are not merely workarounds for current hardware limitations but are fundamental enablers of practical quantum advantage.

• Scalability: HADOF bypasses the physical qubit limits of current devices, allowing the solution of problems far larger than the hardware can natively support.
• HPQ Alignment: The framework aligns with the emerging High Performance Quantum computing paradigm, showing that distributed quantum architectures can deliver substantial performance gains.
• Practical Viability: By successfully applying the method to genome assembly, the paper proves that quantum optimization can be integrated into real-world scientific pipelines, provided that noise is managed through decomposition and parallel execution strategies.

The authors conclude that future work should focus on adaptive decomposition strategies, error mitigation techniques, and integrating HADOF into standard genome assembly pipelines with real sequencing data.