Prime Factorization Equation from a Tensor Network Perspective

• URL: http://arxiv.org/abs/2508.00907v1
• Date: Tue, 29 Jul 2025 10:38:51 GMT
• Title: Prime Factorization Equation from a Tensor Network Perspective
• Authors: Alejandro Mata Ali, Jorge Martínez Martín, Sergio Muñiz Subiñas, Miguel Franco Hernando, Javier Sedano, Ángel Miguel García-Vico,
• Abstract summary: This paper presents an exact and explicit equation for prime factorization, along with an algorithm for its computation.<n>The proposed method is based on the MeLoCoToN approach, which addresses optimization problems through classical tensor networks.
• Score: 37.037023521034925
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents an exact and explicit equation for prime factorization, along with an algorithm for its computation. The proposed method is based on the MeLoCoToN approach, which addresses combinatorial optimization problems through classical tensor networks. The presented tensor network performs the multiplication of every pair of possible input numbers and selects those whose product is the number to be factorized. Additionally, in order to make the algorithm more efficient, the number and dimension of the tensors and their contraction scheme are optimized. Finally, a series of tests on the algorithm are conducted, contracting the tensor network both exactly and approximately using tensor train compression, and evaluating its performance.

Related papers

• Knapsack and Shortest Path Problems Generalizations From A Quantum-Inspired Tensor Network Perspective [40.5694560588179]
  We present two quantum-inspired algorithms to solve the knapsack and the shortest path problems.<n>The methods provide an exact equation which returns the optimal solution of the problems.
  arXiv  Detail & Related papers  (2025-06-13T12:27:34Z)
• Quick design of feasible tensor networks for constrained combinatorial optimization [1.8775413720750924]
  A quantum-inspired solver using tensor networks has been proposed, which works on classical computers.<n>We numerically constructed a feasible tensor network for facility location problem, to find much faster construction than conventional methods.
  arXiv  Detail & Related papers  (2024-09-03T08:36:23Z)
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
  We introduce a method to efficiently approximate tensor network contractions using low-rank approximations.<n>The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations.
  arXiv  Detail & Related papers  (2024-06-14T07:13:52Z)
• Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
  We introduce an algorithm for data quantization based on the principles of Kashin representation. Our findings demonstrate that Kashin Quantization achieves competitive or superior quality in model performance.
  arXiv  Detail & Related papers  (2024-04-15T12:38:46Z)
• Tensor Completion via Integer Optimization [7.813563137863005]
  The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution. This paper develops a novel tensor completion algorithm that resolves this tension by achieving both provable convergence (in numerical tolerance) in a linear number of oracle steps and the information-theoretic rate.
  arXiv  Detail & Related papers  (2024-02-06T21:44:07Z)
• TERM Model: Tensor Ring Mixture Model for Density Estimation [48.622060998018206]
  In this paper, we take tensor ring decomposition for density estimator, which significantly reduces the number of permutation candidates. A mixture model that incorporates multiple permutation candidates with adaptive weights is further designed, resulting in increased expressive flexibility. This approach acknowledges that suboptimal permutations can offer distinctive information besides that of optimal permutations.
  arXiv  Detail & Related papers  (2023-12-13T11:39:56Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning [58.14930566993063]
  We present connections between three models used in different research fields: weighted finite automata(WFA) from formal languages and linguistics, recurrent neural networks used in machine learning, and tensor networks. We introduce the first provable learning algorithm for linear 2-RNN defined over sequences of continuous vectors input.
  arXiv  Detail & Related papers  (2020-10-19T15:28:00Z)
• Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
  Efficient modelling of feature interactions underpins supervised learning for non-sequential tasks. To alleviate this issue, it has been proposed to implicitly represent the model parameters as a tensor. For enhanced expressiveness, we generalize the framework to allow feature mapping to arbitrarily high-dimensional feature vectors.
  arXiv  Detail & Related papers  (2020-01-27T22:38:40Z)
• Algorithms for Tensor Network Contraction Ordering [0.0]
  Well-designed contraction sequences can dramatically reduce the contraction cost. We benchmark two common discrete optimization techniques to this ordering problem. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources.
  arXiv  Detail & Related papers  (2020-01-15T19:00:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.