Computational complexity continuum within Ising formulation of NP problems

cam.depositDate2021-12-14
cam.issuedOnline2022-01-12
cam.orpheus.counter6
cam.orpheus.success2022-05-18
dc.contributor.authorKalinin, Kirill P
dc.contributor.authorBerloff, Natalia G
dc.contributor.orcidBerloff, Natalia [0000-0003-2114-4321]
dc.date.accessioned2021-12-18T00:30:22Z
dc.date.available2021-12-18T00:30:22Z
dc.date.issued2022
dc.date.updated2021-12-14T18:50:50Z
dc.description.abstractA 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.
dc.identifier.doi10.17863/CAM.79052
dc.identifier.issn2399-3650
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/331600
dc.publisherNature Research
dc.publisher.departmentDepartment of Applied Mathematics And Theoretical Physics
dc.publisher.urlhttps://www.nature.com/articles/s42005-021-00792-0#rightslink
dc.rightsCreative Commons CC BY 4.0
dc.rights.urihttp://www.rioxx.net/licenses/CC BY 4.0
dc.subjectquant-ph
dc.subjectquant-ph
dc.subjectcond-mat.stat-mech
dc.subjectcs.CC
dc.subjectcs.ET
dc.subjectphysics.comp-ph
dc.titleComputational complexity continuum within Ising formulation of NP problems
dc.typeArticle
dcterms.dateAccepted2021-12-14
prism.publicationDate
prism.publicationNameCOMMUNICATIONS PHYSICS
prism.volume
pubs.licence-display-nameApollo Repository Deposit Licence Agreement
pubs.licence-identifierapollo-deposit-licence-2-1
rioxxterms.typeJournal Article/Review
rioxxterms.versionVoR
rioxxterms.versionofrecord10.1038/s42005-021-00792-0
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Computational complexity continuum within Ising formulation of NP problems.pdf
Size:
1.62 MB
Format:
Adobe Portable Document Format
Description:
Published version
Licence
http://www.rioxx.net/licenses/CC BY 4.0