Polynomial-time Solver of Tridiagonal QUBO, QUDO and Tensor QUDO problems with Tensor Networks

For the code, I understand that the authors' efforts to include everything in one Jupyter notebook and make it self-contained. However, an installable package with proper code structure is almost always more user-friendly, maintainable, and expandable. Since you already have a separate copy in Python files for the web app, it should be straightforward to add a pyproject.toml to make it a package.

Installation instructions - The requirements.txt in the web app folder seems outdated and doesn't match the dependency list in README.md. The latter, on the other hand, doesn't specify the version requirements. Having a proper pyproject.toml help solve such issues.

Documentation - The functions are all documented, but there is no other way of browsing the documentation (e.g., a hosted API reference website, or an aggregated file) besides looking at the docstrings.

Programming standards - Type-hinting is adopted but can be improved. For example, the dict type hints should also specify the types of the mapping. The proper typing for numpy arrays is numpy.typing.NDArray, followed by numpy dtype. There is no formatting, linting, or type-checking. Some practices, such as using np.random.seed() instead of np.random.default_rng(), are not desirable.

Testing - There is no testing.

For the accompanying manuscript, SciPost Physics Codebases requires it to be a user guide containing a guide to using the software and worked-out examples, both of which are lacking in the current manuscript.

From an academic paper perspective, the manuscript (and this work in general) has numerous issues (in the order of appearance):

1. I believe the more commonly used term for QUBO generalizing to integer variables is quadratic unconstrained integer optimization (QUIO). It's a good idea to at least mention QUIO as an alternative name for the same concept.

2. Tensor QUBO seems to be a self-invented concept. I don't think it is more general than QUBO/QUDO as claimed in the manuscript; it's just an alternative representation.

3. "Lineal chain" is also not used elsewhere. In scientific writing, "Linear chain" is the correct term. "Lineal" refers to ancestry/descent.

4. Solving a 1D nearest-neighbor QUBO/Ising model efficiently is not a novel contribution. It is well-known to be solvable in linear time O(N) using dynamic programming or the transfer matrix method. The claim "in the state-of-the-art, there are no prior algorithms that address the lineal chain problem exactly and efficiently" is therefore factually incorrect, and I suspect that the claim of the algorithm in Ref. [12] takes O(n^16) is a misinterpretation (likely Ref. [12] is solving a different problem).

5. The "theorems" given in the manuscript are just informal claims without any mathematically rigorous proofs.

6. The caption descriptions of Figure 2 (b) and (c) should be reversed.

7. The algorithm and the complexity analysis in general seem valid. Though I suspect a simpler MPS method exists for this problem without needing imaginary time evolution. ITE leads to numerical stability issues when tau is taken to infinity. Section 3.4 discusses the conditions tau should satisfy in the practical scenario to avoid overflow, but it remains unclear how exactly tau can be tuned to satisfy these conditions without running the algorithm multiple times. Section 4 further suggests that this issue prevents the implementation from leveraging efficient numerical libraries at large scales.

8. The compared baselines are poorly chosen. Google OR-TOOLS and D-Wave dimod (simulated annealing) are general-purpose heuristics for arbitrary combinatorial optimization problems, not optimized for the 1D case. The algorithm should be compared to baselines specifically designed for the target problem.

9. What is the reason that the algorithm, claimed to find the exact optimal solution, finds a worse solution than the baseline heuristics at smaller problem sizes? Is it because tau is not large enough for those scales?

Reject