How Simplified Models Can Still Lead to Smarter Solutions

Table of Links

I. Introduction

II. Spim Performance, Advantages and Generality

III. Inherently Low Rank Problems

A. Properties of Low Rank Graphs

B. Weakly NP-Complete Problems and Hardware Precision Limitation

C. Limitation of Low Rank Matrix Mapping

IV. Low Rank Approximation

A. Decomposition of Target Coupling Matrix

B. How Fields Influence Ran

C. Low Rank Approximation of Coupling Matrices

D. Low-Rank Approximation of Random Coupling Matrices

E. Low Rank Approximation for Portfolio Optimization

F. Low-Rank Matrices in Restricted Boltzmann Machines

V. Constrained Number Partitioning Problem

A. Definition and Characteristics of the Constrained Number Partitioning Problem

B. Computational Hardness of Random CNP Instances

VI. Translation Invariant Problems

A. “Realistic” Spin Glass

B. Circulant Graphs

VII. Conclusions, Acknowledgements, and References

IV. LOW RANK APPROXIMATION

Building on our understanding of low-rank problems, this section explores the practical application of low-rank approximations.

A. Decomposition of Target Coupling Matrix

B. How Fields Influence Rank

Ising-type problems with a magnetic field (i.e., a term linear in the spins in the Hamiltonian) can be reduced to a problem without a field by adding an auxiliary spin. If the initial Hamiltonian is

then the corresponding Hamiltonian without field is

C. Low Rank Approximation of Coupling Matrices

Given any Ising problem with external fields, we can convert it into another Ising problem with no external field and a coupling matrix with a rank at most two higher. We can then use SVD to decompose the resultant coupling matrix into the linear combination of Mattis-type matrices. This decomposition, in general, produces N terms, where N is the dimension of the coupling matrix, and the precision of each term is not bounded. Under low-rank approximation, we retain only the K largest λk terms in the sum produced by SVD, i.e.

D. Low-Rank Approximation of Random Coupling Matrices

Figure 1 compares the quality of solutions obtained using varying values of K and L. Figures 1(a) and (b) show results from the low-rank, limited-precision approximation of a random 1000-vertex unweighted connectivity graph, where each pair of vertices has an equal probability of being connected or unconnected. Figures 1(c) and (d) show results from a sparse 3-regular random graph, where each vertex is connected to 3 other random vertices. From Figs. 1(a) and (c), we observe that the quality of solutions obtained from 8-bit precision approximations is indistinguishable from solutions obtained from full-precision calculations, regardless of the rank of the approximate coupling matrix. This suggests that SPIM can still find highly accurate approximate solutions to

Ising problems with both dense and sparse coupling matrices, even with limited precision.

This observation is further supported by Figs. 1(b) and (d). It can be seen that with at least 6 bits of precision, SPIM can find low-energy solutions comparable to those found by full-precision machines using the same algorithm. However, the loss of accuracy is more pronounced in dense graphs than in sparse graphs.

highly dependent on the rank of the approximated coupling matrix. In both dense and sparse graphs, the energy of the approximate solution increases rapidly as the rank of the approximate coupling matrix decreases. Therefore, for a general random matrix, the precision of the Mattis-type matrices is not a significant factor in the quality of the approximate solution, but the rank of the approximate matrix is. The dependence on rank is likely to limit the efficiency of SPIM hardware on random Ising problems because the computation of Ising energy contributions from each rank-1 component by SPIM must be time-multiplexed, leading to much longer computation times per iteration.

In Section IV E, we discuss a practical application in finance where a low-rank matrix can often approximate the matrix in question, making it suitable for implementhe matrix in question, making it suitable for implementation in SPIM hardware.