REVIEW 3 major objections 5 minor 34 references
Knapsack and Shortest Path Problems Generalizations From A Quantum-Inspired Tensor Network Perspective
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper claims that contracting a tensor network whose amplitudes are exponentials of the objective, with constraints enforced by projection, yields the exact optimal solution to knapsack and shortest-path problems by selecting the…
desk verdict A clean tensor-network reformulation of two classic DP problems, but the 'exact' claim only holds in an unattainable tau limit; the real contribution is the generalization section. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The core object is a chain-shaped tensor network encoding the objective and all constraints as exponentials. For knapsack, the tensors $M^m$ and $K^k$ carry a variable index $i$ and a weight index $\mu$; the nonzero elements place $e^{\tau v_i}$ on the diagonal $\mu = i w_m$ plus accumulated weight, and the final tensor clamps the state to the capacity. Contracting the chain downward and storing intermediate vectors turns each variable determination into one sparse matrix-vector product of cost $O(Q c_k)$, giving total $O(nQ c)$ time and $O(nQ)$ memory. For shortest path, the tensors are $V \times V$ matrices with entries $e^{-\tau E_{ij}}$, tracing out all but one vertex to get the next step. The reused-intermediate contraction scheme is what reduces the complexity from $O(n^2 Q c)$ to $O(nQ c)$.
What would settle it
Find a knapsack or shortest-path instance for which, over every $\tau$ in the range where the exponentials avoid overflow, the argmax of the partial-traced tensor network differs from the true optimum computed by dynamic programming or Dijkstra's algorithm. If such an instance exists, the "exact equation" claim fails in the practical sense the paper's experiments use; the paper's own Fig. 8 already shows the relative error rising for large $\tau$.
Extended reading notes
Core claim
The central claim is that a tensor network can serve as an exact formula for a combinatorial optimization problem. For knapsack, the network starts from a uniform superposition of all item-count configurations, applies a diagonal evolution that multiplies each configuration by $e^{\tau V(\vec{x})}$, then projects out configurations exceeding the capacity $Q$; tracing out all variables except one leaves a vector whose largest component identifies the optimal value of that variable. For shortest path, the same construction uses $e^{-\tau C(\vec{v})}$ along a fixed-length path with origin and destination fixed, and partial tracing selects the next vertex. The authors state that "the provided tensor network is the exact formula that solves the combinatorial problem," and they support this with convergence experiments showing relative error decreasing as $\tau$ increases. They further note that in floating-point practice $\tau$ must be chosen large enough to separate the optimal amplitude but small enough to avoid overflow, which limits the size of instances solvable in practice.
Load-bearing premise
The argument hinges on choosing a single real parameter $\tau$ that makes the optimal configuration's amplitude dominate every other configuration's amplitude in every partial trace, while remaining small enough that no exponential overflows the computer's number format; the paper gives no rule for choosing such a $\tau$ and does not prove one always exists for a given instance.
Editorial extensions
If this is right
- If correct, any knapsack instance with $n$ classes and capacity $Q$ can be solved in $O(nQ)$ time and $O(nQ)$ memory by building the tensors and contracting, with no branching or search tree.
- The same construction handles 0-1, bounded, and unbounded knapsack variants uniformly, since the qudit dimension $c_i+1$ encodes the multiplicity of each class.
- For shortest paths, the network gives a fixed-number-of-steps solution in $O(nE)$ time, and the intermediate-reuse scheme keeps the total cost linear in the number of steps.
- The generalizations to nonlinear value functions, polynomial weight constraints, and time-dependent edge costs are solved by the same formula with only the tensor entries changed, at unchanged time complexity.
- The method provides an explicit analytical description of the optimum as the argmax of a partial trace, which may offer a new mathematical handle on these classical problems.
Reading between the lines
- The paper stops short of proving a bound on $\tau$; a natural extension would be to derive a sufficient $\tau$ from the gap between the optimal and second-best objective values and the number of competing configurations, turning the practical recipe into a certified algorithm.
- The amplitude-competition mechanism suggests a generic recipe for any combinatorial problem whose constraints can be expressed as local projectors on a chain graph, hinting at a broader class of "exact-by-construction" tensor network solvers beyond the two problems treated here.
- Because exactness in real arithmetic holds as $\tau$ grows while the floating-point version degrades, a high-precision or log-domain implementation that works with exponents rather than exponentials could remove the overflow bottleneck and test the exactness claim on larger instances.
- The reported linear scaling with $Q$ and $E$ invites a direct comparison against other exact methods like branch-and-bound on instances where overflow is avoided, which would clarify where the tensor network is competitive in practice.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents two tensor-network algorithms, one for bounded/unbounded knapsack and one for fixed-step shortest path. The algorithms are built from an imaginary-time amplitude e^{τV(x)} (or e^{-τC(v)}), a constraint projector, and a partial trace that produces per-variable marginals; each variable is selected from the position of the largest marginal, and tensor contractions are reused to reach O(nQ) time for knapsack and O(nE) time for shortest path. Sections 5.1–5.3 extend the construction to nonlinear/polynomial knapsack and time-dependent edge costs. The abstract and Section 2.1.2 claim that the tensor network is an exact formula returning the optimal solution.
Significance. If the exactness claim were true, the paper would offer a conceptually clean single-formula view of two classical optimization problems, and the reuse of intermediate contractions gives polynomial complexity. The tensor network itself is a correct exhaustive enumeration in exact arithmetic and the sparse contraction scheme is transparent. However, the exactness is only asymptotic in the parameter τ; the paper provides no bound or selection rule for τ, and its own experiments (Fig. 8, Sec. 4.1) show that the algorithm becomes suboptimal when τ is too small or too large. The paper is therefore best read as a softmax-marginal heuristic rather than the exact method advertised. The claimed generalizations in Sec. 5.1–5.2 also contain an explicit formula that does not maximize the stated nonlinear value function. In its current form the central advertised result is not established.
major comments (3)
- [Sec. 2.1.1, Eq. (5); abstract; Sec. 2.1.2] The paper's central claim that Eqs. (3)–(5) provide 'an exact equation which returns the optimal solution' is not true for any finite τ. Eq. (5) computes S_k(τ)=Σ_{x:x_0=k,W(x)≤Q} e^{τV(x)}; for finite τ this is a softmax marginal, so a coordinate with many slightly suboptimal completions can have a larger sum than the coordinate containing the global optimum, and argmax_k S_k(τ) can be wrong. Exactness holds only for τ→∞, and the required threshold grows roughly like (1/δ) log M, where δ is the gap between the optimum value and the best competitor and M is the multiplicity of competing feasible configurations. The paper neither states nor proves such a threshold; Section 4.1 explicitly concedes that overflow prevents reaching it in practice, and Section 6 repeats that exactness is only 'theoretical.' Because the abstract and Sec. 2.1.2 base the paper's contribution on this exactness, the missing τ-selection rule is load-bearing.
- [Sec. 4.1, Fig. 8, Eq. (19)] The experimental evidence does not support the exactness/optimality claim. The relative error in Eq. (19) is measured against a greedy heuristic, not against the true optimum; achieving 'results as good as greedy' is weaker than solving the problem exactly. Fig. 8 also shows that relative error is not monotone in τ and increases after overflow for some c_i, demonstrating that no simple 'larger τ is better' rule works. Without an instance-specific τ-selection rule or a comparison against an exact solver, the experiments cannot validate the headline claim.
- [Sec. 5.1, Eq. (25); Sec. 5.2, Eq. (27)] The nonlinear-generalization tensors are mathematically incorrect for arbitrary value functions. Eq. (25) defines d_i = argmax_y ρ_i_y with ρ_i_y = 1/(Q−i−w_{n−1,y}); this chooses the feasible y that minimizes the remaining capacity, not the y that maximizes v_{n−1,y}. For the linear positive-value case minimizing remaining capacity can coincide with maximizing the count, but for an arbitrary nonlinear v_{n−1}(y) (e.g., a value function with a peak at a smaller y) the formula selects the wrong value. The same issue occurs in Eq. (27), where the last tensor picks a single d_i by residual-capacity minimization rather than optimizing the value function over all feasible y. Consequently the claimed easy handling of nonlinear and polynomial knapsack in Secs. 5.1–5.2 is not established.
minor comments (5)
- [Sec. 3.1.1, Eq. (13)] The right-hand side of Eq. (13) is not a well-formed tensor product as written, because consecutive factors share the index v_{t+1}; the intended pairwise contraction between adjacent qudits should be stated explicitly.
- [Sec. 5.1 and Sec. 5.2] The values v_{i,b}=-∞ and w_{i,b}=∞ for b>c_i are never resolved in the argmax definitions; the text should state explicitly that infeasible y are excluded from the argmax rather than using extended values inside exponentials.
- [Sec. 4.2] Comparing the n-step path found by the tensor network with Dijkstra's variable-length shortest path requires specifying how paths of length shorter than n are handled; self-loop padding is not discussed, so the comparison may be between different optimization problems.
- [Data and Code Availability] The statement that all data and code are available 'upon reasonable request' is not verifiable; for an algorithmic paper with strong performance claims, a public code repository would substantially improve reproducibility.
- [Introduction] The reference to Ali (2025) as the source of the 'exact equation' is to an unpublished document and is not described; the present paper should either provide the proof itself or cite a peer-reviewed source.
Circularity Check
The tensor-network contractions are exact algebra, and no fitted parameter is renamed as a prediction; the score is 4 because the paper's headline exactness is imported from a same-author unpublished citation, while the unquantified tau regime is a correctness gap rather than a by-construction circularity.
-
self citation load bearing
[Introduction, second paragraph]
"Our method is based on previous works applied to traveling salesman problem (Ali et al., 2024b), QUBO problems (Ali et al., 2024d) and task scheduling (Ali et al., 2024c). Following the results in (Ali, 2025), it provides an exact equation that returns the optimal solution to these problems."
The paper's own derivation establishes only that Eq. (5) equals the weighted feasible-state sum; the unconditional claim that this 'returns the optimal solution' is not proved in the paper. The introduction attributes that exactness to Ali (2025), an unpublished manuscript by co-author A. M. Ali. No independent, machine-checked, or externally benchmarked derivation of the exactness theorem is supplied, so the central headline rests on a same-author citation that is load-bearing.
full rationale
The core contraction chain (Eqs. 2-5) is self-contained: Eq. (5) follows from Eq. (3) by linearity and exactly represents the sum of e^{tau V(x)} over feasible configurations. No data are fitted and no fitted parameter is renamed as a prediction; the tau scan in Fig. 8 is an experiment, not a per-instance calibration. However, the abstract and Section 2.1.2 claim an 'exact equation' that 'returns the optimal solution,' while the text only justifies this 'for a sufficiently large tau' and 'if the peak is high enough' (Section 2.1.1). No threshold, bound, or tau-selection rule is given, and Section 4.1 concedes that overflow prevents reaching the exact regime in practice. This is a genuine missing-support/correctness issue, but it is not circular in the strict sense: the finite-tau softmax marginal is not asserted to equal the optimum by construction. The separate circular element is the delegation of unconditional exactness to Ali (2025), a same-author unpublished citation. Weighing these together, the central claim still has independent content in the explicit tensor equations, so the appropriate score is 4 rather than higher.
Assumptions & free parameters
free parameters (2)
- tau (imaginary time evolution parameter) =
not fixed; e.g., tau=1 in knapsack experiments, tau=600 in shortest path
- number of steps n in the shortest path network =
varies, e.g., 50 to 800 in experiments
assumptions (4)
- domain assumption Exponential amplitudes e^{tau V(x)} can be computed and compared without overflow for all states in the superposition.
- domain assumption All knapsack item values are strictly positive, so the last class should always be filled to its maximum allowed count given remaining capacity.
- domain assumption Shortest path edge costs are non-negative and self-loop costs are zero, so any path of length k can be padded to length n without changing the cost.
- domain assumption In the polynomial knapsack generalization, all coefficients a_k are positive integers, implying Q' >= F(W) >= W.
Cite this review
Pith. "Pith review of Knapsack and Shortest Path Problems Generalizations From A Quantum-Inspired Tensor Network Perspective." pith.science (2026). https://pith.science/paper/J6P3CG2O
@misc{pith2026250611711,
author = {Pith},
title = {Pith review of: Knapsack and Shortest Path Problems Generalizations From A Quantum-Inspired Tensor Network Perspective},
year = {2026},
howpublished = {\url{https://pith.science/paper/J6P3CG2O}},
note = {Machine review of arXiv:2506.11711}
}
read the original abstract
In this paper, we present two tensor network quantum-inspired algorithms to solve the knapsack and the shortest path problems, and enables to solve some of its variations. These methods provide an exact equation which returns the optimal solution of the problems. As in other tensor network algorithms for combinatorial optimization problems, the method is based on imaginary time evolution and the implementation of restrictions in the tensor network. In addition, we introduce the use of symmetries and the reutilization of intermediate calculations, reducing the computational complexity for both problems. To show the efficiency of our implementations, we carry out some performance experiments and compare the results with those obtained by other classical algorithms.
Figures
Figures from the paper (8 more)
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...
-
[2]
Ali, A. M. (2025). Explicit solution equation for every combinatorial problem via tensor networks: Melocoton
work page 2025
-
[3]
Ali, A. M., de Leceta, A. M. F., and Rubio, J. L. (2024a). Anomaly detection from a tensor train perspective
work page 2024
-
[4]
Ali, A. M., Delgado, I. P., and de Leceta, A. M. F. (2024b). Traveling salesman problem from a tensor networks perspective
work page 2024
-
[5]
Ali, A. M., Delgado, I. P., Markaida, B. G., and de Leceta, A. M. F. (2024c). Task scheduling optimization from a tensor network perspective
work page 2024
-
[6]
Ali, A. M., Delgado, I. P., Roura, M. R., and de Leceta, A. M. F. (2024d). Polynomial-time solver of tridiagonal qubo and qudo problems with tensor networks
work page 2024
-
[7]
Bateni, M., Hajiaghayi, M., Seddighin, S., and Stein, C. (2018). Fast algorithms for knapsack via convolution and prediction. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2018, page 1269–1282, New York, NY, USA. Association for Computing Machinery
work page 2018
-
[8]
Benson, B. M., Ingman, V. M., Agarwal, A., and Keinan, S. (2023). A cqm-based approach to solving a combinatorial problem with applications in drug design
work page 2023
Show all 34 references
-
[9]
Biamonte, J. (2020). Lectures on quantum tensor networks
2020
-
[10]
and Bergholm, V
Biamonte, J. and Bergholm, V. (2017). Tensor networks in a nutshell
2017
-
[11]
Bock, S., Bomsdorf, S., Boysen, N., and Schneider, M. (2024). A survey on the traveling salesman problem and its variants in a warehousing context. European Journal of Operational Research
2024
-
[12]
Dauzère-Pérès, S., Ding, J., Shen, L., and Tamssaouet, K. (2024). The flexible job shop scheduling problem: A review. European Journal of Operational Research , 314(2):409--432
2024
-
[13]
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik , 1(1):269--271
1959
-
[14]
Egor, B., Egor, G., and Daria, L. (2022). Two heuristics for one of bin-packing problems. IFAC-PapersOnLine , 55(10):2575--2580. 10th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2022
2022
-
[15]
Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm
2014
-
[16]
Fredman, M. L. and Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM , 34(3):596–615
1987
-
[17]
Glover, F., Kochenberger, G., and Du, Y. (2019). A tutorial on formulating and using qubo models
2019
-
[18]
and Kahan, W
Golub, G. and Kahan, W. (1965). Calculating the singular values and pseudo-inverse of a matrix. Journal of the Society for Industrial and Applied Mathematics Series B Numerical Analysis , 2(2):205--224
1965
-
[19]
and Yeo, A
Gutin, G. and Yeo, A. (2007). The greedy algorithm for the symmetric tsp. Algorithmic Operations Research , 2(1)
2007
-
[20]
Hao, T., Huang, X., Jia, C., and Peng, C. (2022). A quantum-inspired tensor network algorithm for constrained combinatorial optimization problems. Frontiers in Physics , 10
2022
-
[21]
E., Nilsson, N
Hart, P. E., Nilsson, N. J., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics , 4(2):100--107
1968
-
[22]
Katangur, A., Pan, Y., and Fraser, M. (2002). Message routing and scheduling in optical multistage networks using simulated annealing. In Proceedings 16th International Parallel and Distributed Processing Symposium , pages 8 pp--
2002
-
[23]
and Vygen, J
Korte, B. and Vygen, J. (2000). Bin-Packing , pages 407--422. Springer Berlin Heidelberg, Berlin, Heidelberg
2000
-
[24]
and Vygen, J
Korte, B. and Vygen, J. (2008). The Traveling Salesman Problem , pages 527--562. Springer Berlin Heidelberg, Berlin, Heidelberg
2008
-
[25]
Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research , 59(2):231--247
1992
-
[26]
u l, M., Hamacher, H. W., and T \
Lenstra, J. K. (1992). Job shop scheduling. In Akg \"u l, M., Hamacher, H. W., and T \"u fek c i, S., editors, Combinatorial Optimization , pages 199--207, Berlin, Heidelberg. Springer Berlin Heidelberg
1992
-
[27]
Liu, G., Xu, X., Wang, F., and Tang, Y. (2022). Solving traveling salesman problems based on artificial cooperative search algorithm. Computational Intelligence and Neuroscience , 2022:1–8
2022
-
[28]
Mathews, G. B. (1896). On the partition of numbers. Proceedings of the London Mathematical Society , s1-28(1):486--490
-
[29]
J., Aspuru-Guzik, A., and O'Brien, J
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., and O'Brien, J. L. (2014). A variational eigenvalue solver on a photonic quantum processor. Nature Communications , 5(1):4213
2014
-
[30]
Pilcher, T. (2023). A self-adaptive genetic algorithm for the flying sidekick travelling salesman problem
2023
-
[31]
Qing, Y., Li, K., Zhou, P.-F., and Ran, S.-J. (2024). Compressing neural network by tensor network with exponentially fewer variational parameters
2024
-
[32]
Stastny, J., Skorpil, V., Balogh, Z., and Klein, R. (2021). Job shop scheduling problem optimization by means of graph-based algorithm. Applied Sciences , 11(4)
2021
-
[33]
and Dong, H
Wang, B. and Dong, H. (2024). Bin packing optimization via deep reinforcement learning
2024
-
[34]
Wang, J., Roberts, C., Vidal, G., and Leichenauer, S. (2020). Anomaly detection with tensor networks. CoRR , abs/2006.02516
2020 arXiv
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.