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 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. N N k 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 K L 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. 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.

How Simplified Models Can Still Lead to Smarter Solutions

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

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

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps