Table of Links I. Introduction I. Introduction Introduction II. Spim Performance, Advantages and Generality II. Spim Performance, Advantages and Generality II. Spim Performance, Advantages and Generality III. Inherently Low Rank Problems III. Inherently Low Rank Problems A. Properties of Low Rank Graphs A. Properties of Low Rank Graphs B. Weakly NP-Complete Problems and Hardware Precision Limitation B. Weakly NP-Complete Problems and Hardware Precision Limitation C. Limitation of Low Rank Matrix Mapping C. Limitation of Low Rank Matrix Mapping IV. Low Rank Approximation IV. Low Rank Approximation A. Decomposition of Target Coupling Matrix A. Decomposition of Target Coupling Matrix B. How Fields Influence Ran B. How Fields Influence Ran C. Low Rank Approximation of Coupling Matrices C. Low Rank Approximation of Coupling Matrices D. Low-Rank Approximation of Random Coupling Matrices D. Low-Rank Approximation of Random Coupling Matrices E. Low Rank Approximation for Portfolio Optimization E. Low Rank Approximation for Portfolio Optimization F. Low-Rank Matrices in Restricted Boltzmann Machines F. Low-Rank Matrices in Restricted Boltzmann Machines V. Constrained Number Partitioning Problem V. Constrained Number Partitioning Problem A. Definition and Characteristics of the Constrained Number Partitioning Problem A. Definition and Characteristics of the Constrained Number Partitioning Problem B. Computational Hardness of Random CNP Instances B. Computational Hardness of Random CNP Instances VI. Translation Invariant Problems VI. Translation Invariant Problems A. “Realistic” Spin Glass A. “Realistic” Spin Glass B. Circulant Graphs B. Circulant Graphs VII. Conclusions, Acknowledgements, and References VII. Conclusions, Acknowledgements, and References VII. Conclusions, Acknowledgements, and References B. Computational Hardness of Random CNP Instances As the number of integers N in a CNP problem increases, the probability of finding a perfect partition will undergo a phase transition from 0 to 1, but the critical value of Nc where this happens is expected to increase as bias S of the problem increases because it is increasingly challenging to balance the sums in each subset while fulfilling the constraint of greater cardinality difference. This trend is observed in Fig. 3(a). A complete picture of the phase transition landscape is shown in Fig. 3(b), which is the probability of the existence of a perfect solution in a random CNP problem with various numbers of integers N and bias S. We can observe a “hard” phase in which the probability of a perfect solution’s existence is low (labelled as region 2 in the colour map) and a “perfect” phase in which the probability of a perfect solution’s existence is close to 1 (labelled as region 3). It can be observed that the phase transition between the “hard” and “perfect” phases is not sharp, and there exists an intermediate region where the probability of a perfect solution being present is neither close to 0 nor 1. This can be attributed to the finite system size N. Unlike the theoretical studies presented in [60], which depicts the asymptotic behaviour when N → ∞, this phase diagram models a finite system implementable in SPIM hardware. From the phase diagram, we observe that region 2, where the probability of a perfect solution’s existence is close to 0, extends into N values much greater than L = 12 used in the simulation. Hence, this numerical experiment suggests that it is possible to realize CNP problem instances with size N much greater than hardware precision L on SPIM and still keep the parameters in region 2, where the probability of a perfect solution being present is very low. c Next, we must understand if problem instances in region 2 represent computationally hard instances. The existing state-of-the-art pseudo-polynomial time algorithm for number partitioning problems is the complete differencing algorithm [38]. As shown in Fig. 4, the algorithm performs the search in a depth-first manner through a tree. The root comprises all integers in a descending order. At each node with more than one element, the node leads to new branches. The left branch takes the difference of the first two elements of the parent node, denoting the decision to assign the two leading elements into two different subsets. The right branch takes the sum of the first two elements of the parent node, denoting the decision to assign the two leading elements to the same subset. The only integer in each leaf node indicates the final discrepancy corresponding to the partition defined by the route from the root to the leaf. Here, we investigate two versions of the CNP problem. The first is a decision problem: given a CNP instance, determine if a perfect solution exists. The complete differencing algorithm was adapted by enforcing the bias constraint and then used on many random CNP problem instances with given size N and bias S. The number of possible configurations that must be searched before the determination can be made is shown in Fig. 5(a). It can be observed that the number of searched configurations first increases exponentially with N before hitting a peak. We note that the average hardness of problems, as indicated by the number of configurations searched, peaks at around the same time as the phase transition from the "hard" phase to the "perfect" phase shown in Fig. 3(a). This is because if a perfect solution exists, the algorithm can locate it early on without searching the entire configuration space. If no perfect solution exists, the algorithm will likely have to search most part of the configuration space to rule it out. Hence, our numerical test shows that CNP and NPP are likely to behave similarly, with the existence of a perfect solution correlated with the problem being easy. The second version of CNP problems we investigate is a harder optimization problem: given a CNP instance, find the best partition, regardless of whether it is perfect. Figure 5(b) shows the degenerate ground states in randomly generated CNP problem instances with different bias parameters b = S/N but with fixed precision L = 12. When N is smaller than L, it can be observed that the number of degenerate ground states did not grow exponentially with N for all values of bias ratio parameters b, which corresponds to the lower-left corner of region 2 in Fig. 3(b). When N is larger than L, the number of degenerate ground states grows exponentially with N for smaller values of b. For the largest considered b value of 0.4, the number of degenerate ground states is approximately constant by an order of magnitude, even as the total solution space grows exponentially with N. This strongly suggests that for the largest bias ratio b value, the problem remains computationally hard even as N grows while the precision L is fixed. Hence, random CNP problems with large bias ratio values can be meaningful benchmark problems for testing the performance of SPIM hardware in solving computationally hard problems because they have limited precision requirements and can be mapped to an Ising problem with a low-rank coupling matrix, as we show in the following subsection. b S/N N L b N b N N L Authors:
(1) Richard Zhipeng Wang, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom;
(2) James S. Cummins, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom;
(3) Marvin Syed, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom;
(4) Nikita Stroev, Department of Physics of Complex Systems, Weizmann Institute of Science, Rehovot 76100, Israel;
(5) George Pastras, QUBITECH, Thessalias 8, Chalandri, GR 15231 Athens, Greece;
(6) Jason Sakellariou, QUBITECH, Thessalias 8, Chalandri, GR 15231 Athens, Greece;
(7) Symeon Tsintzos, QUBITECH, Thessalias 8, Chalandri, GR 15231 Athens, Greece and UBITECH ltd, 95B Archiepiskopou Makariou, CY 3020 Limassol, Cyprus;
(8) Alexis Askitopoulos, QUBITECH, Thessalias 8, Chalandri, GR 15231 Athens, Greece and UBITECH ltd, 95B Archiepiskopou Makariou, CY 3020 Limassol, Cyprus;
(9) Daniele Veraldi, Department of Physics, University Sapienza, Piazzale Aldo Moro 5, Rome 00185, Italy;
(10) Marcello Calvanese Strinati, Research Center Enrico Fermi, Via Panisperna 89A, 00185 Rome, Italy;
(11) Silvia Gentilini, Institute for Complex Systems, National Research Council (ISC-CNR), Via dei Taurini 19, 00185 Rome, Italy;
(12) Calvanese Strinati, Research Center Enrico Fermi, Via Panisperna 89A, 00185 Rome, Italy
(13) Davide Pierangeli, Institute for Complex Systems, National Research Council (ISC-CNR), Via dei Taurini 19, 00185 Rome, Italy;
(14) Claudio Conti, Department of Physics, University Sapienza, Piazzale Aldo Moro 5, Rome 00185, Italy;
(15) Natalia G. Berlof, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom (N.G.Berloff@damtp.cam.ac.uk). Authors: Authors: (1) Richard Zhipeng Wang, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom; (2) James S. Cummins, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom; (3) Marvin Syed, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom; (4) Nikita Stroev, Department of Physics of Complex Systems, Weizmann Institute of Science, Rehovot 76100, Israel; (5) George Pastras, QUBITECH, Thessalias 8, Chalandri, GR 15231 Athens, Greece; (6) Jason Sakellariou, QUBITECH, Thessalias 8, Chalandri, GR 15231 Athens, Greece; (7) Symeon Tsintzos, QUBITECH, Thessalias 8, Chalandri, GR 15231 Athens, Greece and UBITECH ltd, 95B Archiepiskopou Makariou, CY 3020 Limassol, Cyprus; (8) Alexis Askitopoulos, QUBITECH, Thessalias 8, Chalandri, GR 15231 Athens, Greece and UBITECH ltd, 95B Archiepiskopou Makariou, CY 3020 Limassol, Cyprus; (9) Daniele Veraldi, Department of Physics, University Sapienza, Piazzale Aldo Moro 5, Rome 00185, Italy; (10) Marcello Calvanese Strinati, Research Center Enrico Fermi, Via Panisperna 89A, 00185 Rome, Italy; (11) Silvia Gentilini, Institute for Complex Systems, National Research Council (ISC-CNR), Via dei Taurini 19, 00185 Rome, Italy; (12) Calvanese Strinati, Research Center Enrico Fermi, Via Panisperna 89A, 00185 Rome, Italy (13) Davide Pierangeli, Institute for Complex Systems, National Research Council (ISC-CNR), Via dei Taurini 19, 00185 Rome, Italy; (14) Claudio Conti, Department of Physics, University Sapienza, Piazzale Aldo Moro 5, Rome 00185, Italy; (15) Natalia G. Berlof, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom (N.G.Berloff@damtp.cam.ac.uk). This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Computational Hardness of Random CNP Instances

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

What Investors and AI Researchers Can Learn from Low-Rank Optimization

Can Light Solve Problems Faster Than Supercomputers?

Low-Rank Matrices, NP-Hardness, and the Roadblocks to Quantum-Inspired Hardware

How Simplified Models Can Still Lead to Smarter Solutions

Cracking the Constrained Number Partitioning Problem (CNP) with SPIMs

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

What Investors and AI Researchers Can Learn from Low-Rank Optimization

Can Light Solve Problems Faster Than Supercomputers?

Low-Rank Matrices, NP-Hardness, and the Roadblocks to Quantum-Inspired Hardware

How Simplified Models Can Still Lead to Smarter Solutions

Cracking the Constrained Number Partitioning Problem (CNP) with SPIMs

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps