Quantum Information & Computation
Volume 25, Issue 6
RESEARCH ARTICLE Open access

Random-Projector Quantum Diagnostics of Ramsey Numbers and A Prime-factor Heuristic for R (5, 5) = 45

Fabrizio Tamburini

Author affiliations
  • Fabrizio Tamburini1
  1. Rotonium – Quantum Computing, Le Village by CA, Piazza G. Zanellato, 23, Padova PD, Italy

pp. 739-772 · 10.2478/qic-2025-0039

Read PDF View on Reference Global
On this page

Abstract

We introduce a statistical framework for estimating Ramsey numbers by embedding two-color Ramsey instances into a ℤ2 × ℤ2 -graded Majorana algebra. This approach replaces brute-force enumeration with two randomized spectral diagnostics applied to operators of a given dimension d associated with Ramsey numbers: a linear projector Plin and an exponential map Pexp (α), suitable for both classical and quantum computation. In the diagonal case, both diagnostics identify R(5, 5) at n = 45. The quantum realizations act on a reduced module and therefore require only five data qubits plus a few ancillas via block-encoding/qubitization for R(5, 5) = 45, in stark contrast to the (n2)≈103\left(\begin{matrix} n \\ 2 \\\end{matrix} \right) \approx {10^3} logical qubits demanded by direct edge encodings. We also provide few-qubit estimates for R(6, 6) and R(7, 7), and propose a simple “prime-sequence” consistency heuristic that connects R(5, 5) = 45 to constrained diagonal growth. Our method echoes Erdős’s probabilistic paradigm, emphasizing randomized arguments rather than explicit colorings, and parallels the classical coin-flip approach to Ramsey bounds. Finally, we discuss potential applications of this framework to machine learning with a limited number of qubits.
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum algorithms
  • ramsey number R(5, 5)
  • random projectors

Suggested citation

Fabrizio Tamburini (2025). Random-Projector Quantum Diagnostics of Ramsey Numbers and A Prime-factor Heuristic for R (5, 5) = 45. Quantum Information & Computation, 25(6), 739-772. https://doi.org/10.2478/qic-2025-0039

Download BibTeX

References (33)

  1. Frank P. Ramsey (1930). On a problem of formal logic. Proceedings of the London Mathematical Society, 30, 264–286.DOI: 10.1112/plms/s2-30.1.264Google Scholar
  2. Geoffrey Exoo (1989). A lower bound for r (5, 5). Journal of Graph Theory, 13, 97–98.DOI: 10.1002/jgt.3190130113Google Scholar
  3. Vigleik Angeltveit and Brendan D. McKay (2024). r(5, 5) ≤ 46 (2024). arXiv:2409.15709.Google Scholar
  4. Vigleik Angeltveit and Brendan D. McKay (2018). r (5, 5) ≤ 48. Journal of Graph Theory, 89, 5–13.DOI: 10.1002/jgt.22235Google Scholar
  5. Ronald L. Graham and Joel H. Spencer (1990). Ramsey theory. Scientific American, 263, 112–117.DOI: 10.1038/scientificamerican0790-112Google Scholar
  6. Richard W. Hamming (1950). Error detecting and error correcting codes. The Bell System Technical Journal, 29, 147–160.DOI: 10.1002/j.1538-7305.1950.tb00463.xGoogle Scholar
  7. Noga Alon and Joel H. Spencer (2008). The probabilistic method. Wiley-Interscience. Hoboken, NJ,. 3 edition.DOI: 10.1002/9780470277331Google Scholar
  8. Ronald L. Graham, Bruce L. Rothschild and Joel H. Spencer (1990). Ramsey theory. Wiley-Interscience. NewYork, 2 edition.DOI: 10.1038/scientificamerican0790-112Google Scholar
  9. Andrew M. Childs, Eddie Schoute and Cem M. Unsal (2019). Circuit transformations for quantum architectures. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:24. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. arXiv:1902.09102.Google Scholar
  10. Fabrizio Tamburini, Nicolò Leone, Marco Sanna and Roberto Siagri (2025). Graded paraparticle algebra of majorana fields for multidimensional quantum computing with structured light. arXiv:2505.23232.DOI: 10.1103/kbkl-9m9lGoogle Scholar
  11. Stanisław P. Radziszowski (2021). Small ramsey numbers. Electronic Journal of Combinatorics, DS1.Google Scholar
  12. Jan Goedgebeur and Steven Van Overberghe (2021). New bounds for ramsey numbers r(kk – e, kℓ – e). arXiv:2107.04460.Google Scholar
  13. Hefeng Wang (2016). Determining ramsey numbers on a quantum computer. Physical Review A, 93, 032301.DOI: 10.1103/PhysRevA.93.032301Google Scholar
  14. Frank Gaitan and Lane Clark (2012). Ramsey numbers and adiabatic quantum computing. Physical Review Letters, 108,010501.DOI: 10.1103/PhysRevLett.108.010501Google Scholar
  15. Paul Erdős (1947). Some remarks on the theory of graphs. Bulletin of the American Mathematical Society, 53, 292–294.DOI: 10.1090/S0002-9904-1947-08785-1Google Scholar
  16. Brendan D. McKay and Stanisław P. Radziszowski (1995). r (4, 5) = 25. Journal of Graph Theory, 19, 309–322.DOI: 10.1002/jgt.3190190304Google Scholar
  17. H. S. Green (1953). A generalized method of field quantization. Physical Review, 90, 270–273.DOI: 10.1103/PhysRev.90.270Google Scholar
  18. A. Yu. Kitaev (2001). Unpaired majorana fermions in quantum wires. Physics-Uspekhi, 44, s131–s136.DOI: 10.1070/1063-7869/44/10S/S29Google Scholar
  19. P. Erdős and L. Lovász (1975). Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado, and V. T. Sós, editors, Infinite and Finite Sets. Volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 609–627. North-Holland, Amsterdam.Google Scholar
  20. Svante Janson, Tomasz Łuczak and Andrzej Rucinski (2000). Random graphs. Wiley Series in Discrete Mathematics and Optimization. Wiley-Interscience. New York. url: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118032718.DOI: 10.1002/9781118032718Google Scholar
  21. Svante Janson (1990). Poisson approximation for large deviations. Random Structures & Algorithms, 1, 221–229.DOI: 10.1002/rsa.3240010209Google Scholar
  22. Neil J. Calkin, Paul Erdős and Craig A. Tovey (1997). New ramsey bounds from cyclic graphs of prime order. SIAM Journal on Discrete Mathematics, 10, 381–387.DOI: 10.1137/S0895480196298378Google Scholar
  23. Rudolf Mathon (1987). Lower bounds for ramsey numbers and association schemes. Journal of Combinatorial Theory, Series B, 42, 122–127.DOI: 10.1016/0095-8956(87)90067-0Google Scholar
  24. Xiaodong Xu and Stanisław P. Radziszowski (2009). An improvement to mathon’s cyclotomic ramsey colorings. Electronic Journal of Combinatorics 16, N1.DOI: 10.37236/239Google Scholar
  25. R. E. A. C. Paley (1933). On orthogonal matrices. Journal of Mathematics and Physics, 12, 311–320.DOI: 10.1002/sapm1933121311Google Scholar
  26. V. I. Oseledets (1968). A multiplicative ergodic theorem: Characteristic lyapunov exponents of dynamical systems. Trudy Moskovskogo Matematicheskogo Obshchestva, 19, 179–210.Google Scholar
  27. Dermot McCarthy and Chris Monico (2025). A mathon-type construction for digraphs and improved lower bounds for ramsey numbers. Electronic Journal of Combinatorics, 32, P2.42.DOI: 10.37236/13294Google Scholar
  28. Geoffrey Exoo. “Paley graph data: Clique/chromatic numbers and ramsey bounds”. https://cs.indstate.edu/ge/Paley/index.html. Accessed Aug. 2025. Includes the Paley(797) witness used for R(10, 10) ≥ 798.Google Scholar
  29. OEIS Foundation Inc (2025). The on-line encyclopedia of integer sequences, sequence a212954. https://oeis.org/A212954. accessed 2025-08-19.Google Scholar
  30. David Cariolaro, Gianfranco Cariolaro, Uwe Schauz and Xiaogang Sun (2014). The list-chromatic index of k6. Discrete Mathematics, 322, 15–18.DOI: 10.1016/j.disc.2013.12.022Google Scholar
  31. David Cariolaro (2007). On the ramsey number r (3, 6). Australasian Journal of Combinatorics, 37, 301–304.Google Scholar
  32. Ian T. Jolliffe and Jorge Cadima (2016). Principal component analysis: A review and recent developments. Philosophical Transactions of the Royal Society A, 374, 20150202.DOI: 10.1098/rsta.2015.0202Google Scholar
  33. Sanjoy Dasgupta and Anupam Gupta (1999). An elementary proof of the johnson–lindenstrauss lemma. Technical Report TR-99-006. International Computer Science InstituteBerkeley, CA.Google Scholar