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

arXiv:2307.08371 · Journal of Graph Algorithms and Applications

Quantum Graph Drawing

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista

Published May 20, 2025• 2 citations
arXivHTMLPDF

Abstract

In this paper, we initiate the study of quantum algorithms in the Graph Drawing research area. We focus on two foundational drawing standards: 2-level drawings and book layouts. Concerning $2$-level drawings, we consider the problems of obtaining drawings with the minimum number of crossings, $k$-planar drawings, quasi-planar drawings, and the problem of removing the minimum number of edges to obtain a $2$-level planar graph. Concerning book layouts, we consider the problems of obtaining $1$-page book layouts with the minimum number of crossings, book embeddings with the minimum number of pages, and the problem of removing the minimum number of edges to obtain an outerplanar graph. We explore both the quantum circuit and the quantum annealing models of computation. In the quantum circuit model, we provide an algorithmic framework based on Grover's quantum search, which allows us to obtain, ignoring polynomial terms, a quadratic speedup on the best known classical exact algorithms for all the considered problems. In the quantum annealing model, we perform experiments on the quantum processing unit provided by D-Wave, focusing on the classical $2$-level crossing minimization problem, demonstrating that quantum annealing is competitive with respect to classical algorithms.

DOI
10.7155/jgaa.v29i2.3039

Related papers

Quantum algorithms and the maximum clique problem in graphs

Matheus Augusto Condé Dias

Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.

•Sep 14, 2022•0 citations

A Quantum Framework for K Coloring of Graphs

Lord Sen, Shyamapada Mukherjee

Graph coloring is a well-known NP-complete problem with applications in scheduling, register allocation, frequency assignment, and network optimization. Quantum computing offers the potential for polynomial or even super-polynomial speedups in certain problem instances, yet practical quantum graph coloring methods must carefully balance qubit resources, circuit depth, and constraint enforcement. We proposed a solver agnostic quantum framework for $K$-coloring. Along with a novel encoding and efficient constraint implementation for its exact coloring exploiting Grover search and almost optimal coloring by the Quantum Approximate Optimization Algorithm \emph{(QAOA)}, and \emph{Quantum Annealing}. Unlike using $O(NK)$ qubits as in \emph{SOTA}, we reduced the qubit requirements to $O(N \log_2 K)$, along with optimized comparator circuits enforcing adjacency constraints. Further symmetry-based graph reduction is incorporated as an optional preprocessing step to further reduce the instance size before quantum execution.

quant-pharXiv:2609.32348•International Conference on Computational Intelligence and Communication Networks (CICN)•Sep 29, 2026•0 citations

Quantum Tutte Embeddings

Shion Fukuzawa, Michael T. Goodrich, Sandy Irani

Using the framework of Tutte embeddings, we begin an exploration of \emph{quantum graph drawing}, which uses quantum computers to visualize graphs. The main contributions of this paper include formulating a model for quantum graph drawing, describing how to create a graph-drawing quantum circuit from a given graph, and showing how a Tutte embedding can be calculated as a quantum state in this circuit that can then be sampled to extract the embedding. To evaluate the complexity of our quantum Tutte embedding circuits, we compare them to theoretical bounds established in the classical computing setting derived from a well-known classical algorithm for solving the types of linear systems that arise from Tutte embeddings. We also present empirical results obtained from experimental quantum simulations.

arXiv:2307.08851•Jul 17, 2023•1 citation

A Quantum-Classical Approach to Solve the Graph Colouring Problem with Minimum Colours

Prem Shanker Dwivedi, Amit Biswas, Indu Dohare

Abstract Graph colouring with minimum colours is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph colouring problem with the minimum number of colours. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for exponential speed up on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum-classical method for solving the graph colouring problem with guaranteed correctness. The proposed method is inspired by Grover’s quantum search algorithm, the Clifford circuit, and the classical binary search algorithm. Here, Grover’s algorithm helps to achieve a quadratic speed up, Clifford circuit helps to mitigate the errors, and binary search helps to find the chromatic number with guaranteed correctness in polynomial time. We also conducted several experiments to evaluate the proposed method's performance and correctness, and the experimental results corroborate our claims regarding the proposed method. Additionally, a mathematical analysis is performed to assess its time and qubit complexities, and to compare its efficiency with existing methods.

•Oct 17, 2025•0 citations

Quantum Computing for Graph Partitioning with Optimal Speedup

Jincheng Zhang

Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.

•Sep 5, 2026•0 citations

Quantum algorithms for one-sided crossing minimization

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista

We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an n -vertex bipartite graph G = ( U , V , E ⊆ U × V ) , a 2 -level drawing ( π U , π V ) of G is described by a linear ordering π U : U ↔ { 1 , … , | U | } of U and linear ordering π V : V ↔ { 1 , … , | V | } of V . For a fixed linear ordering π U of U , the OSCM problem seeks to find a linear ordering π V of V that yields a 2-level drawing ( π U , π V ) of G with the minimum number of edge crossings. We show that OSCM can be viewed as a set problem over V amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [ Quantum Speedups for Exponential-Time Dynamic Programming Algorithms . SODA 2019] to devise a QRAM-based algorithm that solves OSCM in ⁎ O ⁎ ( 1.728 n ) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in ⁎ O ⁎ ( 2 n ) time and polynomial space.

arXiv:2409.01942•Theoretical Computer Science•Jun 20, 2025•1 citation
In this paper, we initiate the study of quantum algorithms in the Graph Drawing research area. We focus on two foundational drawing standards: 2-level drawings and book layouts. Concerning 222-level drawings, we consider the problems of obtaining drawings with the minimum number of crossings, kkk-planar drawings, quasi-planar drawings, and the problem of removing the minimum number of edges to obtain a 222-level planar graph. Concerning book layouts, we consider the problems of obtaining 111-page book layouts with the minimum number of crossings, book embeddings with the minimum number of pages, and the problem of removing the minimum number of edges to obtain an outerplanar graph. We explore both the quantum circuit and the quantum annealing models of computation. In the quantum circuit model, we provide an algorithmic framework based on Grover's quantum search, which allows us to obtain, ignoring polynomial terms, a quadratic speedup on the best known classical exact algorithms for all the considered problems. In the quantum annealing model, we perform experiments on the quantum processing unit provided by D-Wave, focusing on the classical 222-level crossing minimization problem, demonstrating that quantum annealing is competitive with respect to classical algorithms.
Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.
Graph coloring is a well-known NP-complete problem with applications in scheduling, register allocation, frequency assignment, and network optimization. Quantum computing offers the potential for polynomial or even super-polynomial speedups in certain problem instances, yet practical quantum graph coloring methods must carefully balance qubit resources, circuit depth, and constraint enforcement. We proposed a solver agnostic quantum framework for KKK-coloring. Along with a novel encoding and efficient constraint implementation for its exact coloring exploiting Grover search and almost optimal coloring by the Quantum Approximate Optimization Algorithm \emph{(QAOA)}, and \emph{Quantum Annealing}. Unlike using O(NK)O(NK)O(NK) qubits as in \emph{SOTA}, we reduced the qubit requirements to O(Nlog⁡2K)O(N \log_2 K)O(Nlog2​K), along with optimized comparator circuits enforcing adjacency constraints. Further symmetry-based graph reduction is incorporated as an optional preprocessing step to further reduce the instance size before quantum execution.
Using the framework of Tutte embeddings, we begin an exploration of \emph{quantum graph drawing}, which uses quantum computers to visualize graphs. The main contributions of this paper include formulating a model for quantum graph drawing, describing how to create a graph-drawing quantum circuit from a given graph, and showing how a Tutte embedding can be calculated as a quantum state in this circuit that can then be sampled to extract the embedding. To evaluate the complexity of our quantum Tutte embedding circuits, we compare them to theoretical bounds established in the classical computing setting derived from a well-known classical algorithm for solving the types of linear systems that arise from Tutte embeddings. We also present empirical results obtained from experimental quantum simulations.
Abstract Graph colouring with minimum colours is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph colouring problem with the minimum number of colours. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for exponential speed up on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum-classical method for solving the graph colouring problem with guaranteed correctness. The proposed method is inspired by Grover’s quantum search algorithm, the Clifford circuit, and the classical binary search algorithm. Here, Grover’s algorithm helps to achieve a quadratic speed up, Clifford circuit helps to mitigate the errors, and binary search helps to find the chromatic number with guaranteed correctness in polynomial time. We also conducted several experiments to evaluate the proposed method's performance and correctness, and the experimental results corroborate our claims regarding the proposed method. Additionally, a mathematical analysis is performed to assess its time and qubit complexities, and to compare its efficiency with existing methods.
Graph partitioning is a fundamental problem in computer science with applications in diverse fields like network design, compiler optimization, and data analysis. Traditional algorithms for graph partitioning often suffer from computational complexity, particularly when dealing with large graphs. This paper explores the potential of utilizing quantum computing to accelerate graph partitioning. Specifically, we investigate the application of Grover's algorithm, a quantum search algorithm, to the problem. Our core claim is that by leveraging the superposition and interference capabilities inherent in quantum mechanics, a quantum solution can achieve a provable speedup compared to classical approaches. We present a theoretical framework outlining the algorithm's operation and derive the expected speedup. The key mathematical formulation involves representing the graph partitioning problem as an unstructured search problem amenable to Grover's algorithm. We define the problem as minimizing the cut size, represented by the objective function: *f(S) = Σi∈S Σj∈Sc d(i, j)* where *S* is a subset of vertices, *Sc* is the complement of *S* in the graph, and *d(i, j)* is the shortest path distance between vertices *i* and *j*. The algorithm then constructs a quantum oracle that maps the problem state to a superposition of all possible partitions. Grover's algorithm is then applied to amplify the amplitude of the solution state, resulting in a high probability of finding an optimal or near-optimal partition. The speedup is directly proportional to the square root of the number of iterations performed by Grover's algorithm, which is influenced by the problem size and the quality of the oracle. We analyze the complexity of the quantum algorithm and compare it to the complexity of the best-known classical algorithms, demonstrating a potential for significant speedup. Further research will focus on optimizing the oracle construction and exploring other quantum algorithms suitable for graph partitioning.
We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an n -vertex bipartite graph G = ( U , V , E ⊆ U × V ) , a 2 -level drawing ( π U , π V ) of G is described by a linear ordering π U : U ↔ { 1 , … , | U | } of U and linear ordering π V : V ↔ { 1 , … , | V | } of V . For a fixed linear ordering π U of U , the OSCM problem seeks to find a linear ordering π V of V that yields a 2-level drawing ( π U , π V ) of G with the minimum number of edge crossings. We show that OSCM can be viewed as a set problem over V amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [ Quantum Speedups for Exponential-Time Dynamic Programming Algorithms . SODA 2019] to devise a QRAM-based algorithm that solves OSCM in ⁎ O ⁎ ( 1.728 n ) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in ⁎ O ⁎ ( 2 n ) time and polynomial space.