Speaker
Description
The computation of Ramsey Numbers in graph theory looks for the appearance
of order of a certain substructure in a graph of given size. Mathematically, the
calculation of a Ramsey Number R(k, l) = n is a two colouring problem that
finds the smallest graph of size n, that contains either a colouring of size k
or a different colouring of size l, [1]. This is a formidable computational challenge. Classical algorithms face a search space that grows super-exponentially
with the number of vertices, rendering the problem intractable. This abstract
presents an approach to utilizing Quantum Optimisation Algorithms to address
this complexity, with an experimental implementation targeting IBMQ quan-
tum hardware.
The following paper, [2], reformulates the problem of determining if R(k, l) > n
(i.e., if an n-vertex graph exists with no k-clique or l-independent set) into
a Quadratic Unconstrained Binary Optimisation (QUBO) problem. The as-
sociated Problem Hamiltonian, HP , is constructed such that its ground state
corresponds to a solution that satisfies our decision problem.
We employ the Variational Algorithm, a leading hybrid quantum-classical method.
The circuit is implemented using the Qiskit framework and executed on acces-
sible IBMQ systems. A key aspect of our work is the introduction of quantum
approaches in this field and execution on Utility scale IBMQ architecture.
To our knowledge, the following paper, [3], solves R(5, 5) = 45 with Majorana
based Algebra on a Photonic Quantum Computer, using only 5 qubits.
We have verified classical results for the computation of small, yet non-trivial,
Ramsey numbers, such as R(3, 3), by benchmarking the performance classical
optimization. We would like to investigate the scale-up performance and qual-
ity of results on Utility scale quantum computers. Our findings will contribute
to the knowledge of solving problems beyond the reach of conventional High
Performance Computing (HPC) resources.
[1] - Bondy, J.A., and P. Erd¨os. “Ramsey numbers for cycles in graphs.” Journal
of Combinatorial Theory, Series B, vol. 14, no. 1, 1973, pp. 46–54. Crossref,
https://doi.org/10.1016/S0095-8956(73)80005-X
[2] - Wang, Hefeng. “Determining Ramsey Numbers on a Quantum Computer.”
Physical Review A, vol. 93, no. 3, Mar. 2016. Crossref, https://doi.org/10.1103/physreva.93.032301
[3] - Tamburini, Fabrizio. “Random-projector quantum diagnostics of Ramsey
numbers and a prime-factor heuristic for R(5,5)=45.” arXiv, 2025. arXiv:2508.16699.
| Presenting Author | Shawal Kassim |
|---|---|
| Institute | University of the Witwatersrand |
