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

Journal of the Physical Society of Japan

Graph Partitioning Based on Pair Interaction Energy Using Quantum Annealer

Takako Mashiko, Yuzo Otomo, Ikumi Kondo, Masayuki Ohzeki

Published Jul 28, 2026• 0 citations
Publisher
DOI
10.7566/jpsj.95.095001

Related papers

Graph comparison via nonlinear quantum search

Mitchell Chiew, K. de Lacy, Chao‐Hua Yu +2 more

arXiv:1810.01647•Quantum Information Processing•Aug 20, 2019•10 citations

Graph Partitioning using Quantum Annealing on the D-Wave System

Hayato Ushijima‐Mwesigwa, Christian F. A. Negre, Susan M. Mniszewski

Graph partitioning (GP) applications are ubiquitous throughout mathematics, computer science, chemistry, physics, bio-science, machine learning, and complex systems. Post Moore's era supercomputing has provided us an opportunity to explore new approaches for traditional graph algorithms on quantum computing architectures. In this work, we explore graph partitioning using quantum annealing on the D-Wave 2X machine. Motivated by a recently proposed graph-based electronic structure theory applied to quantum molecular dynamics (QMD) simulations, graph partitioning is used for reducing the calculation of the density matrix into smaller subsystems rendering the calculation more computationally efficient. Unconstrained graph partitioning as community clustering based on the modularity metric can be naturally mapped into the Hamiltonian of the quantum annealer. On the other hand, when constraints are imposed for partitioning into equal parts and minimizing the number of cut edges between parts, a quadratic unconstrained binary optimization (QUBO) reformulation is required. This reformulation may employ the graph complement to fit the problem in the Chimera graph of the quantum annealer. Partitioning into 2 parts and k parts concurrently for arbitrary k are demonstrated with benchmark graphs, random graphs, and small material system density matrix based graphs. Results for graph partitioning using quantum and hybrid classical-quantum approaches are shown to be comparable to current "state of the art" methods and sometimes better.

arXiv:1705.03082•Nov 3, 2017•200 citations

Distinguishing graphs with a quantum annealer using susceptibility measurements

Matthew Wittmann, Itay Hen, A. P. Young

Bulletin of the American Physical Society•Jan 1, 2014•0 citations

Quantum-Inspired Optimization of Graph Partitioning Algorithms

Jincheng Zhang

Graph partitioning is a fundamental problem in various fields, including computer graphics, high-performance computing, and network design. Traditional graph partitioning algorithms often suffer from high computational complexity, particularly when dealing with large and complex graphs. This research investigates the potential of quantum-inspired optimization techniques, specifically leveraging concepts from quantum annealing, to accelerate the graph partitioning process. We formulate the graph partitioning problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, allowing us to simulate the behavior of a quantum annealer on classical hardware. The core of our approach involves mapping the graph's connectivity structure onto a QUBO, representing nodes as binary variables and edges as constraints. By exploiting the inherent parallelism of quantum annealing, we aim to find optimal or near-optimal partitions significantly faster than conventional methods. The results demonstrate the feasibility and potential advantages of this quantum-inspired strategy for graph partitioning, offering a promising direction for tackling computationally intensive graph problems.

•Sep 5, 2026•0 citations

Graph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer

Eugenio Cocchi, Edoardo Tignone, Davide Vodola

We demonstrate that a quantum annealer can be used to solve the NP-complete problem of graph partitioning into subgraphs containing Hamiltonian cycles of constrained length. We present a method to find a partition of a given directed graph into Hamiltonian subgraphs with three or more vertices, called vertex 3-cycle cover. We formulate the problem as a quadratic unconstrained binary optimisation and run it on a D-Wave Advantage quantum annealer. We test our method on synthetic graphs constructed by adding a number of random edges to a set of disjoint cycles. We show that the probability of solution is independent of the cycle length, and a solution is found for graphs up to 4000 vertices and 5200 edges, close to the number of physical working qubits available on the quantum annealer.

arXiv:2104.09503•Apr 18, 2021•4 citations

Quantum annealing for combinatorial clustering

Vaibhaw Kumar, Gideon Bass, Casey Tomlin +1 more

arXiv:1708.05753•Quantum Information Processing•Jan 12, 2018•111 citations
Graph partitioning (GP) applications are ubiquitous throughout mathematics, computer science, chemistry, physics, bio-science, machine learning, and complex systems. Post Moore's era supercomputing has provided us an opportunity to explore new approaches for traditional graph algorithms on quantum computing architectures. In this work, we explore graph partitioning using quantum annealing on the D-Wave 2X machine. Motivated by a recently proposed graph-based electronic structure theory applied to quantum molecular dynamics (QMD) simulations, graph partitioning is used for reducing the calculation of the density matrix into smaller subsystems rendering the calculation more computationally efficient. Unconstrained graph partitioning as community clustering based on the modularity metric can be naturally mapped into the Hamiltonian of the quantum annealer. On the other hand, when constraints are imposed for partitioning into equal parts and minimizing the number of cut edges between parts, a quadratic unconstrained binary optimization (QUBO) reformulation is required. This reformulation may employ the graph complement to fit the problem in the Chimera graph of the quantum annealer. Partitioning into 2 parts and k parts concurrently for arbitrary k are demonstrated with benchmark graphs, random graphs, and small material system density matrix based graphs. Results for graph partitioning using quantum and hybrid classical-quantum approaches are shown to be comparable to current "state of the art" methods and sometimes better.
Graph partitioning is a fundamental problem in various fields, including computer graphics, high-performance computing, and network design. Traditional graph partitioning algorithms often suffer from high computational complexity, particularly when dealing with large and complex graphs. This research investigates the potential of quantum-inspired optimization techniques, specifically leveraging concepts from quantum annealing, to accelerate the graph partitioning process. We formulate the graph partitioning problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, allowing us to simulate the behavior of a quantum annealer on classical hardware. The core of our approach involves mapping the graph's connectivity structure onto a QUBO, representing nodes as binary variables and edges as constraints. By exploiting the inherent parallelism of quantum annealing, we aim to find optimal or near-optimal partitions significantly faster than conventional methods. The results demonstrate the feasibility and potential advantages of this quantum-inspired strategy for graph partitioning, offering a promising direction for tackling computationally intensive graph problems.
We demonstrate that a quantum annealer can be used to solve the NP-complete problem of graph partitioning into subgraphs containing Hamiltonian cycles of constrained length. We present a method to find a partition of a given directed graph into Hamiltonian subgraphs with three or more vertices, called vertex 3-cycle cover. We formulate the problem as a quadratic unconstrained binary optimisation and run it on a D-Wave Advantage quantum annealer. We test our method on synthetic graphs constructed by adding a number of random edges to a set of disjoint cycles. We show that the probability of solution is independent of the cycle length, and a solution is found for graphs up to 4000 vertices and 5200 edges, close to the number of physical working qubits available on the quantum annealer.