Statistical mechanical models of integer factorization problem

Abstract

We formulate the integer factorization problem via a formulation of the searching problem for the ground state of a statistical mechanical Hamiltonian. The first passage time required to find a correct divisor of a composite number signifies the exponential computational hard- ness. Analysis of the density of states of two macroscopic quantities, i.e. the energy and the Hamming distance from the correct solutions, leads to the conclusion that the ground state (the correct solution) is completely isolated from the other low energy states, with the distance being proportional to the system size. In addition, the profile of the microcanonical entropy of the model has two peculiar features which are each related to two dramatic changes in the energy region sampled via Monte Carlo simulation or simulated annealing. Hence, we find a peculiar first-order phase transition in our model.

arXiv comment21 pages, 14 figures

References in corpus (18)

• An efficient, multiple range random walk algorithm to calculate the density of states
• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Quantum Annealing in the Transverse Ising Model
• Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Mathematical Foundation of Quantum Annealing
• Phase Transition in the Number Partitioning Problem
• First order phase transition in the Quantum Adiabatic Algorithm
• Quantum annealing with antiferromagnetic fluctuations
• Simple Glass Models and their Quantum Annealing
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Quantum Effects in Neural Networks
• Quantum annealing with Jarzynski equality
• Energy gap at first-order quantum phase transitions: An anomalous case
• Nonequilibrium work on spin glasses in longitudinal and transverse fields
• Solution-space structure of (some) optimization problems
• Nonequilibrium work performed in quantum annealing
• Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers