Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint

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

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that a continuous-time quantum walk with inverse-weight couplings encodes the minimum spanning tree as the highest-probability path, recoverable with O(log N) qubits.

desk verdict The quantum walk part reduces to Kruskal; the central equivalence claim (min sum vs max product) is wrong, though the MDC heuristic and experiments are honest. read the letter →

arxiv 2508.07007 v1 pith:QMROEXLB submitted 2025-08-09 quant-ph

F. S. Luiz , F. F. Fanchini , Victor Hugo C. de Albuquerque , J. P. Papa , M. C. de Oliveira This is my paper · ORCID
classification quant-ph PACS 03.67.Ac
keywords minimumspanningtreemaximumdegreeconstraintcontinuous-timequantumwalkKruskal'salgorithmtransitionprobabilitiesresourceefficiencyShannonentropymaximalrandom
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

The paper proposes that, on a fully connected graph, the minimum spanning tree is the tree whose edges have the largest cumulative quantum transition probabilities, once the Hamiltonian is built from inverse edge weights. At short evolution times, the transition probability between two vertices is shown to be approximately proportional to 1/$w^{2}$, so the highest-probability edges are precisely the lowest-weight edges; a greedy 'Quantum Kruskal' selection then recovers the MST. The authors report exact MST recovery for unconstrained graphs and optimal or near-optimal total weight for degree-constrained versions when the maximum allowed degree is at least 5, using a qubit count that scales as O(log N) instead of O($N^{2}$). If the claims hold, this would make large-scale MST and MDC-MST instances accessible to hybrid quantum-classical solvers and quantum-inspired classical heuristics, sidestepping the qubit bottleneck of QUBO-based approaches.

What carries the argument

The central object is the inverse-weight Hamiltonian H = D′ − A′, where the off-diagonal coupling between vertices i and j is 1/w_ij instead of w_ij, driving a continuous-time quantum walk U(t) = $e^{{−iHt}}$. The load-bearing identity is the short-time expansion P(λ|m) ≈ $τ^{2}$ $w^{{-2}}$_{λm}, which converts the combinatorial problem of minimizing edge weights into an ordering problem on transition probabilities; the resulting 'Quantum Kruskal' algorithm greedily assembles the tree from the ordered probabilities, inheriting correctness from the classical cut property and exchange arguments.

What would settle it

Take a fully connected graph with, say, 16 vertices and choose edge weights so that two edges have nearly equal weights but very different numbers of length-2 paths connecting their endpoints. At the fitted τ(V), compute the continuous-time quantum walk transition probabilities and check whether the highest V−1 cycle-free probabilities still form the true MST. A single weight distribution where the second-order term reorders an edge pair, so that the greedy probability-ordered tree has a higher total weight than the MST, would falsify the short-time ordering claim in Eq. (9).

Watch

Extended reading notes

Core claim

The central claim is that the MST is the spanning tree maximizing the product of single-step quantum transition probabilities, T = argmax_{T'} ∏_{(i,j)∈E_{T'}} P(j|i), with P(j|i) taken from a continuous-time quantum walk whose Hamiltonian H = D' − A' uses inverse edge weights as couplings. For short times, the expansion P(λ|m) ≈ $τ^{2}$ $w^{{-2}}$_{λm} shows that the ordering of transition probabilities is the reverse ordering of edge weights; maximizing the product over the V−1 chosen edges is therefore equivalent, by a monotone transformation, to minimizing the total edge weight. The paper proves by cut-property and exchange arguments that greedy selection of the highest-probability edges that do

Load-bearing premise

The whole method rests on the assumption that within the chosen short evolution time, the transition-probability ordering is dominated by the 1/$w^{2}$ term, so the most probable edges are exactly the lowest-weight edges; the paper justifies this with a truncated Taylor expansion and an empirically fitted time window, not with a proof that higher-order interference terms never reorder the probabilities.

Editorial extensions

If this is right

  • MDC-MST instances with degree bound Δ ≥ 5 can be solved to near-optimality on graphs with roughly 10^4 vertices using approximately 14 qubits, a dramatic reduction from the thousands or more required by Ising/QUBO formulations.
  • Because the ordering of transition probabilities is what matters, the method is robust to monotone rescaling of edge weights; the quantum walk effectively discovers the MST ordering rather than computing it by explicit comparisons.
  • The algorithm runs on near-term quantum hardware, since it only requires short-time coherent evolution and not ground-state preparation or variational optimization; classically it reduces to an O(N^3) quantum-inspired heuristic.
  • The empirical time window τ(V) links the number of coherent walk steps to Grover-style search on complete graphs, suggesting that the MST structure is sampled before interference scrambles the probability ordering.
  • The observed coincidence between the entropy-maximizing tree and the MST, in both constrained and unconstrained cases, implies that the method naturally outputs the tree that maximizes information content among spanning trees.

Reading between the lines

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

  • Editorial extension: The equivalence between minimizing weights and maximizing the probability product only requires the edge-ordering to be preserved; if a rigorous bound on the second-order interference terms could be established for a broad class of weight distributions, the fitted τ(V) would become a provable guarantee rather than an empirical fit.
  • Editorial extension: The reported MDC failure modes (needing low-probability edges and degeneracy) suggest a concrete diagnosis: randomly perturbing near-degenerate weights should restore optimality at Δ = 2–4, isolating degeneracy as the main obstacle and potentially extending the exact regime.
  • Editorial extension: The interpretation that the MST is 'the most informative tree' suggests a testable bridge to network science: on real-world weighted graphs, the tree computed from quantum-walk probabilities should coincide with the MST whenever the graph is Markovian, and deviations may flag non-Markovian structures worth studying in their own right.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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. This paper proposes a continuous-time quantum walk (CTQW) approach to the minimum spanning tree (MST) problem and its maximum-degree-constrained (MDC) variant. Vertices are encoded in log2(V) qubits and the Hamiltonian is taken from the weighted Laplacian with edge weights inverted (A'_ij = 1/w_ij). Transition probabilities P(j|i) = |<j|e^{-iHτ}|i>|^2 are computed, sorted in decreasing order, and edges are added greedily if they do not create a cycle (Quantum Kruskal). The authors claim that, in a short-time window, the V−1 highest probabilities form an exact MST, and that the MDC version returns optimal/near-optimal trees for Δ≥5. They also claim that the MST maximizes a Shannon-entropy measure and relate the construction to maximal-entropy random walks. Numerical experiments on complete graphs up to 10^4 vertices are reported.

Significance. If the central equivalence were proved, the log-qubit encoding would be an interesting representational economy, and the MDC heuristic results might be of practical interest. The paper does provide extensive numerical evidence that, for random weights in limited ranges, a fitted short-time window makes the greedy probability ordering reproduce Kruskal's choice. However, the correctness of the entire construction rests on this empirical short-time window: no rigorous bound is given, the proof of the main theorem is circular, and the entropy/MERW connection is asserted rather than derived. The paper also does not provide code or data. Hence the central claim is not established.

major comments (3)
  1. [Methods, Eqs. (8)–(10), and Theorem .1] The load-bearing step is the passage from Eq. (8) to Eqs. (9)–(10). Eq. (8) contains terms of the form (τ^2/2! Σ_j w^{-1}_{λj} w^{-1}_{jm})^2 plus higher-order and cross terms, so for finite τ the probability P(λ|m) is not a function of the single edge weight w_{λm}. The paper truncates to P ≈ τ^2 w^{-2}_{λm} and then concludes that sorting by P is equivalent to sorting by w. No bound is provided for the neglected terms, and the fitted time τ(V) = 4/(π√V) + 0.1 (Fig. 3c) is obtained empirically on random weights in [1,20]; it cannot guarantee order preservation for arbitrary positive weights, where gaps between w^{-2} can be arbitrarily small. Consequently Theorem .1 is unsupported: the proof's statement that 'the edge of maximal p(e) crossing that cut, which by definition is the edge of minimal w(e)' is exactly the unproved assertion. If the ordering ever differs for some edge, Algorith
  2. [Shannon Entropy and MERW] The claim that the MST maximizes the Shannon entropy of transition probabilities, and that this reflects MERW behavior, is not established. It is illustrated for one 4-vertex graph (Fig. 4) and then generalized. No derivation connects the finite-time CTQW probabilities to the MERW stationary distribution or entropy rate. This is not needed for Algorithm 1, but it is advertised in the abstract and conclusion; as stated it is an unsupported assertion.
  3. [Algorithm 2 / MDC] The MDC extension is a greedy heuristic that enforces the degree constraint after probability sorting. The observed success rates (Fig. 5b) are empirical and cannot justify the general claim 'for MDC bigger or equal to 6 all the cases result in a MST'. Since MDC-MST is NP-hard, no polynomial guarantee is expected, but the paper should present the MDC version as a heuristic and characterize when it can fail. The ad hoc explanation in terms of 'non-Markovian' behavior does not provide such a characterization.
minor comments (5)
  1. [Algorithm 1, lines 4–5] The pseudocode sets D'_ii = 1/Dii and A'_ij = -1/Aij, which is inconsistent with Eq. (2) and the Methods definition A'_ij = 1/w_ij with H = D' - A'. As written, the pseudocode would give H = D' + A'.
  2. [Methods, encoding paragraph] The phrase 'If the number of vertices (V) is a multiple of two' should presumably read 'a power of two'.
  3. [Eqs. (2), (7) and τ=ct] The constants ℏ and c are introduced and then set to 1; the definition of τ = ct and the sign convention in the expansion Eq. (7) should be stated consistently. Currently the reader must reverse-engineer the convention from the Trotter approximation.
  4. [Figs. 3a/3b captions and text] The text describes 'solid lines' and 'dotted lines', while the captions refer to solid dots and markers; the legend should be clarified.
  5. [Table II vs Fig. 5b] Table II reports 'MST accuracy (MDC≥5) > 99%', while Fig. 5b reports 0.04% failures at Δ=5. These are consistent, but the paper should reconcile the statement 'from the MDC bigger or equal to 6 all the cases result in a MST' with the earlier text saying 'MDC exceeds 5'.

Circularity Check

3 steps flagged · score 7.0 of 10

The MST 'prediction' reduces to the inverse-weight Hamiltonian plus a τ fitted to MST-success; Theorem .1 is Kruskal's theorem conditional on an unproven probability-order/weight-order equivalence.

  1. self definitional [Methods, 'Formulation via Quantum Walk and Construction of the Hamiltonian', Eqs. (8)-(10)]
    "To align the Hamiltonian with the state-transition formulation, we introduce a key modification: the inverse of the non-zero edge weights is used to redefine the elements of the adjacency matrix. Specifically, A′ij = w−1ij for wij ̸= 0... Here we use A′ij = w−1ij, for short time the effective contribution to the probability is given by the term P(λ|m) ≈ τ^2ω^{-2}_{λm}."

    The Hamiltonian is defined with edge couplings A′ij = 1/wij, so the leading-order transition probability is a monotone decreasing function of the input edge weight. Eq. (9) then asserts that maximizing the product of probabilities is equivalent to minimizing the sum of weights. This equivalence is not an independent quantum-mechanical discovery; it is a restatement of the chosen encoding plus a truncated Taylor expansion. Any strictly decreasing function of w would yield the same Kruskal ordering, so the 'hypothesis' is baked into the definition of H.

  2. self definitional [Methods, Theorem .1 proof, 'Proof via Cut Property']
    "The algorithm picks the edge e of maximal p(e) crossing that cut, which by definition is the edge of minimal w(e)."

    The proof of Theorem .1 reduces to classical Kruskal's cut-property proof, but only if maximal p(e) is identical to minimal w(e). The phrase 'by definition' smuggles in the approximate result of Eq. (9) as if it were an exact definition. That equivalence is exactly what is not proven for the finite evolution times used in the algorithm; the full expansion Eq. (8) contains higher-order multi-edge terms that can in principle reorder probabilities. Thus the theorem's conclusion is conditional on the very equivalence it assumes, making the proof circular.

1 more flagged steps
  1. fitted input called prediction [Results, 'Exact MST reconstruction via quantum walk', Figure 3c and τ(V) fit]
    "To determine the time window during which the V−1 largest transition probabilities correspond to a valid minimum spanning tree (MST), we track the sum of weights associated with the V−1 highest-probability edges... Figure 3c plots τmax(V) ... the purple curve in the Figure 3c are well fitted by the expression: τ(V) = 4/(π√V) + 0.1."

    The evolution time τ(V) is chosen as the largest time at which the highest-probability edges still form the MST on the tested random graphs. This is a fit to the success criterion itself. The paper then uses this fitted τ(V) to report that the algorithm reconstructs the MST and achieves near-optimal weights under MDC. No analytical bound on the higher-order interference terms of Eq. (8) is provided for arbitrary weights, so the algorithm's correctness is not independently predicted; it is an artifact of selecting τ based on the outcome it is supposed to predict.

full rationale

The paper's central claim—that the quantum walk 'naturally selects' the MST by maximizing cumulative transition probabilities—is substantially circular. The Hamiltonian is deliberately built from inverse edge weights (A′ij = 1/wij), and the short-time expansion truncates the transition probability to P ≈ τ²/w². Under that truncation, sorting by probability is exactly sorting by weight, so Algorithm 1 is just Kruskal's algorithm with edges renamed by a monotone transform. Theorem .1's proof relies on the phrase 'by definition' to equate maximal probability with minimal weight, which is precisely the unproven equivalence the paper needs. Furthermore, the evolution time τ(V) is empirically fitted to the maximum time at which the highest-probability edges still form the MST, so the reported success is partly a consequence of the fitting procedure rather than an independent verification. There are no load-bearing self-citations and no imported uniqueness theorems; the circularity is internal to the derivation. However, the paper is transparent that the algorithm is a 'kind of quantum Kruskal,' and the numerical benchmarks against classical and MILP solvers are real, so the score is high but not maximal: the quantum walk contributes no ordering information beyond the inverse weights, but the empirical demonstrations do show that the fitted short-time regime works on the tested distributions. The central derivation is nevertheless equivalent to its inputs by construction, giving a score of 7.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper's central derivation depends on two pulled-from-a-hat choices: the inverse-weight Hamiltonian and the fitted evolution time. The former builds the answer into the equations, and the latter is calibrated on the simulations it is then used to explain.

free parameters (2)
  • Evolution time tau = tau(V) = 4/(pi sqrt(V)) + 0.1 (plateau near 0.1 for large V)
    The probability matrix depends on the chosen evolution time; the paper selects a time window fitted to simulation data in Figure 3c to ensure correct MST reconstruction.
  • Inverse-weight encoding = A'_ij = 1/w_ij and D'_ii = sum_j 1/w_ij
    The functional form is chosen by hand so that low-weight edges become high-probability transitions; this choice is the entire mechanism of the result, not a derived consequence.
assumptions (4)
  • standard math Cut property of minimum spanning trees
    Used in Theorem .1 to show that greedy selection by minimal weight is safe.
  • domain assumption Leading-order truncation of the Trotter/Dyson expansion dominates transition-probability ordering
    Eqs. (7)-(9) assume the short-time term tau^2 w^{-2} determines the ranking of probabilities; no proof is given that higher-order interference preserves this ordering.
  • domain assumption Graph is fully connected with positive edge weights
    The encoding and the complete-graph experiments assume full connectivity; the paper does not address sparse or disconnected graphs.
  • ad hoc to paper Shannon entropy maximization coincides with minimum weight
    Asserted after one 4-vertex example (Figure 4); not proven and not generally true.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint." pith.science (2026). https://pith.science/paper/QMROEXLB

@misc{pith2026250807007,
  author       = {Pith},
  title        = {Pith review of: A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QMROEXLB}},
  note         = {Machine review of arXiv:2508.07007}
}
abstract

We present a novel quantum walk-based approach to solve the Minimum Spanning Tree (MST) problem under a maximal degree constraint (MDC). By recasting the classical MST problem as a quantum walk on a graph, where vertices are encoded as quantum states and edge weights are inverted to define a modified Hamiltonian, we demonstrate that the quantum evolution naturally selects the MST by maximizing the cumulative transition probability (and thus the Shannon entropy) over the spanning tree. Our method, termed Quantum Kruskal with MDC, significantly reduces the quantum resource requirement to $\mathcal{O}(\log N)$ qubits while retaining a competitive classical computational complexity. Numerical experiments on fully connected graphs up to $10^4$ vertices confirm that, particularly for MDC values exceeding $4$, the algorithm delivers MSTs with optimal or near-optimal total weights. When MDC values are less or equal to $4$, some instances achieve a suboptimal solution, still outperforming several established classical algorithms. These results open promising perspectives for hybrid quantum-classical solutions in large-scale graph optimization.

Figures

Figures reproduced from arXiv: 2508.07007 by the authors.

Figure 1
Figure 1. Illustration of quantum-walk based MST reconstruction on a small example. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Trotter–Suzuki approximation: The figure shows the transition probabilities for the graph in Figure 1a. Solid lines: full evolu￾tion operator; dashed lines: Trotter–Suzuki (n=1). The terms of the Hamiltonian (2) do not commute with each other, "X k D′ kk|k⟩⟨k|, X o X l Alo|l⟩⟨o| # = X p X q D′ ppA ′ pq (|q⟩⟨p| − |p⟩⟨q|), (5) where we use that the indexes of the sum are dumb and the graph are undirected, A′ pq = A′ q… view at source ↗
Figure 3
Figure 3. Evolution of MST reconstruction over varying graph sizes and times. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Shannon entropy correlates with MST. Plot of total tree weight versus Shannon entropy for the 16 possible spanning trees of the example graph in Fig￾ure 1a. The MST is highlighted by the red dashed marker, which attains the maximum entropy among all trees. This result …
Figure 5
Figure 5. Figure 5: Performance comparison of MST algorithms under MDC. [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: Shannon entropy of MDC spanning trees. Plot of total tree weight versus Shannon entropy for all 16 spanning trees of the example graph in Figure 1a. Four trees violate the maximum-degree constraint (marked with “X” symbols) and are excluded from analysis. Among the rem…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem

    quant-ph 2025-12 reject novelty 4.0 of 10

    A continuous-time quantum walk transition-probability heuristic is proposed for Minimum Vertex Cover, with iterative vertex freezing.

Reference graph

Works this paper leans on

46 extracted references · 34 canonical work pages · cited by 1 Pith paper

  1. [1]

    For any partition of V into S and V \ S, the edge of minimum weight crossing the cut belongs to some MST

    Proof via Cut Property Lemma .2(Cut Property). For any partition of V into S and V \ S, the edge of minimum weight crossing the cut belongs to some MST. Applying the lemma: at any stage, consider the cut be- tween the connected components formed by the already- chosen edges. The algorithm picks the edgee of maximal p(e) crossing that cut, which by definit...

    work page

  2. [2]

    non-Markovian

    Proof via Exchange Argument Let T ∗ be an arbitrary MST and let T be the tree constructed by our algorithm. Suppose T ̸= T ∗. Let e ∈ T \ T ∗ be the edge of highest probability (i.e., lowest weight) among those in T but not in T ∗. Adding e to T ∗ creates a cycleC. Since e /∈ T ∗, there exists an edge f ∈ C with f /∈ T. Because e was chosen by maximal pro...

    work page 2012

  3. [3]

    Castillo, Process Optimization: A Statistical Ap- proach, International Series in Operations Research & Management Science (Springer US, 2007)

    E. Castillo, Process Optimization: A Statistical Ap- proach, International Series in Operations Research & Management Science (Springer US, 2007)

    work page 2007

  4. [4]

    Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 10.3389/fphy.2014.00005 (2014)

    A. Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 10.3389/fphy.2014.00005 (2014)

    arXiv 2014

  5. [5]

    R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. H. III, Approximation algorithms for degree- constrained minimum-cost network-design problems, Al- gorithmica 31, 58 (2001)

    work page 2001

  6. [6]

    Fowler, Improved QUBO formulations for D-Wave quantum computing, Master’s thesis, University of Auck- land (2017)

    A. Fowler, Improved QUBO formulations for D-Wave quantum computing, Master’s thesis, University of Auck- land (2017)

    work page 2017

  7. [7]

    Graham and P

    R. Graham and P. Hell, On the history of the minimum spanning tree problem, Annals of the History of Com- puting 7, 43 (1985)

    work page 1985

  8. [8]

    Y. K. Dalal and R. M. Metcalfe, Reverse path forward- ing of broadcast packets, Commun. ACM21, 1040–1048 (1978)

    work page 1978

Show all 46 references
  1. [9]

    J. C. Gower and G. J. S. Ross, Minimum spanning trees and single linkage cluster analysis, Journal of the Royal Statistical Society. Series C (Applied Statistics)18, 54 (1969)

    1969

  2. [10]

    Asano, B

    T. Asano, B. Bhattacharya, M. Keil, and F. Yao, Cluster- ing algorithms based on minimum and maximum span- ning trees, inProceedings of the Fourth Annual Sympo- sium on Computational Geometry, SCG ’88 (Association for Computing Machinery, New York, NY, USA, 1988) p. 252–257

    1988

  3. [11]

    Päivinen, Clustering with a minimum spanning tree of scale-free-like structure, Pattern Recognition Letters 26, 921 (2005)

    N. Päivinen, Clustering with a minimum spanning tree of scale-free-like structure, Pattern Recognition Letters 26, 921 (2005)

    2005

  4. [12]

    J. P. Papa, A. X. Falcão, and C. T. N. Suzuki, Supervised pattern classification based on optimum-path forest, In- ternational Journal of Imaging Systems and Technology 19, 120 (2009)

    2009

  5. [13]

    J.P.Papa, A.X.Falcão, V.H.C.Albuquerque,andJ.M. R. S. Tavares, Efficient supervised optimum-path forest classification for large datasets, Pattern Recognition45, 512 (2012)

    2012

  6. [14]

    Y. Xu, V. Olman, and D. Xu, Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees, Bioinformatics18, 536 (2002)

    2002

  7. [15]

    S. L. Gan and M. Djauhari, Optimality problem of net- work topology in stocks market analysis, Physica A: Sta- tistical Mechanics and its Applications419, 108 (2014)

    2014

  8. [16]

    R. N. Mantegna, Hierarchical structure in financial mar- kets (1999)

    1999

  9. [17]

    Assuncao, M

    R. Assuncao, M. Neves, G. Camara, and C. Freitas, Effi- cient regionalization techniques for socio- economic geo- graphical units using minimum spanning trees, Interna- tional Journal of Geographical Information Science20, 10.1080/13658810600665111 (2020)

    2020 doi

  10. [18]

    Suk and O

    M. Suk and O. Song, Curvilinear feature extraction us- ing minimum spanning trees, Computer Vision, Graph- ics, and Image Processing26, 400 (1984)

    1984

  11. [19]

    J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society7, 48 (1956)

    1956

  12. [20]

    R. C. Prim, Shortest connection networks and some gen- eralizations, The Bell System Technical Journal36, 1389 (1957)

    1957

  13. [21]

    R. M. Karp, Reducibility among combinatorial prob- lems, in Complexity of Computer Computations: Pro- ceedings of a symposium on the Complexity of Com- puter Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and spon...

    1972

  14. [22]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near- term devices, Phys. Rev. X10, 021067 (2020)

    2020

  15. [23]

    Squartini and D

    T. Squartini and D. Garlaschelli, Maximum-Entropy Networks: Pattern Detection, Network Reconstruction and Graph Combinatorics, SpringerBriefs in Complexity 13 (Springer International Publishing, 2017)

    2017

  16. [24]

    Farhi and S

    E. Farhi and S. Gutmann, Quantum computation and decision trees, Physical Review A58, 915 (1998)

    1998

  17. [25]

    Schulz, D

    S. Schulz, D. Willsch, and K. Michielsen, Guided quan- tum walk, Physical Review Research6, 10.1103/Phys- RevResearch.6.013312 (2024)

    2024 doi

  18. [26]

    Scully and M

    M. Scully and M. Zubairy,Quantum Optics, Quantum Optics (Cambridge University Press, 1997)

    1997

  19. [27]

    Qiang, S

    X. Qiang, S. Ma, and H. Song, Review on quantum walk computing: Theory, implementation, andapplication,In- telligent Computing 10.34133/icomputing.0097 (2024)

    2024 doi

  20. [28]

    H.BreuerandF.Petruccione, The Theory of Open Quan- tum Systems (Oxford University Press, 2002)

    2002

  21. [29]

    Hatano and M

    N. Hatano and M. Suzuki, Finding exponential product formulas of higher orders (2005)

    2005

  22. [30]

    Sinatra, J

    R. Sinatra, J. Gómez-Gardeñes, R. Lambiotte, V. Nicosia, and V. Latora, Maximal-entropy random walks in complex networks with limited information, Phys. Rev. E83, 030103 (2011)

    2011

  23. [31]

    J. K. Ochab and Z. Burda, Localization of the maxi- mal entropy random walk, Physical Review Letters102, 160602 (2009)

    2009

  24. [32]

    Duboux and Y

    T. Duboux and Y. Offret, Maximum entropy random walks: the infinite setting and the example of spi- der networks with their scaling limits, arXiv preprint arXiv:2203.05274 10.48550/arXiv.2203.05274 (2022)

    2022 doi

  25. [33]

    Chakraborty, L

    S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar, Spatial search by quantum walk is optimal for almost all graphs, Phys. Rev. Lett.116, 100501 (2016)

    2016

  26. [34]

    A. M. Childs, On the relationship between continuous- and discrete-time quantum walk, Communications in Mathematical Physics294, 581 (2009)

    2009

  27. [35]

    T. G. Wong, Grover search with lackadaisical quantum walks, Journal of Physics A: Mathematical and Theoret- ical 48, 435304 (2015)

    2015

  28. [36]

    Y. Zhou, E. M. Stoudenmire, and X. Waintal, What lim- its the simulation of quantum computers?, Phys. Rev. X 10, 041038 (2020)

    2020

  29. [37]

    M. B. Cohen, Y. T. Lee, and Z. Song, Solving linear programs in the current matrix multiplication time, J. ACM 68, 10.1145/3424305 (2021)

    2021 doi

  30. [38]

    Golub and C

    G. Golub and C. Van Loan,Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences (Johns Hopkins University Press, 1996)

    1996

  31. [39]

    Cormen, C

    T. Cormen, C. Leiserson, R. Rivest, and C. Stein,Intro- duction To Algorithms, Mit Electrical Engineering and Computer Science (MIT Press, 2001)

    2001

  32. [40]

    Tarjan, Efficiency of a good but not linear set union algorithm, Journal of the ACM (JACM)22, 215 (1975)

    R. Tarjan, Efficiency of a good but not linear set union algorithm, Journal of the ACM (JACM)22, 215 (1975)

    1975

  33. [41]

    Motlagh and N

    D. Motlagh and N. Wiebe, Generalized quantum signal processing, PRX Quantum5, 020368 (2024)

    2024

  34. [42]

    A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem, Electron. Colloquium Comput. Com- plex. TR96 (1995)

    1995

  35. [43]

    Beals, S

    R. Beals, S. Brierley, O. Gray, A. W. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather, Efficient dis- tributed quantum computing, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sci- ences 469, 20120686 (2013)

    2013

  36. [44]

    C. E. Shannon, A mathematical theory of communica- tion, Bell System Technical Journal27, 379 (1948)

    1948

  37. [45]

    Cayley, A theorem on trees (Cambridge University Press, 1888) pp

    A. Cayley, A theorem on trees (Cambridge University Press, 1888) pp. 376–378

  38. [46]

    M.Aigner, K.Hofmann,andG.Ziegler, Proofs from THE BOOK (Springer Berlin Heidelberg, 2013)

    2013

Pith tools

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