Pith. sign in

REVIEW 3 major objections 5 minor 32 references

Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Pith's one-line read The paper proves that when the bridge weight equals M, a continuous-time quantum walk on the simplex of complete graphs reaches the marked vertex with probability 0.8 in O(sqrt(N)) time, giving the first analytical proof of optimal search o

desk verdict The w=M result is a real step forward, but the 'proof' has a perturbation-theory gap at the same order as the effect it computes; still worth refereeing. read the letter →

arxiv 2608.03777 v1 pith:MQGEJYGJ submitted 2026-08-04 quant-ph

classification quant-ph MSC 81P68 PACS 03.67.-a03.67.Ac
keywords continuous-timequantumwalkspatialsearchweightedgraphsimplexofcompletegraphstruncatedlatticedegenerateperturbationtheoryoptimalconnectivity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how fast a continuous-time quantum walk can find a marked vertex on the simplex of complete graphs, a network of M+1 cliques of M vertices with N=M(M+1) vertices total. The central result is a proof: at bridge weight M and hopping rate gamma=(2M-3)/(3(M-1)(M-3)), the walker provably evolves from the uniform state to a state that is 80% marked vertex and 20% its neighbor in time pi*sqrt(5)*sqrt(N)/4, which is O(sqrt(N)). Previous work on this graph could show optimal runtime numerically or deterministic success analytically, but not both in the same algorithm. The paper also maps the full range of bridge weights numerically: weights at least sqrt(M) give optimal runtime, weights strictly between sqrt(M) and M give both optimal runtime and deterministic success, and in nondeterministic regimes, measuring and checking neighbors within O(sqrt(N)) extra queries locates the marked vertex. Along the way it shows that spectral connectivity measures are not a reliable predictor of search speed even within this single graph family.

What carries the argument

The load-bearing object is the 2x2 degenerate subspace spanned by |g'> and |ac> inside a seven-dimensional symmetry-adapted basis, with the Hamiltonian split by scaling order. At w=M the leading-order Hamiltonian makes these two states degenerate at the critical hopping rate; the sqrt(M)-order terms leave them degenerate, and the constant-order term produces the energy splitting Delta E approximately 4/(sqrt(5)M). That gap sets the oscillation time pi/Delta E, giving the O(sqrt(N)) runtime, and the eigenvector |ac> sets the 80/20 measurement split. The primed change of basis is the enabling device: it creates the direct |g'>-|a> and |g'>-|c> couplings that the degenerate perturbation theory

What would settle it

Numerically diagonalize the exact seven-dimensional Hamiltonian at w=M and compute the second-order corrections to the 2x2 energy gap through all sqrt(M)-order off-diagonal couplings; if any neglected correction is O(1/M) rather than o(1/M), the 80% peak will drift as M grows. The direct check is whether the gap converges to 4/(sqrt(5)M) fast enough that the time pi*sqrt(5)M/4 remains the peak.

Watch

Extended reading notes

Core claim

At w=M, the search Hamiltonian H=-gamma*A-|a><a| is reduced by symmetry to seven basis states, then transformed to a primed basis. Splitting the transformed Hamiltonian into terms scaling as M, sqrt(M), and constants, the two leading eigenvectors |g'> (approximately the starting state) and |ac>=(2|a>+|c>)/sqrt(5) become degenerate at gamma=(2M-3)/(3(M-1)(M-3)). The sqrt(M)-order terms leave the degeneracy, while the constant-order term splits it by an energy gap Delta E approximately 4/(sqrt(5)M). As a result, |s> rotates to |ac> in time pi*sqrt(5)*M/4, approximately 1.756*sqrt(N), and measurement gives the marked vertex with probability 0.8 and its clique neighbor c with probability 0.2. Th

Load-bearing premise

The load-bearing premise is that the truncated perturbation calculation, keeping only the leading, next-to-leading, and constant terms and only the two important states, becomes exact as the number of vertices grows, so neglected couplings cannot shift the 80% success probability.

Editorial extensions

If this is right

  • At w=M, with gamma=(2M-3)/(3(M-1)(M-3)), the algorithm is analytically proven to return the marked vertex with probability 0.8 in time pi*sqrt(5)*sqrt(N)/4.
  • Any bridge weight w at least sqrt(M) gives optimal O(sqrt(N)) runtime with success probability at least 50%, so repeating the walk or measuring and checking neighbors keeps the overall search optimal.
  • For weights strictly between sqrt(M) and M, such as w=M^(3/4), the walk is asymptotically both optimal and deterministic, reaching the marked vertex with probability approaching 1 in time pi*sqrt(N)/2.
  • In nondeterministic regimes, measuring the walker and then checking the found vertex and its clique, or following the bridge from the c vertex, locates the marked vertex within O(sqrt(N)) extra queries.
  • Neither algebraic connectivity nor normalized algebraic connectivity reliably predicts search speed within the weighted simplex of complete graphs; around w=M connectivity rises while the algorithm slows down.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The primed-basis construction, found by trial and error, is likely reusable: applying the same M/sqrt(M)/constant decomposition at w=M^(3/4) could upgrade the deterministic optimal regime from numerical to analytic, which the paper leaves open.
  • The threshold at w=sqrt(M), separating suboptimal O(N^(3/4)) from optimal O(sqrt(N)) search, looks like a phase transition in the effective two-level dynamics; proving it analytically would explain why the final state switches among |b>, |a>, and mixed |a>/|c> branches.
  • If the weight-window design rule is general, the same optimal-and-deterministic window should appear on higher-order truncated simplex lattices and for Laplacian-based quantum walk search; that is a direct testable extension of the paper's numerics.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies continuous-time quantum walk search on the weighted simplex of complete graphs, a graph with M+1 cliques of M vertices and bridge weight w. The authors' central analytical result is the case w=M: by changing to a seven-dimensional basis and applying degenerate perturbation theory, they derive the critical jumping rate gamma=(2M-3)/(3(M-1)(M-3)), Eq. (7), and show that the system evolves from the uniform state to |ac>=(2|a>+|c>)/sqrt(5) in time t=pi sqrt(5) sqrt(N)/4, giving an 80% success probability and O(sqrt(N)) runtime. The remaining sections numerically map the behavior for other bridge weights: w=sqrt(M) gives 50% |a> and 50% |b>; sqrt(M) << w << M gives asymptotically deterministic search at pi sqrt(N)/2 time; w >> M gives 50% |a> and 50% |c> at pi sqrt(N/2) time; and w>=sqrt(M) is claimed to be optimal, though not always deterministic. The paper also proposes a neighbor-inspection procedure for nondeterministic regimes and argues that algebraic connectivity is not a reliable predictor of search speed within this graph family.

Significance. If the w=M derivation is made rigorous, the paper would deliver the first analytical proof of optimal continuous-time quantum search on the simplex of complete graphs, improving on earlier numerical results (36% and 75% success probabilities) and providing an explicit 80% success probability with a closed-form runtime. The paper also provides a useful numerical map of the search behavior across bridge weights, an extension of known two-stage results, and a practical neighbor-inspection strategy. The explicit formulas for gamma and the runtime, together with numerical tables up to M=10^10, are valuable and appear to strongly support the qualitative claims. The main weakness is that the analytic proof in Section 3 rests on an unproved perturbation truncation, and the broader 'optimal whenever w>=sqrt(M)' and 'deterministic when sqrt(M)<<w<<M' conclusions are extrapolated from finite numerical fits without error estimates.

major comments (3)
  1. [Section 3, display before Eq. (9)] The w=M proof is not yet rigorous. The authors split H' = H'(0)+H'(1)+H'(2) and then solve a 2x2 problem in span{|ac>,|g'>} using only H'(0)+H'(2), stating that H'(2) 'behaves as the first-order correction' because H'(1) does not perturb the two degenerate eigenvectors directly. However, H'(1) has off-diagonal elements of size gamma sqrt(M) = O(1/sqrt(M)) coupling the degenerate subspace to |b'>, |d'>, and |e'>. At the critical gamma, the relevant H'(0) gaps in those channels are O(1), so second-order virtual processes through H'(1) contribute at order (gamma sqrt(M))^2 / O(1) = O(1/M). This is the same order as the H'(2) matrix element -3 gamma / sqrt(5) = O(1/M) and the same order as the computed splitting Delta E = 4/(sqrt(5) M). Omitting these terms can change the effective 2x2 Hamiltonian by O(1) relative corrections. The sentence 'H'(2) behaves as the first-order correction' is the
  2. [Sections 4-7, Tables 5,7,9,11] The numerical determination of the critical jumping rate in the non-w=M regimes is not accompanied by uncertainty estimates or convergence tests. For each example, gamma is obtained by locating the crossing |<s|psi_0>|^2 = |<s|psi_1>|^2 and then fitting an ad-hoc inverse-power series. For w=M^{3/4}, Table 9 supplies only 13 support points to fix 9 coefficients; for w=M^{7/8}, Table 11 uses 99 points but the fit has 17 terms and no reported residuals. The coefficients are rounded to integers without justification. Since the abstract and Fig. 2b claim behavior over entire regimes (e.g., 'optimal whenever w>=sqrt(M)' and 'deterministic when sqrt(M)<<w<<M'), these are extrapolations beyond the sampled exponents. I recommend that the authors report fit residuals, confidence intervals, and an explicit statement distinguishing numerically established facts from conjectures. This does not invali
  3. [Abstract and Section 6] The claim that the algorithm is deterministic for all weights between sqrt(M) and M is supported only by three example exponents, w=M^{5/8}, M^{3/4}, and M^{7/8}. While these are representative, the paper provides no proof, or even a numerical scan, that the behavior is uniform over the continuous interval. The same issue applies to the claim in the introduction that optimality holds for every w>=sqrt(M); Fig. 3 uses only a discrete set of alpha values. The authors should temper these statements to 'numerically supported at the sampled values' or provide an argument (even heuristic) that the properties are monotone or continuous in w. This is proportionate because the abstract presents these as general results.
minor comments (5)
  1. [Table 10] The header says 'at time t_{w=\sqrt{M}}' but the section is about w=M^{3/4}; should be 'at time t_{w=M^{3/4}}'.
  2. [Section 7.3] The text refers to 'Fig. 18' when discussing w=M^2, but the relevant figure is Fig. 20.
  3. [Eq. (8) and surrounding text] The linear combination is written with |g>, but the degenerate subspace is span{|ac>,|g'>}. Clarify the notation to avoid confusion between the unprimed and primed basis states.
  4. [Section 3] The paper states that the primed basis was found 'by trial and error.' This is not an error, but the presentation would be improved by explaining the construction or at least providing the intuition in a more structured way, since the basis choice is central to the calculation.
  5. [Throughout] The term 'deterministic' is used for a success probability that tends to 1 asymptotically. Please define this terminology explicitly in Section 1 to avoid confusion with exact probability 1 for finite N.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the w=M result is derived from a degeneracy condition and eigenvector calculation, and the other regimes are explicitly numerical fits/simulations, not disguised predictions.

full rationale

The derivation chain is not circular in the sense defined here. For the central analytical claim (w=M), the critical jumping rate γ_{w=M} is fixed by a degeneracy condition: Eq. (7) sets the H'(0) eigenvalues of |g'> and the a–c eigenvector equal, and the 80% |a> / 20% |c> outcome is then read off the resulting normalized eigenvector |ac> = (2|a>+|c>)/√5, with runtime t = π/ΔE in Eq. (9). Neither the success probability nor the runtime is fitted; both are consequences of the perturbative calculation. The primed basis is admittedly found by trial and error, but a basis choice is not circular unless it secretly encodes the target result; here the critical γ and the 2:1 amplitude ratio are solved for rather than preset. For all other regimes, the paper is candid that γ is guessed, fitted to numerically determined crossing points (Tables 5, 7, 9, 11), or found by trial and error, and it describes the results as numerical rather than as predictions; e.g., Section 4 says 'We guessed ... and numerically confirmed', Section 5 says 'we fit the following function', and Section 7 says 'Through trial and error, we numerically found'. Thus the 'fitted input called prediction' pattern does not apply. Self-citations to [17,19] supply the 7D subspace, the Hamiltonian (6), and some runtimes, but those are parameter-free prior derivations that are independently cross-checked here (e.g., Table 3, Fig. 4), so they are real evidence rather than load-bearing circularity. The genuine weakness is the unproved truncation in Section 3: the text asserts 'Rather, H′(2) behaves as the first-order correction' while omitting second-order H′(1) couplings that are also O(1/M); this is a rigor/correctness gap in the 'first analytical proof' claim, not a circularity of the kind where a result reduces to its own input. Section 3 also explicitly states 'we were unsuccessful in making the approach work for the remaining weights, so the sections below are numerical rather than analytical', and Section 10 asks for analytical proofs of the numerical observations, consistent with a non-circular but partially unproven presentation.

Assumptions & free parameters 6 free parameters · 6 assumptions · 0 invented entities

The analytical w=M result rests on a chosen change of basis and an unproven perturbation truncation, but adds no fitted constants. All other regimes introduce gamma parameters either guessed or fitted to numerical data; the numerical phase diagram therefore inherits the fit uncertainty. No new physical entities are introduced.

free parameters (6)
  • Series coefficients for gamma at w=M^{1/4} = a1=1, a2=1, a3=-1, a4=-3, a5=2 (Eq. 14)
    Fit to numerically determined critical gamma values in Table 5.
  • Series coefficients for gamma at w=M^{5/8} = a1=1, a2=-1, a3=1, a4=2, a5=-4 (Eq. 15)
    Fit to numerically determined critical gamma values in Table 7.
  • Series coefficients for gamma at w=M^{3/4} = a1=1, a2=-1, a3=2, a4=-3, a5=8, a6=-14, a7=28, a8=-58, a9=103 (Eq. 17)
    Fit to numerically determined critical gamma values in Table 9.
  • Series coefficients for gamma at w=M^{7/8} = 17 coefficients listed in Eq. (19), rounded to nearest integer
    Fit to 99 numerical critical gamma values in Table 11.
  • Critical jumping rate at w=sqrt(M) = gamma = 1/(M-2) (Eq. 10)
    Guessed, then numerically confirmed; no analytic derivation.
  • Critical jumping rate for w much greater than M = gamma = (M+w-2)/((M-2)(M+2w-2)) (Eq. 21)
    Found by trial and error numerically; no analytic derivation.
assumptions (6)
  • domain assumption The search Hamiltonian H = -gamma A - |a><a| is the correct model for continuous-time quantum walk search.
    Standard from Childs and Goldstone [5]; used in Eq. (2).
  • domain assumption The simplex of complete graphs is vertex-transitive for any w, so marking any vertex yields the same 7D evolution.
    Section 1: 'the graph is vertex transitive, meaning each vertex has the same structure...'.
  • domain assumption The 7D subspace reduction with basis {|a>,|b>,|c>,|d>,|e>,|f>,|g>} is exact and the initial state is |s> approximately |g> for large N.
    Section 2, taken from [17,19]; used for Eq. (5) and Eq. (6).
  • ad hoc to paper Truncating degenerate perturbation theory at H'^(0)+H'^(1)+H'^(2) and solving only the 2x2 degenerate block gives asymptotically exact evolution for w=M.
    Section 3; the paper orders terms by scaling but does not bound neglected higher-order couplings or the spectral gap.
  • ad hoc to paper The critical jumping rate can be expanded as a series in inverse powers of M with integer coefficients in each w regime.
    Sections 5-6; fit forms are chosen by hand and not derived.
  • domain assumption Finite-M numerical simulations up to M=10^20 determine the asymptotic large-N behavior.
    The paper infers asymptotic probabilities and runtimes from large-M tables and figures without a convergence proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs." pith.science (2026). https://pith.science/paper/MQGEJYGJ

@misc{pith2026260803777,
  author       = {Pith},
  title        = {Pith review of: Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MQGEJYGJ}},
  note         = {Machine review of arXiv:2608.03777}
}
abstract

The simplex of complete graphs, also known as the first-order truncated simplex lattice, is a network of $M+1$ identical complete graphs, each with $M$ vertices, such that each clique contains an edge or bridge to every other clique. It contains $N = M(M+1)$ vertices, and previous asymptotic results using a continuous-time quantum walk to search this graph for a single marked vertex have either numerically demonstrated an optimal runtime of $O(\sqrt{N})$, or analytically proved a deterministic success probability of 1, but not both, even when the bridges are weighted. In this paper, we give the first analytical proof of optimal quantum search on this graph, proving that it occurs when the weight of the bridges equals $M$. In addition, we numerically show that the optimal runtime is achieved more broadly whenever the weight is at least $\sqrt{M}$. Furthermore, the algorithm is also deterministic when the weight scales between $\sqrt{M}$ and $M$, and this is the first example of quantum search on the simplex of complete graphs that is both asymptotically optimal and deterministic. In addition, for weights where the algorithm is nondeterministic, we give a way to find the marked vertex by inspecting neighboring vertices. Finally, while it is known that connectivity is not a reliable indicator of fast quantum search when comparing different graph families, we show that it is also unreliable within the graph family of weighted simplex of complete graphs.

Figures

Figures reproduced from arXiv: 2608.03777 by the authors.

Figure 4
Figure 4. This critical jumping rate is listed in Table 2, along with others from [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC ’96, pp

    Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC ’96, pp. 212–219. ACM, New York, NY, USA (1996)

  2. [2]

    Fortschr

    Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys.46(4-5), 493–505 (1998)

  3. [3]

    Math., pp

    Benioff, P.: Space searches with a quantum robot, volume 305 ofContemp. Math., pp. 1–12. Amer. Math. Soc., Providence, RI (2002)

  4. [4]

    Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theor. Comput.1(4), 47–79 (2005)

  5. [5]

    Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A70, 022314 (2004)

  6. [6]

    Shenvi, N., Kempe, J., Whaley, K.B.: Quantum random-walk search algorithm. Phys. Rev. A67, 052307 (2003)

  7. [7]

    Kempe, J.: Quantum random walks: An introductory overview. Contemp. Phys.44(4), 307–327 (2003)

  8. [8]

    Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A58, 915–928 (1998)

Show all 32 references
  1. [9]

    Mochon, C.: Hamiltonian oracles. Phys. Rev. A75, 042313 (2007)

  2. [10]

    Janmark, J., Meyer, D.A., Wong, T.G.: Global symmetry is unnecessary for fast quan- tum search. Phys. Rev. Lett.112, 210502 (2014)

  3. [11]

    Novo, L., Chakraborty, S., Mohseni, M., Neven, H., Omar, Y.: Systematic dimensional- ity reduction for quantum walks: Optimal spatial search and transport on non-regular graphs. Sci. Rep.5, 13304 (2015)

  4. [12]

    Quantum Inf

    Wong, T.G., Tarrataca, L., Nahimov, N.: Laplacian versus adjacency matrix in quantum walk search. Quantum Inf. Process.15(10), 4029–4048 (2016)

  5. [13]

    Philipp, P., Tarrataca, L., Boettcher, S.: Continuous-time quantum search on balanced trees. Phys. Rev. A93, 032305 (2016)

  6. [14]

    Wong, T.G.: Quantum walk search on Johnson graphs. J. Phys. A: Math. Theor.49(19), 195303 (2016)

  7. [15]

    Quantum Inf

    Tanaka, H., Sabri, M., Portugal, R.: Spatial search on Johnson graphs by continuous- time quantum walk. Quantum Inf. Process.21, 74 (2022)

  8. [16]

    Xie, W., Tamon, C.: Optimality of spatial search in graphs with infinite tail. Phys. Rev. A107, 032416 (2023)

  9. [17]

    Meyer, D.A., Wong, T.G.: Connectivity is a poor indicator of fast quantum search. Phys. Rev. Lett.114, 110503 (2015)

  10. [18]

    Dhar, D.: Lattices of effectively nonintegral dimensionality. J. Math. Phys.18(4), 577– 585 (1977)

  11. [19]

    Wong, T.G.: Faster quantum walk search on a weighted graph. Phys. Rev. A92, 032320 (2015)

  12. [20]

    Wang, Y., Wu, S., Wang, W.: Optimal quantum search on truncated simplex lattices. Phys. Rev. A101, 062333 (2020)

  13. [21]

    Quantum Inf

    Wong, T.G.: Spatial search by continuous-time quantum walk with multiple marked vertices. Quantum Inf. Process.15(4), 1411–1443 (2016)

  14. [22]

    Wong, T.G., Ambainis, A.: Quantum search with multiple walk steps per oracle query. Phys. Rev. A92, 022338 (2015)

  15. [23]

    Laser Phys

    Zhu, X., Deng, Y., Zhang, D., Gao, R., Wei, Q., Luo, Z.: Spatial search by continuous- time quantum walk on truncated simplex lattices. Laser Phys. Lett.20(3), 035205 (2023)

  16. [24]

    Quantum Inf

    Zhang, D., Zhu, X., Deng, Y., Gao, R., Wei, Q., Luo, Z.: Degenerate perturbation theory to quantum search. Quantum Inf. Process.23(4), 126 (2024)

  17. [25]

    Wong, T.G., Philipp, P.: Engineering the success of quantum walk search using weighted graphs. Phys. Rev. A94, 022304 (2016)

  18. [26]

    Duda, J., Wong, T.G.: Searching weighted barbell graphs with Laplacian and adjacency quantum walks. Phys. Rev. A110, 042417 (2024)

  19. [27]

    Duda, J., McLaughlin, M.E., Wong, T.G.: Quantum search with a generalized Laplacian. Phys. Rev. A112, 042438 (2025) Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs 37

  20. [28]

    Wong, T.G., W¨ unscher, K., Lockhart, J., Severini, S.: Quantum walk search on Kro- necker graphs. Phys. Rev. A98, 012338 (2018)

  21. [29]

    Prentice Hall (2005)

    Griffiths, D.J.: Introduction to Quantum Mechanics. Prentice Hall (2005)

  22. [30]

    Ambainis, A., Baˇ ckurs, A., Nahimovs, N., Ozols, R., Rivosh, A.: Search by quan- tum walks on two-dimensional grid without amplitude amplification. In: K. Iwama, Y. Kawano, M. Murao (eds.) Theory of Quantum Computation, Communication, and Cryptography, pp. 87–97. Springer Ber...

  23. [31]

    Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J.23(98), 298–305 (1973)

  24. [32]

    Number 92 in CBMS Regional Conference Series in Mathematics

    Chung, F.R.K.: Spectral Graph Theory. Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society (1997)

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.