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:1510.01884 · Physical Review A

Determining Ramsey numbers on a quantum computer

Hefeng Wang

Published Mar 1, 2016• 7 citations
arXivHTMLPDF

Abstract

We present a quantum algorithm for computing the Ramsey numbers whose computational complexity grows superexponentially with the number of vertices of a graph on a classical computer. The problem is mapped to a decision problem on a quantum computer, and a probe qubit is coupled to a register that represents the problem and detects the energy levels of the problem Hamiltonian. The decision problem is solved by detecting the decay dynamics of the probe qubit.

DOI
10.1103/physreva.93.032301

Related papers

Ramsey Numbers and Adiabatic Quantum Computing

Frank Gaitan, Lane Clark

The graph-theoretic Ramsey numbers are notoriously difficult to calculate. In fact, for the two-color Ramsey numbers R(m,n) with m, n≥3, only nine are currently known. We present a quantum algorithm for the computation of the Ramsey numbers R(m,n). We show how the computation of R(m,n) can be mapped to a combinatorial optimization problem whose solution can be found using adiabatic quantum evolution. We numerically simulate this adiabatic quantum algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(2,s) for 5≤s≤7. We then discuss the algorithm's experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class quantum Merlin Arthur.

arXiv:1103.1345•Physical Review Letters•Jan 5, 2012•69 citations

Quantum algorithm for solving some discrete mathematical problems by probing their energy spectra

Hefeng Wang, Heng Fan, Fuli Li

When a probe qubit is coupled to a quantum register that represents a physical system, the probe qubit will exhibit a dynamical response only when it is resonant with a transition in the system. Using this principle, we propose a quantum algorithm for solving discrete mathematical problems based on the circuit model. Our algorithm has favorable scaling properties in solving some discrete mathematical problems.

arXiv:1206.4747•Physical Review A•Jan 6, 2014•3 citations

Quantum Algorithm for Solving an NP-Complete Problem

Hefeng Wang, Fuli Li

When a probe qubit is coupled to a quantum register that represents a physical system, the probe qubit will exhibit a dynamical response only when it is resonant with a transition in the system. Using this principle, we propose a quantum algorithm for solving discrete mathematical problems based on the circuit model. Our algorithm has favorable scaling properties in solving some discrete mathematical problems.

Bulletin of the American Physical Society•Jun 21, 2012•0 citations

A quantum–classical approach to solve the graph coloring problem with minimum colors

Prem Shanker Dwivedi, Abhinav Kumar, Amit Biswas +1 more

Abstract Graph coloring with minimum colors 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 coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup 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 coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.

Physica Scripta•Oct 9, 2026•0 citations

A Quantum Algorithm for the Sub-graph Isomorphism Problem

Nicola Mariella, Andrea Simonetto

We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.

arXiv:2111.09732•ACM Transactions on Quantum Computing•Oct 26, 2022•7 citations

Toward computing bounds for Ramsey numbers using quantum annealing

Joel E. Pion, Susan M. Mniszewski

Abstract Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.

arXiv:2311.04405•Quantum Information Processing•Jul 11, 2025•0 citations
We present a quantum algorithm for computing the Ramsey numbers whose computational complexity grows superexponentially with the number of vertices of a graph on a classical computer. The problem is mapped to a decision problem on a quantum computer, and a probe qubit is coupled to a register that represents the problem and detects the energy levels of the problem Hamiltonian. The decision problem is solved by detecting the decay dynamics of the probe qubit.
The graph-theoretic Ramsey numbers are notoriously difficult to calculate. In fact, for the two-color Ramsey numbers R(m,n) with m, n≥3, only nine are currently known. We present a quantum algorithm for the computation of the Ramsey numbers R(m,n). We show how the computation of R(m,n) can be mapped to a combinatorial optimization problem whose solution can be found using adiabatic quantum evolution. We numerically simulate this adiabatic quantum algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(2,s) for 5≤s≤7. We then discuss the algorithm's experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class quantum Merlin Arthur.
Abstract Graph coloring with minimum colors 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 coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup 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 coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.
We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.
Abstract Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.