Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF)
Pith reviewed 2026-05-07 06:02 UTC · model grok-4.3
The pith
Parallel execution of the Hamiltonian Auto Decomposition Optimisation Framework on multiple quantum processors reduces wall-clock time for combinatorial problems by up to four times.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that parallelised HADOF execution across sequential, single-QPU parallel, and multi-QPU modes delivers up to 3-4x wall-clock speedup on IBM quantum hardware for QUBO instances, with solution quality comparable to the sequential baseline. Simulated parallel runs exceed 5x speedup. The iterative decomposition of large QUBOs into smaller subproblems enables solving beyond single-device qubit limits, and both sequential and parallel variants achieve competitive accuracy on genome-assembly benchmarks while improving time to solution.
What carries the argument
Parallelised job orchestration of iteratively decomposed QUBO subproblems across one or more QPUs, which solves each subproblem on quantum or classical backends and stitches partial solutions together.
If this is right
- Combinatorial problems too large for single quantum devices become solvable by distributing subproblems across multiple processors.
- Even single-QPU runs become faster through improved job scheduling and parallel execution of independent subproblems.
- Genome assembly and similar real-world tasks gain practical speedups while retaining competitive accuracy.
- Simulated scaling indicates further time reductions as the number of available QPUs increases.
Where Pith is reading between the lines
- The same decomposition-plus-stitching pattern could be combined with classical heuristics to handle still larger instances in hybrid workflows.
- Distributed execution across remote quantum processors might become feasible once quantum networks improve, extending the approach beyond co-located hardware.
- The framework may apply to other iterative quantum algorithms that rely on problem splitting rather than direct embedding.
Load-bearing premise
Decomposing large optimization problems into smaller subproblems and combining their solutions preserves overall accuracy even when the subproblems are solved on noisy quantum hardware.
What would settle it
Apply the parallel HADOF variant to a genome-assembly instance larger than those tested, obtain a final solution, and compare its accuracy against a high-quality classical reference; a substantial drop in quality relative to the sequential version would show that decomposition and stitching errors dominate.
Figures
read the original abstract
Practical applicability of quantum optimisation on near term devices is constrained by limited qubit counts and hardware noise, which restricts the scalability of quantum optimisation algorithms for combinatorial problems. The simulation of large quantum circuits is also difficult and constrained by memory requirement. The Hamiltonian Auto Decomposition Optimisation Framework (HADOF) addresses this by decomposing large QUBOs into smaller subproblems that can be solved iteratively on quantum or classical backends. This allows the scalability of quantum QUBO algorithms beyond device limits, as well as their simulation on classical devices. In this research, we extend the evaluation of HADOF by benchmarking on real IBM QPUs across sequential, single-QPU parallel, and multi-QPU parallel execution modes, advancing toward High Performance Quantum (HPQ) computing for combinatorial optimisation problems. Experimental results on IBM quantum hardware demonstrate up to 3-4x reduction in wall clock time when utilising four QPUs compared to sequential execution baseline, while maintaining comparable solution quality. Notably, even single QPU execution benefits from parallelised job orchestration and execution, yielding up to 3x speedup. Simulated results predict over 5x speed-up in parallel execution mode. We further validate the practical applicability of the approach on real world genome assembly instances, showing that both sequential and parallel HADOF variants achieve competitive accuracy while significantly improving time to solution. These results highlight the importance of parallelism at both the algorithmic and system levels, positioning HADOF as a viable pathway toward scalable quantum optimisation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript extends the Hamiltonian Auto Decomposition Optimisation Framework (HADOF) by parallelizing its decomposition of large QUBOs into smaller subproblems for execution across multiple IBM QPUs (sequential, single-QPU parallel orchestration, and multi-QPU modes). It reports empirical wall-clock speedups of up to 3-4x with four QPUs (and >5x in simulation) relative to sequential baselines while claiming comparable solution quality, with additional validation on real-world genome assembly instances showing competitive accuracy and improved time-to-solution.
Significance. If the quality-preservation claims hold under the reported decomposition and stitching, the work would be a meaningful step toward scalable quantum optimization on NISQ hardware by demonstrating practical parallelism at the system level. The use of real IBM QPUs for timing measurements, the observation that even single-QPU parallel job orchestration yields up to 3x speedup, and the inclusion of genome-assembly benchmarks add concrete empirical value beyond purely simulated studies. These elements directly address qubit-count and noise barriers highlighted in the abstract.
major comments (3)
- [§4] §4 (Experimental Results on IBM QPUs): The central speedup claims (3-4x wall-clock reduction with four QPUs, up to 3x even on single QPU) are presented without error bars, number of independent runs, or statistical tests for the timing data. This is load-bearing because the abstract asserts concrete numerical improvements whose reliability cannot be assessed without variance information or significance testing.
- [§5] §5 (Genome Assembly Validation): The claim that both sequential and parallel HADOF variants achieve 'competitive accuracy' on genome-assembly instances lacks an ablation on iteration count versus quality degradation, an explicit error-bound analysis for the iterative decomposition, and a direct comparison against a non-decomposed classical solver on the identical instances. This directly tests the weakest assumption that stitching recovers globally consistent solutions without significant loss from noise or approximation accumulation.
- [§3] §3 (HADOF Parallelisation and Stitching): The description of the stitching procedure that recombines subproblem solutions is insufficiently detailed to determine whether it is heuristic or exact and how it handles potential inconsistencies introduced by noisy subproblem solves on hardware. This is load-bearing for the 'comparable solution quality' assertion that underpins the overall speedup claim.
minor comments (3)
- [Figure 2] Figure 2 (timing plots): Add explicit annotation of the sequential baseline time and consider a log scale on the y-axis to make the reported speed-up factors visually immediate.
- [Table 1] Table 1 (solution quality metrics): Clarify the exact definition of 'solution quality' or 'accuracy' used for both combinatorial benchmarks and genome instances (e.g., objective value, percentage of correct contigs, or Hamming distance to reference).
- [Abstract and §1] Abstract and §1: The phrase 'parameter-free' appears in the context of the original HADOF; confirm it is not inadvertently applied to the parallelized version, which introduces new orchestration parameters.
Simulated Author's Rebuttal
We thank the referee for their constructive and detailed feedback, which helps strengthen the manuscript. We address each major comment point by point below, indicating the revisions we will make.
read point-by-point responses
-
Referee: [§4] §4 (Experimental Results on IBM QPUs): The central speedup claims (3-4x wall-clock reduction with four QPUs, up to 3x even on single QPU) are presented without error bars, number of independent runs, or statistical tests for the timing data. This is load-bearing because the abstract asserts concrete numerical improvements whose reliability cannot be assessed without variance information or significance testing.
Authors: We agree that the timing results require statistical support to substantiate the speedup claims. Wall-clock times on IBM QPUs inherently vary due to hardware noise, queue delays, and execution fluctuations. In the revised manuscript, we will specify the number of independent runs (minimum of five per configuration), add error bars showing standard deviation, and include a brief statistical analysis (e.g., paired t-tests) confirming the significance of the observed 3-4x and 3x speedups. This directly addresses the reliability concern. revision: yes
-
Referee: [§5] §5 (Genome Assembly Validation): The claim that both sequential and parallel HADOF variants achieve 'competitive accuracy' on genome-assembly instances lacks an ablation on iteration count versus quality degradation, an explicit error-bound analysis for the iterative decomposition, and a direct comparison against a non-decomposed classical solver on the identical instances. This directly tests the weakest assumption that stitching recovers globally consistent solutions without significant loss from noise or approximation accumulation.
Authors: We acknowledge these gaps in the validation. We will add an ablation study in the revised §5 plotting solution quality against decomposition iteration count for the genome instances. We will also include an explicit error-bound discussion based on the propagation analysis from the original HADOF paper. However, exact non-decomposed classical solvers cannot handle the full genome QUBO sizes in reasonable time; we will instead provide comparisons against classical heuristics (simulated annealing and Gurobi on subproblems, plus full-instance metaheuristics) to demonstrate practical time-to-solution and consistency. This constitutes a partial revision that strengthens the section while respecting computational limits. revision: partial
-
Referee: [§3] §3 (HADOF Parallelisation and Stitching): The description of the stitching procedure that recombines subproblem solutions is insufficiently detailed to determine whether it is heuristic or exact and how it handles potential inconsistencies introduced by noisy subproblem solves on hardware. This is load-bearing for the 'comparable solution quality' assertion that underpins the overall speedup claim.
Authors: We agree the stitching description is insufficiently detailed. In the revised §3, we will expand the explanation to clarify that stitching is a heuristic procedure relying on variable-overlap consensus and majority voting to resolve inconsistencies. For hardware noise, it uses backend-reported solution confidence scores to weight sub-solutions and re-optimizes conflicting subproblems when inconsistency exceeds a tunable threshold. We will add pseudocode and a brief flowchart. This elaboration will better justify the maintained solution quality under parallel execution. revision: yes
Circularity Check
No significant circularity; claims rest on direct experimental benchmarks
full rationale
The paper reports empirical wall-clock timing measurements and solution-quality metrics on IBM QPUs for sequential vs. parallel HADOF executions (including genome-assembly instances). Speedup claims (3-4x on four QPUs, 3x on single QPU, >5x simulated) are obtained from direct hardware runs and simulations rather than any derivation, equation, or prediction that reduces to fitted parameters or prior self-citations by construction. No mathematical chain, uniqueness theorem, or ansatz is invoked whose validity depends on the present results. Self-reference to the original HADOF framework is limited to context-setting and is not load-bearing for the new parallelization or benchmarking claims, which are independently falsifiable via external timing data. The paper is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Large combinatorial problems can be faithfully encoded as QUBOs whose optimal solutions remain useful after decomposition and reassembly.
Reference graph
Works this paper leans on
-
[1]
Toward prediction of financial crashes with a D-Wave quantum annealer.Entropy (Basel), 25(2):323, February 2023
Yongcheng Ding, Javier Gonzalez-Conde, Lucas Lamata, José D Martín-Guerrero, Enrique Lizaso, Samuel Mugel, Xi Chen, Román Orús, Enrique Solano, and Mikel Sanz. Toward prediction of financial crashes with a D-Wave quantum annealer.Entropy (Basel), 25(2):323, February 2023
2023
-
[2]
Krishna Khadka, Jaganmohan Chandrasekaran, yu Lei, Raghu Kacker, and D. Kuhn. A combinatorial approach to hyperparameter optimization. pages 140–149, 06 2024
2024
-
[3]
A novel combinatorial optimization based feature selection method for network intrusion detection.Computers & Security, 102:102164, 2021
Anjum Nazir and Rizwan Ahmed Khan. A novel combinatorial optimization based feature selection method for network intrusion detection.Computers & Security, 102:102164, 2021
2021
-
[4]
The present and future of de novo whole-genome assembly.Briefings in Bioinformatics, 19(1):23–40, 10 2016
Jang-il Sohn and Jin-Wu Nam. The present and future of de novo whole-genome assembly.Briefings in Bioinformatics, 19(1):23–40, 10 2016
2016
-
[5]
Clement, Quinn Snell, Jared C
Paul Bodily, Mark J. Clement, Quinn Snell, Jared C. Price, Stanley Fujimoto, and Nozomu Okuda. Application of a max-cut heuristic to the contig orientation problem in genome assembly. InProceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics, BCB’13, page 476–483, New York, NY , USA, 2013. Associatio...
2013
-
[6]
Ignacio Cirac
Guillermo González-García, Rahul Trivedi, and J. Ignacio Cirac. Error propagation in nisq devices for solving classical optimization problems.PRX Quantum, 3:040326, Dec 2022
2022
-
[7]
Quantum computing in the NISQ era and beyond.Quantum, 2(79):79, August 2018
John Preskill. Quantum computing in the NISQ era and beyond.Quantum, 2(79):79, August 2018
2018
-
[8]
Obstacles to state preparation and variational optimization from symmetry protection.Quantum, 4:204, 2020
Sergey Bravyi, Martin Kliesch, Robert Koenig, and Ersen Tang. Obstacles to state preparation and variational optimization from symmetry protection.Quantum, 4:204, 2020
2020
-
[9]
Qaoa-in-qaoa: Solving large-scale maxcut problems on small quantum machines.Phys
Zeqiao Zhou, Yuxuan Du, Xinmei Tian, and Dacheng Tao. Qaoa-in-qaoa: Solving large-scale maxcut problems on small quantum machines.Phys. Rev. Appl., 19:024027, Feb 2023. 15 Sankar et al
2023
-
[10]
Pascuzzi, Zhihao Xu, Tengfei Luo, Eungkyu Lee, and In-Saeng Suh
Seongmin Kim, Vincent R. Pascuzzi, Zhihao Xu, Tengfei Luo, Eungkyu Lee, and In-Saeng Suh. Distributed quantum approximate optimization algorithm on a quantum-centric supercomputing architecture.arXiv preprint arXiv:2407.20212, 2025
-
[11]
Sankar, Georgios Miliotis, and Simon Caton
Namasi G. Sankar, Georgios Miliotis, and Simon Caton. Scalable quantum optimisation using hadof: Hamiltonian auto-decomposition optimisation framework. InProceedings of the 3rd International Workshop on AI for Quantum and Quantum for AI (AIQxQIA 2025), co-located with the 28th European Conference on Artificial Intelligence (ECAI 2025), volume 4153 ofCEUR ...
2025
-
[12]
Johnson, Aniello Esposito, Barbara Chapman, Marco Fiorentino, Kirk Bresniker, Ray Beausoleil, and Masoud Mohseni
Xin Zhan, K. Johnson, Aniello Esposito, Barbara Chapman, Marco Fiorentino, Kirk Bresniker, Ray Beausoleil, and Masoud Mohseni. A full stack framework for high performance quantum-classical computing, 10 2025
2025
-
[13]
https://quantum.cloud.ibm.com/, 2025
Ibm quantum. https://quantum.cloud.ibm.com/, 2025
2025
-
[14]
Genome assembly using quantum and quantum-inspired annealing.Sci
A S Boev, A S Rakitko, S R Usmanov, A N Kobzeva, I V Popov, V V Ilinsky, E O Kiktenko, and A K Fedorov. Genome assembly using quantum and quantum-inspired annealing.Sci. Rep., 11(1):13183, June 2021
2021
-
[15]
A quantum approximate optimization algorithm, 2014
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014
2014
-
[16]
A comparison of classical and quantum annealing dynamics.J
Sei Suzuki. A comparison of classical and quantum annealing dynamics.J. Phys. Conf. Ser., 143:012002, December 2009
2009
-
[17]
Ising formulations of many np problems.Frontiers in physics, 2:5, 2014
Andrew Lucas. Ising formulations of many np problems.Frontiers in physics, 2:5, 2014
2014
-
[18]
IBM ILOG Cplex. V12. 1: User’s manual for cplex.International Business Machines Corporation, 46(53):157, 2009
2009
-
[19]
The unconstrained binary quadratic programming problem: a survey.J
Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, and Yang Wang. The unconstrained binary quadratic programming problem: a survey.J. Comb. Optim., 28(1):58–81, July 2014
2014
-
[20]
A multilevel approach for solving large-scale qubo problems with noisy hybrid quantum approximate optimization
Filip B Maciejewski, Bao G Bach, Maxime Dupont, P Aaron Lott, Bhuvanesh Sundar, David E Bernal Neira, Ilya Safro, and Davide Venturelli. A multilevel approach for solving large-scale qubo problems with noisy hybrid quantum approximate optimization. In2024 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–10. IEEE, 2024
2024
-
[21]
Pennylane: Automatic differentiation of hybrid quantum- classical computations, 11 2018
Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M Alam, B Akashnarayanan, Ali Asadi, Juan Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas Bromley, Benjamin Cordier, Jack Ceroni, Alain Delgado, Olivia Matteo, and Nathan Killoran. Pennylane: Automatic differentiation of hybrid quantum- classical computa...
2018
-
[22]
Review of general algorithmic features for genome assemblers for next generation sequencers.Genomics Proteomics Bioinformatics, 10(2):58–73, April 2012
Bilal Wajid and Erchin Serpedin. Review of general algorithmic features for genome assemblers for next generation sequencers.Genomics Proteomics Bioinformatics, 10(2):58–73, April 2012
2012
-
[23]
Whole-genome sequencing in outbreak analysis.Clin
Carol A Gilchrist, Stephen D Turner, Margaret F Riley, William A Petri, Jr, and Erik L Hewlett. Whole-genome sequencing in outbreak analysis.Clin. Microbiol. Rev., 28(3):541–563, July 2015
2015
-
[24]
Novel avenues for the detection of cancer- associated viral genome integrations using long-read sequencing technologies.Cancers (Basel), 17(11):1740, May 2025
Larissa-Anna Bergmann, Alicja Pacholewska, and Michal R Schweiger. Novel avenues for the detection of cancer- associated viral genome integrations using long-read sequencing technologies.Cancers (Basel), 17(11):1740, May 2025
2025
-
[25]
Information-optimal genome assembly via sparse read-overlap graphs
Ilan Shomorony and Thomas Courtade. Information-optimal genome assembly via sparse read-overlap graphs. Bioinformatics, 32(17):i494–i502, 2016
2016
-
[26]
Wick, Louise M
Ryan R. Wick, Louise M. Judd, Claire L. Gorrie, and Kathryn E. Holt. Unicycler: Resolving bacterial genome assemblies from short and long sequencing reads.PLoS Computational Biology, 2017
2017
-
[27]
Genome assembly using quantum and quantum-inspired annealing.Scientific Reports, 11(1):13183, June 2021
A S Boev, A S Rakitko, S R Usmanov, A N Kobzeva, I V Popov, V V Ilinsky, E O Kiktenko, and A K Fedorov. Genome assembly using quantum and quantum-inspired annealing.Scientific Reports, 11(1):13183, June 2021
2021
-
[28]
Sarkar et al
S. Sarkar et al. Quaser: Quantum accelerated de novo sequence reconstruction.PLOS ONE, 2021. QUBO-based quantum assembly pipeline with annealing and quantum-inspired optimizers
2021
-
[29]
Quantum annealing in the transverse ising model.Physical Review E, 58(5):5355–5363, 1998
Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model.Physical Review E, 58(5):5355–5363, 1998
1998
-
[30]
Acceler- ating de novo genome assembly via quantum-assisted graph optimization with bitstring recovery, 01 2026
Jaya Pamidimukkala, Himanshu Sahu, Ashwini Kannan, Janani Ananthanarayanan, and Sanjib Senapati. Acceler- ating de novo genome assembly via quantum-assisted graph optimization with bitstring recovery, 01 2026
2026
-
[31]
Local search heuristics for quadratic unconstrained binary optimization (QUBO).Journal of Heuristics, 13(2):99–132, April 2007
Endre Boros, Peter L Hammer, and Gabriel Tavares. Local search heuristics for quadratic unconstrained binary optimization (QUBO).Journal of Heuristics, 13(2):99–132, April 2007
2007
-
[32]
Analyzing quadratic unconstrained binary optimization problems via multi- commodity flows.Discrete Appl
Di Wang and Robert D Kleinberg. Analyzing quadratic unconstrained binary optimization problems via multi- commodity flows.Discrete Appl. Math., 157(18):3746–3753, November 2009. 16 Sankar et al
2009
-
[33]
Quantum annealing initialization of the quantum approximate optimization algorithm.Quantum, 5(491):491, July 2021
Stefan H Sack and Maksym Serbyn. Quantum annealing initialization of the quantum approximate optimization algorithm.Quantum, 5(491):491, July 2021
2021
-
[34]
Quadratic unconstrained binary optimization (qubo)
Alejandro Montanez. Quadratic unconstrained binary optimization (qubo). https://pennylane.ai/qml/ demos/tutorial_QUBO, 02 2024. Date Accessed: 2025-07-05
2024
-
[35]
Openqaoa – an sdk for qaoa, 2022
Vishal Sharma, Nur Shahidee Bin Saharan, Shao-Hen Chiew, Ezequiel Ignacio Rodríguez Chiacchio, Leonardo Disilvestro, Tommaso Federico Demarie, and Ewan Munro. Openqaoa – an sdk for qaoa, 2022
2022
-
[36]
Joblib: running python functions as pipeline jobs, 2020
Joblib Development Team. Joblib: running python functions as pipeline jobs, 2020
2020
-
[37]
dwave-ocean-sdk Version 8.4.0
D-wave systems inc. dwave-ocean-sdk Version 8.4.0. Software, 2025
2025
-
[38]
Nucleotide sequence of bacteriophage phi X174 DNA.Nature, 265(5596):687–695, February 1977
F Sanger, G M Air, B G Barrell, N L Brown, A R Coulson, C A Fiddes, C A Hutchison, P M Slocombe, and M Smith. Nucleotide sequence of bacteriophage phi X174 DNA.Nature, 265(5596):687–695, February 1977
1977
-
[39]
Angly, Dana Willner, Forest Rohwer, Philip Hugenholtz, and Gene W
Florent E. Angly, Dana Willner, Forest Rohwer, Philip Hugenholtz, and Gene W. Tyson. Grinder: a versatile amplicon and shotgun sequence simulator.Nucleic Acids Research, 40(12):e94–e94, 07 2012
2012
-
[40]
gaftools: a toolkit for analyzing and manipulating pangenome alignments, 12 2024
Samarendra Pani, Fawaz Dabbaghie, Tobias Marschall, and Arda Soylev. gaftools: a toolkit for analyzing and manipulating pangenome alignments, 12 2024
2024
-
[41]
Minimap2: pairwise alignment for nucleotide sequences.Bioinformatics, 2018
Heng Li. Minimap2: pairwise alignment for nucleotide sequences.Bioinformatics, 2018
2018
-
[42]
Fast and accurate de novo genome assembly from long uncorrected reads.Genome Res., 27(5):737–746, May 2017
Robert Vaser, Ivan Sovi´c, Niranjan Nagarajan, and Mile Šiki´c. Fast and accurate de novo genome assembly from long uncorrected reads.Genome Res., 27(5):737–746, May 2017
2017
-
[43]
Optimizing the optimizer: decomposition techniques for quantum annealing.Quantum Machine Intelligence, 3(1):10, 2021
Gideon Bass, Maxwell Henderson, Joshua Heath, and Joseph Dulny. Optimizing the optimizer: decomposition techniques for quantum annealing.Quantum Machine Intelligence, 3(1):10, 2021
2021
- [44]
-
[45]
Minhui Gou, Zeyang Li, Hong-Ze Xu, et al. Hierarchical quantum optimization via backbone-driven problem decomposition.arXiv preprint arXiv:2504.09575, 2025
-
[46]
Yuichiro Minato. Two-step qaoa: Enhancing quantum optimization by decomposing one-hot constraints in qubo formulations.arXiv preprint arXiv:2408.05383, 2024
-
[47]
Globally optimizing qaoa circuit depth for constrained optimization problems.Algorithms, 14(10):294, 2021
Rebekah Herrman, Lorna Treffert, James Ostrowski, et al. Globally optimizing qaoa circuit depth for constrained optimization problems.Algorithms, 14(10):294, 2021
2021
-
[48]
Performance of quantum approximate optimization with quantum error detection.Communications Physics, 8:217, 2025
Zichang He, David Amaro, Ruslan Shaydulin, et al. Performance of quantum approximate optimization with quantum error detection.Communications Physics, 8:217, 2025. 17
2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.