Complexity continuum within Ising formulation of NP problems
- URL: http://arxiv.org/abs/2008.00466v1
- Date: Sun, 2 Aug 2020 11:36:38 GMT
- Title: Complexity continuum within Ising formulation of NP problems
- Authors: Kirill P. Kalinin and Natalia G. Berloff
- Abstract summary: Minimisation of the Ising Hamiltonian is known to be NP-hard problem for certain interaction matrix classes.
We propose to identify computationally simple instances with an optimisation simplicity criterion'
Such simplicity can be found for a wide range of models from spin glasses to k-regular maximum cut problems.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.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.
Related papers
- Quantum Vision Clustering [10.360126989185261]
We present the first clustering formulation tailored for resolution using Adiabatic quantum computing.
The proposed approach demonstrates high competitiveness compared to state-of-the-art optimization-based methods.
This work showcases the solvability of the proposed clustering problem on current-generation real quantum computers for small examples.
arXiv Detail & Related papers (2023-09-18T16:15:16Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics.
One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space.
In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization.
We provide novel excess risk bounds, both in expectation and with high probability.
Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
arXiv Detail & Related papers (2022-11-03T12:40:24Z) - Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
Book presents several efforts to tackle this challenge with important scientific implications.
It provides alternative optimization schemes that scale well in terms of computational complexity.
We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems.
arXiv Detail & Related papers (2022-08-23T18:56:05Z) - A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms [18.075115172621096]
We present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs via Ising solvers.
We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm.
arXiv Detail & Related papers (2022-07-27T16:47:32Z) - Ising machines as hardware solvers of combinatorial optimization
problems [1.8732539895890135]
Ising machines are hardware solvers which aim to find the absolute or approximate ground states of the Ising model.
A scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications.
arXiv Detail & Related papers (2022-04-01T08:24:06Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems.
Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem.
Our results show the effectiveness of this construction and potential applications.
arXiv Detail & Related papers (2022-03-29T05:44:07Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
Most datasets only capture a simpler subproblem and likely suffer from spurious features.
We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features.
Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound.
Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
arXiv Detail & Related papers (2021-10-21T07:28:11Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
We propose a generalization extraient spaces which converges to a stationary point.
The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
arXiv Detail & Related papers (2020-10-31T21:35:42Z) - The limits of min-max optimization algorithms: convergence to spurious
non-critical sets [82.74514886461257]
min-max optimization algorithms encounter problems far greater because of the existence of periodic cycles and similar phenomena.
We show that there exist algorithms that do not attract any points of the problem.
We illustrate such challenges in simple to almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost
arXiv Detail & Related papers (2020-06-16T10:49:27Z)
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.