Have a personal or library account? Click to login
Random-Projector Quantum Diagnostics of Ramsey Numbers and A Prime-factor Heuristic for R(5, 5) = 45 Cover

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

Quantum Information & Computation
Volume 25 (2025): Issue 6 (December 2025)
By: Fabrizio Tamburini  
Open Access
|Mar 2026

Figures & Tables

Figure 1.

Phase-estimation on the Hermitian dilation H (Eq. (23)) to estimate its extremal eigenphase(s), hence ρ(H)=‖A‖2\rho (H) = A{_2}. The “sig” (sign) qubit together with the data register realizes the 2d-dimensional space of the dilation; the PE register controls powers of e−itH. A local maximum of the extracted ‖A‖2A{_2} at the critical v complements the linear/exponential diagnostics.
Phase-estimation on the Hermitian dilation H (Eq. (23)) to estimate its extremal eigenphase(s), hence ρ(H)=‖A‖2\rho (H) = A{_2}. The “sig” (sign) qubit together with the data register realizes the 2d-dimensional space of the dilation; the PE register controls powers of e−itH. A local maximum of the extracted ‖A‖2A{_2} at the critical v complements the linear/exponential diagnostics.

Figure 2.

One-ancilla rank-1 block-encoding gadget Wj implementing the top-left block 12|uj〉〈vj|{1 \over 2}\left| {{u_j}} \right\rangle \langle {v_j}| (see Eq. (24)). The multiplexor applies Uj when the ancilla is |0〉 and Vj when it is |1〉. Composing these gadgets with a single selector/index register and oblivious amplitude amplification yields an α0–block-encoding of A/α0=∑jwj|uj〉〈vj|/α0A/{\alpha _0} = \sum\nolimits_j {{w_j}} \left| {{u_j}} \right\rangle \langle {v_j}|/{\alpha _0}.
One-ancilla rank-1 block-encoding gadget Wj implementing the top-left block 12|uj〉〈vj|{1 \over 2}\left| {{u_j}} \right\rangle \langle {v_j}| (see Eq. (24)). The multiplexor applies Uj when the ancilla is |0〉 and Vj when it is |1〉. Composing these gadgets with a single selector/index register and oblivious amplitude amplification yields an α0–block-encoding of A/α0=∑jwj|uj〉〈vj|/α0A/{\alpha _0} = \sum\nolimits_j {{w_j}} \left| {{u_j}} \right\rangle \langle {v_j}|/{\alpha _0}.

Figure 3.

Hadamard-test realization of the Hutchinson identity (Eq. (25)). A random |r〉 is prepared by a unitary 2-design C on the data register; U˜F{{\tilde U}_F} is a block-encoding of F (either F = Pexp (α) = e−aA or F = Plin). Averaging the ancilla’s 〈Z〉 over random |r〉 gives an unbiased estimate ofTr F/d; amplitude estimation can reduce shot complexity.
Hadamard-test realization of the Hutchinson identity (Eq. (25)). A random |r〉 is prepared by a unitary 2-design C on the data register; U˜F{{\tilde U}_F} is a block-encoding of F (either F = Pexp (α) = e−aA or F = Plin). Averaging the ancilla’s 〈Z〉 over random |r〉 gives an unbiased estimate ofTr F/d; amplitude estimation can reduce shot complexity.

Diagnostic values for the explicit 46-vertex coloring_ For comparison, the rightmost column reproduces the ensemble averages (the Angeltveit–McKay, AM–46, coloring [3]) reported earlier for generic n = 46 instances_

explicit AM-46bulk average (n = 46) Tab I
Tr Plin0.409 ± 0.0040.407
min Reλ Plin)–0.060–0.061
max |Imλ|0.0320.063
ReTrPexp+1.79 × 10−13+1.86 × 10−13

Estimate of the number of qubits required to calculate R(5, 5) with Grover-style algorithm_

nE(n)=(n2)E(n) = \left( \matrix{ n \cr 2 \cr} \right)Total qubits Q(n) (safe upper bound)
4444 · 43/2 = 946946 + 16 ≈ 962
4545 · 44/2 = 990990 + 16 ≈ 1006
4646 · 45/2 = 10351035 + 16 ≈ 1051

R(5, 5) under k ≤ 2n – 1 (n = 5): admissible and selected values as 𝒫k grows_

R(5, 5) kprime setadmissible integers in (43, 46]
3–5𝒫3–5 (11 and 23 absent)45 = 325
5–8𝒫5–8 (11 present)44 = 2211, 45 = 325
9(23 present)44, 45, 46 = 2·23

Prime–sparse extrapolation of the unknown diagonal values R(6, 6) and R(7, 7)_

Ramsey N.𝒫5𝒫6𝒫7𝒫8𝒫9𝒫10𝒫11𝒫12𝒫13
R(6, 6)108108117117115115115111111
R(7, 7)225216221209209209209209205

Upper bounds on Pmiss from Eq_ (A16) for the parameters used in our numerical study_

Surviving rank rMean hits kp = rk/dBound on Pmisslog10 Pmiss
14.171.2 × 10−1–0.9
28.334.0 × 10−2–1.4
416.673.7 × 10−3–2.4
625.003.4 × 10−4–3.5
833.333.0 × 10−5–4.5
1041.672.7 × 10−6–5.6
1250.002.5 × 10−7–6.6

Trace of exponential projector, real and imaginary TrPexp, linear projector TrPlin, Minimum real eigenvalue of linear projector, Lyapunov exponent λL for each n at α = 20, k = 100, for n = 45 reports the best values obtained with α = 40 and k = 400_ and slope of log10(Trace) vs_ {α}_ The symbol* = indicates a known limit solution for n = 5 used as test_

n43 *444546
TrPexp7.92 × 10−121.54 × 10−1210−289 ≈ 01.86 × 10−13
TrPlin0.2840.3600.4620.407
min Reλ–0.058–0.053–0.050–0.061
max Imλ±0.037±0.030±0.032±0.063
λL1.551.481.411.54
Slope–0.674–0.642–0.612–0.670

j_qic-2025-0039_tab_007

Coin-flip model↔Projector model
Indicator 1[mono-Kk]↔residual rank direction in M0
First moment 𝔼X↔𝔼 T(α), 𝔼 Tr Plin
Independence of edge colors↔i.i.d. isotropic vj
Counting (nk)\left( \matrix{ n \cr k \cr} \right) patterns↔k rank–1 probes k in d dimensions
𝔼X ≤ 1 threshold↔T(α) ↓ 0 and Pmiss ≪ 1
DOI: https://doi.org/10.2478/qic-2025-0039 | Journal eISSN: 3106-0544 | Journal ISSN: 1533-7146
Journal RSS Feed
Language: English
Page range: 739 - 772
Submitted on: Aug 25, 2025
|
Accepted on: Oct 30, 2025
|
Published on: Mar 9, 2026
Published by: Cerebration Science Publishing Co., Limited
In partnership with: Paradigm Publishing Services
Publication frequency: 1 issue per year
Keywords:
quantum algorithms,
ramsey number R(5, 5),
random projectors
Related subjects:
Physics,
Quantum physics,
Mathematics,
Applied mathematics,
Computer sciences,
Computer sciences in the humanities,
Computer sciences,
Computer sciences in natural sciences

© 2026 Fabrizio Tamburini, published by Cerebration Science Publishing Co., Limited
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Previous articleVolume 25 (2025): Issue 6 (December 2025)Next article