Computational complexity continuum within Ising formulation of NP problems
View / Open Files
Publication Date
2022-01-12Journal Title
COMMUNICATIONS PHYSICS
ISSN
2399-3650
Publisher
Nature Research
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Kalinin, K. P., & Berloff, N. (2022). Computational complexity continuum within Ising formulation of NP problems. COMMUNICATIONS PHYSICS, https://doi.org/10.1038/s42005-021-00792-0
Abstract
A promising approach to achieve computational supremacy over the classical
von Neumann architecture explores classical and quantum hardware as Ising
machines. The minimisation of the Ising Hamiltonian is known to be NP-hard
problem for certain interaction matrix classes, yet not all problem instances
are equivalently hard to optimise. We propose to identify computationally
simple instances with an `optimisation simplicity criterion'. Such optimisation
simplicity can be found for a wide range of models from spin glasses to
k-regular maximum cut problems. Many optical, photonic, and electronic systems
are neuromorphic architectures that can naturally operate to optimise problems
satisfying this criterion and, therefore, such problems are often chosen to
illustrate the computational advantages of new Ising machines. We further probe
an intermediate complexity for sparse and dense models by analysing circulant
coupling matrices, that can be `rewired' to introduce greater complexity. A
compelling approach for distinguishing easy and hard instances within the same
NP-hard class of problems can be a starting point in developing a standardised
procedure for the performance evaluation of emerging physical simulators and
physics-inspired algorithms.
Keywords
quant-ph, quant-ph, cond-mat.stat-mech, cs.CC, cs.ET, physics.comp-ph
Identifiers
External DOI: https://doi.org/10.1038/s42005-021-00792-0
This record's URL: https://www.repository.cam.ac.uk/handle/1810/331600
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.