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
VII. CONCLUSIONS
SPIMs are emerging physical computing platforms with distinct strengths and practical constraints, setting them apart from conventional digital computing technologies. As advancements in engineering and materials technology continue, these platforms are expected to see enhanced capabilities. It is, however, imperative to identify problems and methods that can effectively utilize these unique strengths, providing a robust basis for benchmarking their performance. This paper identifies several classes of problems that are particularly well-suited for SPIM hardware. SPIMs are shown to efficiently address practical problems such as portfolio optimization through low-rank approximation techniques. This methodology also presents promising opportunities for further research, including the potential implementation of low-rank restricted Boltzmann machines on SPIMs. Furthermore, the constrained number partitioning (CNP) problem, a variation of the classic number partitioning problem, serves as a valuable benchmark for comparing the performance of SPIMs with that of classical computers. The analytically solvable circulant graph provides insights into the differences in performance between gradient-based algorithms, prevalent in many current Ising machines, and sampling-based algorithms that can be implemented on SPIMs. Additionally, SPIMs have the potential to realize many “realistic” spin glasses, extensively studied within the realm of statistical mechanics, thereby making numerous theoretical models experimentally viable.
Our study also highlights the importance of precision and rank in relation to the constraints of SPIM hardware. While low-rank approximations can render problems more manageable on SPIMs, the precision required for these approximations can impact computational efficiency and the accuracy of solutions. Therefore, future research must explore methods to optimize the balance between rank and precision. Beyond portfolio optimization and Boltzmann machines, SPIMs demonstrate potential in solving various NP-hard problems through innovative mapping techniques. Advanced decomposition methods, such as singular value decomposition (SVD), enable SPIMs to manage more complex coupling matrices, expanding their applicability across different optimization tasks.
In conclusion, SPIMs represent a promising advancement in computational technologies. By focusing on lowrank approximations, constrained number partitioning, and the implementation of sophisticated algorithms, this paper sets the stage for future investigations into the capabilities and applications of SPIMs. Continued research and development in this area are crucial for fully realizing the potential of SPIMs, paving the way for novel solutions to some of the most challenging computational problems. The broader implications of this research extend to fields such as finance, logistics, and data science, where SPIMs could significantly enhance performance and efficiency, leading to substantial advancements.
ACKNOWLEDGEMENTS
R.Z.W. M.S. G.P. J.S. A.A. S.T. C.C. D.P. S.G. M.C.S. D.V. and N.G.B. acknowledge support from HORIZON EIC-2022-PATHFINDERCHALLENGES-01 HEISINGBERG Project 101114978. R.Z.W. and N.G.B. acknowledge the support from the Julian Schwinger Foundation Grant No. JSF-19-02-0005. J.S.C. acknowledges the PhD support from the EPSRC. N.S. and N.G.B. acknowledge support from Weizmann-UK Make Connection Grant 142568. N.S. acknowledges the support provided by the Clore Fellowship. A.A. and S.T. acknowledge support from HoloCIM (CODEVELOP-ICTHEALTH/0322/0047).
[1] G. Naseri and M. A. G. Koffas, Nature Communications 11, 2446 (2020).
[2] C. A. Nicolaou and N. Brown, Drug Discovery Today: Technologies 10, e427 (2013).
[3] C. Gambella, B. Ghaddar, and J. Naoum-Sawaya, European Journal of Operational Research 290, 807 (2021).
[4] L. Kotthoff, H. Wahab, and P. Johnson, “Bayesian Optimization in Materials Science: A Survey,” (2021), arxiv:2108.00002 [cond-mat, physics:physics].
[5] Y. Zhang, D. W. Apley, and W. Chen, Scientific Reports 10, 4924 (2020).
[6] V. Paschos, Applications of Combinatorial Optimization, 2nd Edition Paschos, Vangelis., 2nd ed. (Wiley-ISTE, 2014., 2014).
[7] S. Samsi, D. Zhao, J. McDonald, B. Li, A. Michaleas, M. Jones, W. Bergeron, J. Kepner, D. Tiwari, and V. Gadepally, “From Words to Watts: Benchmarking the Energy Costs of Large Language Model Inference,” (2023), arxiv:2310.03003 [cs].
[8] N. G. Berloff, M. Silva, K. Kalinin, A. Askitopoulos, J. D. Töpfer, P. Cilibrizzi, W. Langbein, and P. G. Lagoudakis, Nature Materials 16, 1120 (2017).
[9] P. G. Lagoudakis and N. G. Berloff, New Journal of Physics 19, 125008 (2017).
[10] K. P. Kalinin and N. G. Berloff, New Journal of Physics 20, 113023 (2018).
[11] A. Opala, S. Ghosh, T. C. Liew, and M. Matuszewski, Physical Review Applied 11, 064029 (2019).
[12] A. Opala, R. Panico, V. Ardizzone, B. Piętka, J. Szczytko, D. Sanvitto, M. Matuszewski, and D. Ballarini, Physical Review Applied 18, 024028 (2022).
[13] F. C. Hoppensteadt and E. M. Izhikevich, Physical Review E 62, 4010 (2000).
[14] V. Pal, C. Tradonsky, R. Chriki, A. A. Friesem, and N. Davidson, Physical Review Letters 119, 013902 (2017).
[15] D. Pierangeli, G. Marcucci, and C. Conti, Physical review letters 122, 213902 (2019).
[16] T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K.-i. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, Science 354, 603 (2016).
[17] Y. Yamamoto, K. Aihara, T. Leleu, K.-i. Kawarabayashi, S. Kako, M. Fejer, K. Inoue, and H. Takesue, NPJ quantum information 3, 1 (2017).
[18] T. Honjo, T. Sonobe, K. Inaba, T. Inagaki, T. Ikuta, Y. Yamada, T. Kazama, K. Enbutsu, T. Umeki, R. Kasahara, K.-i. Kawarabayashi, and H. Takesue, Science Advances 7, eabh0952 (2021).
[19] A. Lucas, Frontiers in physics 2, 74887 (2014).
[20] D. Pierangeli, M. Rafayelyan, C. Conti, and S. Gigan, Physical Review Applied 15, 034087 (2021).
[21] D. Pierangeli, G. Marcucci, and C. Conti, Optica, OPTICA 7, 1535 (2020).
[22] D. Pierangeli, G. Marcucci, and C. Conti, Physical Review Letters 122, 213902 (2019).
[23] W. Sun, W. Zhang, Y. Liu, Q. Liu, and Z. He, Optics Letters 47, 1498 (2022), arxiv:2105.09307 [physics].
[24] J. Huang, Y. Fang, and Z. Ruan, Communications On Physics 4, 242 (2021).
[25] H. Yamashita, K.-i. Okubo, S. Shimomura, Y. Ogura, J. Tanida, and H. Suzuki, Physical Review Letters 131, 063801 (2023).
[26] A. Lucas, Front. Physics 2 (2014), 10.3389/fphy.2014.00005, arxiv:1302.5843 [cond-mat, physics:quant-ph].
[27] D. Pierangeli, G. Marcucci, and C. Conti, Optica 7, 1535 (2020).
[28] X. Ye, W. Zhang, S. Wang, X. Yang, and Z. He, (2023).
[29] A. Prabhakar, P. Shah, U. Gautham, V. Natarajan, V. Ramesh, N. Chandrachoodan, and S. Tayur, Philosophical Transactions of the Royal Society A 381, 20210409 (2023).
[30] H. Yamashita, K.-i. Okubo, S. Shimomura, Y. Ogura, J. Tanida, and H. Suzuki, Physical Review Letters 131, 063801 (2023).
[31] “Computational power consumption and speedup,” (2017), d-WAVE White Paper. [
32] B. B. Ivan Gutman, Zbornik Radova , 137 (2011).
[33] S. M. Fallat and L. Hogben, Linear Algebra and its Applications 426, 558 (2007).
[34] F. Hamze, J. Raymond, C. A. Pattison, K. Biswas, and H. G. Katzgraber, Physical Review E 101, 052102 (2020).
[35] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., 1990).
[36] S. Mertens, Physical Review Letters 81, 4281 (1998).
[37] C. Borgs, J. Chayes, and B. Pittel, Random Structures & Algorithms 19, 247 (2001).
[38] S. Mertens, “The easiest hard problem: Number partitioning,” in Computational Complexity and Statistical Physics (Oxford University Press, 2005) Chap. 5.
[39] H. Bauke, S. Mertens, and A. Engel, Physical review letters 90, 158701 (2003).
[40] F.-Y. Wu, Reviews of modern physics 54, 235 (1982).
[41] A. Blum, J. Hopcroft, and R. Kannan, Foundations of Data Science (Cambridge University Press, Cambridge, 2020).
[42] A. Frieze and R. Kannan, Combinatorica. An International Journal on Combinatorics and the Theory of Computing 19, 175 (1999).
[43] H. Markowitz, The Journal of Finance 7, 77 (1952), 2975974.
[44] M. Gilli, D. Maringer, and E. Schumann, Numerical Methods and Optimization in Finance (Academic Press, 2019).
[45] JE. Beasley, in Theory Driven by Influential Applications (Informs, 2013) pp. 201–221.
[46] M. A. Elbannan, International Journal of Economics and Finance 7, 216 (2015).
[47] K. P. Kalinin, G. Mourgias-Alexandris, H. Ballani, N. G. Berloff, J. Clegg, D. Cletheroe, C. Gkantsidis, I. Haller, V. Lyutsarev, F. Parmigiani, et al., arXiv preprint arXiv:2304.12594 (2023), arxiv:2304.12594.
[48] T.-m. Chow, J. Hsu, V. Kalesnik, and B. Little, Financial Analysts Journal 67, 37 (2011).
[49] R. K. Narang, Inside the Black Box: A Simple Guide to Quantitative and High Frequency Trading, Vol. 846 (John Wiley & Sons, 2013).
[50] A. Swade, S. Nolte, M. Shackleton, and H. Lohre, The Journal of Portfolio Management 49, 167 (2023).
[51] N. J. Higham, IMA journal of Numerical Analysis 22, 329 (2002).
[52] R. Zhou, J. Ying, and D. P. Palomar, IEEE Transactions on Signal Processing 70, 4020 (2022).
[53] D. Bertsimas, M. S. Copenhaver, and R. Mazumder, The Journal of Machine Learning Research 18, 907 (2017).
[54] J. Brogaard, T. Hendershott, and R. Riordan, The Review of Financial Studies 27, 2267 (2014).
[55] P. Filipiak and P. Lipinski, in Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, the Netherlands, April 19-21, 2017, Proceedings, Part I 20 (Springer, 2017) pp. 34–50.
[56] P. Smolensky, in Parallel Distributed Processing, Volume 1: Explorations in the Microstructure of Cognition: Foundations (The MIT Press, 1986).
[57] G. E. Hinton, Neural computation 14, 1771 (2002).
[58] R. Salakhutdinov, A. Mnih, and G. Hinton, in Proceedings of the 24th International Conference on Machine Learning (2007) pp. 791–798.
[59] I. P. Gent and T. Walsh, in 12th European Conference on Artificial Intelligence, Budapest, Hungary, August 11-16, 1996, Proceedings, edited by W. Wahlster (John Wiley and Sons, Chichester, 1996) pp. 170–174.
[60] C. Borgs, J. T. Chayes, S. Mertens, and B. Pittel, “Phase diagram for the constrained integer partitioning problem,” (2003), arxiv:cond-mat/0302536.
[61] S. Mertens, “A complete anytime algorithm for balanced number partitioning,” (1999), arxiv:cs/9903011.
[62] S. F. Edwards and P. W. Anderson, Journal of Physics F: Metal Physics 5, 965 (1975).
[63] D. L. Stein and C. M. Newman, in Spin Glasses and Complexity (Princeton University Press, 2013).
[64] M. A. Ruderman and C. Kittel, Physical Review 96, 99 (1954).
[65] T. Kasuya, Progress of Theoretical Physics 16, 45 (1956).
[66] K. Yosida, Physical Review 106, 893 (1957).
[67] E. Dagotto and A. Moreo, Physical Review Letters 63, 2148 (1989).
[68] H. A. Ceccatto, C. J. Gazza, and A. E. Trumper, Physical Review B 45, 7832 (1992).
[69] J. S. Cummins, H. Salman, and N. G. Berloff, arXiv preprint arXiv:2311.17359 (2023).
:::info
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 ([email protected]).
:::
:::info
This paper is available on arxiv under CC BY 4.0 DEED license.
:::
