Speaker
Description
Computing Ramsey numbers $R(k,l)=n$ involves finding the smallest graph of order $n$ that contains either a $k$-clique or an $l$-independent set under a two-coloring [1]. This presents a formidable computational challenge because the classical search space grows super-exponentially with the number of vertices, making the problem intractable.This work utilizes Quantum Optimization Algorithms on IBMQ hardware to address this complexity. The decision problem of determining if $R(k,l) > n$ is reformulated into a Quadratic Unconstrained Binary Optimization (QUBO) problem [2]. The associated Problem Hamiltonian, $H_P$, is constructed so that its ground state corresponds to the solution of the decision problem.We employ a variational quantum algorithm, a hybrid quantum-classical method implemented via the Qiskit framework and executed on utility-scale IBMQ architecture. While alternative quantum frameworks have investigated specific instances—such as solving $R(5,5)=45$ using Majorana-based algebra on a 5-qubit photonic quantum computer [3]—this study focuses on evaluating scalability. Having verified classical optimization benchmarks for small Ramsey numbers like $R(3,3)$, we investigate the scale-up performance and solution quality on utility-scale quantum processors. These findings aim to advance methods for solving combinatorial problems beyond the reach of conventional High-Performance Computing (HPC) resources.
[1] Bondy, J.A., and P. Erdös. “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.”, 2025. arXiv:2508.16699.
| Topic | Quantum variational circuits and their applications |
|---|---|
| Additional Topic | Hybrid quantum-classical approaches for learning and optimization |