Prime Factorization Equation from a Tensor Network Perspective

Abstract

This paper presents an exact and explicit tensor-network equation for the search of nontrivial divisors of a composite integer, together 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 tensorizes a binary multiplication circuit and projects its output onto the target integer 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, including a reduced auxiliary register that still preserves at least one valid factorization orientation. 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.