Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Springer eBooks

The Bipartite QUBO

Abraham P. Punnen

Published Jan 1, 2022• 1 citation
Publisher
DOI
10.1007/978-3-031-04520-2_10

Related papers

Single entanglement connection architecture between multi-layer bipartite hardware efficient ansatz

Shikun Zhang, Zheng Qin, Zhou Yang +3 more

Abstract Variational quantum algorithms are among the most promising algorithms to achieve quantum advantages in the noisy intermediate-scale quantum (NISQ) era. One important challenge in implementing such algorithms is to construct an effective parameterized quantum circuit (also called an ansatz). In this work, we propose a single entanglement connection architecture (SECA) for a bipartite hardware efficient ansatz (HEA) by balancing its expressibility, entangling capability, and trainability. Numerical simulations with a one-dimensional Heisenberg model and quadratic unconstrained binary optimization (QUBO) issues were conducted. Our results indicate the superiority of SECA over the common full entanglement connection architecture in terms of computational performance. Furthermore, combining SECA with gate-cutting technology to construct distributed quantum computation (DQC) can efficiently expand the size of NISQ devices under low overhead. We also demonstrated the effectiveness and scalability of the DQC scheme. Our study is a useful indication for understanding the characteristics associated with an effective training circuit.

arXiv:2307.12323•New Journal of Physics•Jul 1, 2024•9 citations

The Random QUBO

Karthik Natarajan

Springer eBooks•Jan 1, 2022•0 citations

QUANTA: A quantum annealing framework for species tree estimation using weighted quartet amalgamation

Niloy Kumar Mondal, Md. Shamsuzzoha Bayzid

Reconstructing species trees from genome-scale data is challenging due to pervasive gene tree discordance. Maximizing quartet consistency is a widely used approach for species tree inference from multi-locus data. Quartet amalgamation approaches, such as Quartet Fiduccia-Mattheyse (QFM) and Quartet MaxCut (QMC) families, have emerged as highly accurate quartet-based species tree inference techniques, but their reliance on computationally expensive classical bipartitioning heuristics, such as Fiduccia-Mattheyses (FM) and MaxCut, limits their scalability. Here, we introduce QUANTA, a quantum annealing-based quartet amalgamation method that, to our knowledge, represents the first quantum formulation of quartet-based approaches and the first species tree estimation method for multi-locus data that runs on real quantum hardware. At the core of QUANTA is a novel, general formulation of weighted quartet bipartitioning as a quadratic unconstrained binary optimization (QUBO) problem that enables quantum annealing to replace the classical bipartitioning strategies underlying the QFM and QMC families of methods. We prove that our formulation uses the minimum possible number of qubits to represent bipartitions and that its energy function correctly orders satisfied, deferred, and violated quartets for any positive penalty weights. We implemented QUANTA on real D-Wave quantum annealing hardware, and evaluated it on a wide range of simulated and biological datasets. QUANTA achieves accuracy comparable to the state-of-the-art methods, including ASTRAL and wQFM, under challenging evolutionary conditions. We also reanalyzed several biological datasets, including the avian phylogenomic dataset comprising 14,446 genes across 48 genomes, on which QUANTA reconstructed a species tree with a higher quartet score than wQFM. Remarkably, despite running on current noisy intermediate-scale quantum (NISQ) hardware, QUANTA's bipartition technique achieved 4100x speedup over the FM bipartitioning technique in wQFM on bipartition containing 90-200 taxa, while maintaining comparable tree accuracy. By establishing a theoretically grounded, hardware-independent quantum optimization framework for weighted quartet amalgamation, QUANTA opens a new direction for quantum-assisted phylogenomics and provides a foundation for increasingly scalable and accurate species tree estimation as quantum computing hardware advances. QUANTA is publicly available at https://github.com/QuitttCat/QUANTA-Phylogenomics.

•Nov 6, 2026•0 citations

On the State of QUBO Solving

Thorsten Koch, Daniel Rehfeldt, Yuji Shinano

Lecture notes in operations research•Jan 1, 2025•0 citations

Operational Quantum Annealers are Cursed by their Qubits Interconnection Topologies

Daniel Vert, Renaud Sirdey, Stéphane Louise

Recent experimental works have studied how the quantum annealing approach, as implemented in D-Wave devices, deals with pathological instances of the (polynomial) bipartite matching problem known to be hard for classical simulated annealing algorithms and shown that the quantum approach also performed rather poorly on such instances. In this paper, we investigate the extent to which the qubits interconnection topologies explains these latter experimental results. In particular, we provide evidences that the sparsity of these topologies which, as such, lead to QUBO problems of artificially inflated sizes can partly explain the aforementioned disappointing observations. Therefore, this paper hints that denser interconnection topologies are necessary to unleash the potential of the quantum annealing approach.

IEEE Computer Society Annual Symposium on VLSI•Jul 1, 2020•2 citations

Introduction to QUBO

Abraham P. Punnen

Springer eBooks•Jan 1, 2022•4 citations
Abstract Variational quantum algorithms are among the most promising algorithms to achieve quantum advantages in the noisy intermediate-scale quantum (NISQ) era. One important challenge in implementing such algorithms is to construct an effective parameterized quantum circuit (also called an ansatz). In this work, we propose a single entanglement connection architecture (SECA) for a bipartite hardware efficient ansatz (HEA) by balancing its expressibility, entangling capability, and trainability. Numerical simulations with a one-dimensional Heisenberg model and quadratic unconstrained binary optimization (QUBO) issues were conducted. Our results indicate the superiority of SECA over the common full entanglement connection architecture in terms of computational performance. Furthermore, combining SECA with gate-cutting technology to construct distributed quantum computation (DQC) can efficiently expand the size of NISQ devices under low overhead. We also demonstrated the effectiveness and scalability of the DQC scheme. Our study is a useful indication for understanding the characteristics associated with an effective training circuit.
Reconstructing species trees from genome-scale data is challenging due to pervasive gene tree discordance. Maximizing quartet consistency is a widely used approach for species tree inference from multi-locus data. Quartet amalgamation approaches, such as Quartet Fiduccia-Mattheyse (QFM) and Quartet MaxCut (QMC) families, have emerged as highly accurate quartet-based species tree inference techniques, but their reliance on computationally expensive classical bipartitioning heuristics, such as Fiduccia-Mattheyses (FM) and MaxCut, limits their scalability. Here, we introduce QUANTA, a quantum annealing-based quartet amalgamation method that, to our knowledge, represents the first quantum formulation of quartet-based approaches and the first species tree estimation method for multi-locus data that runs on real quantum hardware. At the core of QUANTA is a novel, general formulation of weighted quartet bipartitioning as a quadratic unconstrained binary optimization (QUBO) problem that enables quantum annealing to replace the classical bipartitioning strategies underlying the QFM and QMC families of methods. We prove that our formulation uses the minimum possible number of qubits to represent bipartitions and that its energy function correctly orders satisfied, deferred, and violated quartets for any positive penalty weights. We implemented QUANTA on real D-Wave quantum annealing hardware, and evaluated it on a wide range of simulated and biological datasets. QUANTA achieves accuracy comparable to the state-of-the-art methods, including ASTRAL and wQFM, under challenging evolutionary conditions. We also reanalyzed several biological datasets, including the avian phylogenomic dataset comprising 14,446 genes across 48 genomes, on which QUANTA reconstructed a species tree with a higher quartet score than wQFM. Remarkably, despite running on current noisy intermediate-scale quantum (NISQ) hardware, QUANTA's bipartition technique achieved 4100x speedup over the FM bipartitioning technique in wQFM on bipartition containing 90-200 taxa, while maintaining comparable tree accuracy. By establishing a theoretically grounded, hardware-independent quantum optimization framework for weighted quartet amalgamation, QUANTA opens a new direction for quantum-assisted phylogenomics and provides a foundation for increasingly scalable and accurate species tree estimation as quantum computing hardware advances. QUANTA is publicly available at https://github.com/QuitttCat/QUANTA-Phylogenomics.
Recent experimental works have studied how the quantum annealing approach, as implemented in D-Wave devices, deals with pathological instances of the (polynomial) bipartite matching problem known to be hard for classical simulated annealing algorithms and shown that the quantum approach also performed rather poorly on such instances. In this paper, we investigate the extent to which the qubits interconnection topologies explains these latter experimental results. In particular, we provide evidences that the sparsity of these topologies which, as such, lead to QUBO problems of artificially inflated sizes can partly explain the aforementioned disappointing observations. Therefore, this paper hints that denser interconnection topologies are necessary to unleash the potential of the quantum annealing approach.