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

Aitor Moreno Fdez. de Leceta; Alejandro Mata Ali; I\~nigo Perez Delgado; Marina Ristol Roura

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2309.10509 v4 pith:WT4OJ4PV submitted 2023-09-19 quant-ph cs.ET

Alejandro Mata Ali , Iñigo Perez Delgado , Marina Ristol Roura , Aitor Moreno Fdez. de Leceta This is my paper · ORCID

classification quant-phcs.ET

keywords problemstensoralgorithmsoptimizationquadraticqudounconstrainedalgorithm

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

We present a quantum-inspired tensor network algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and quadratic unconstrained discrete optimization (QUDO) problems. We also solve the more general Tensor quadratic unconstrained discrete optimization (T-QUDO) problems with one-neighbor interactions in a lineal chain. This method provides an exact and explicit equation for these problems. Our algorithms are based on the simulation of a state that undergoes imaginary time evolution and a Half partial trace. In addition, we address the degenerate case and evaluate the polynomial complexity of the algorithm, also providing a parallelized version. We implemented and tested them with other well-known classical algorithms and observed an improvement in the quality of the results. The performance of the proposed algorithms is compared with the Google OR-TOOLS and dimod solvers, improving their results.

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

Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN
cs.ET 2025-02 reject novelty 4.0 of 10

Any finite combinatorial problem with a known logical circuit can be encoded as a tensor network whose contraction defines an explicit, though generally inefficient, solution equation.

Pith tools