Gain-Based Computing for Solving Optimisation Problems

Abstract

Optimisation problems occur in a plethora of quantitative disciplines including, but not limited to, physics, engineering, biology, finance, and machine learning. However, in solving complex optimisation problems, digital computers are increasingly encountering limitations imposed by their traditional von Neumann architecture. This has led to a resurgence of interest in gain-based analogue computing paradigms, which offer a multitude of advantages including speed, energy-efficiency, and scalability. The innovative analogue approach aims to transcend the conventional computing model's limitations, tapping into the intrinsic computational potential of physical systems to address complex optimisation challenges currently beyond traditional methods' reach. This thesis focuses on the advancement of gain-based analogue algorithms to obtain optimal solutions to a broad class of optimisation problems. Chapter 1 is a literature review of material relevant to analogue gain-based computing. We establish the connection between optimisation problems and spin Hamiltonians, demonstrating how an optimisation problem is encoded in the Hamiltonian structure. We then present a survey of prominent gain-based analogue computer architectures whose physical operation minimises a spin Hamiltonian. Chapter 2 introduces the M"obius ladder graph for Ising Hamiltonians. This is a type of circulant graph with multiple parameter regimes that can be used for benchmarking. We analyse under the gain-based analogue computing paradigm how the energy landscape of this graph evolves with dynamic annealing parameters. We show that gain-based semi-classical soft-spin models face challenges due to a widening dimensionality landscape. To counteract this issue, we introduce the manifold reduction method, which restricts the soft-spin amplitudes to a defined phase space region. Chapter 3 introduces the Vector Ising Spin Annealer (VISA), a framework in gain-based analogue computing that leverages higher-dimensional spaces to address complex optimisation problems. Traditional physical minimisers often select excited states due to limitations in spin dynamics. VISA overcomes these limitations by enabling spins to operate within a three-dimensional space, thereby providing a robust method for effectively minimising Ising Hamiltonians. Our comparative analysis demonstrates VISA's superior performance relative to conventional single-dimension spin optimisers, and highlights its capacity to surmount significant barriers in intricate energy landscapes. Detailed studies on cyclic and random graphs reveal VISA's proficiency in dynamically evolving the energy landscape through time-dependent annealing, underscoring its potential in advancing the field of complex problem-solving with gain-based analogue computing. Chapter 4 introduces the Complex Vector Gain-Based Annealer (CoVeGA). Like VISA, this is a gain-based analogue computing platform for solving optimisation problems. However, CoVeGA operates by minimising XY Hamiltonians, rendering it applicable to optimisation problems with rotational symmetry. CoVeGA uses two complex fields to represent each XY spin, while dynamically evolving the energy landscape through time-dependent annealing. By operating in a higher-dimensional space, CoVeGA bridges energy barriers in this expanded space during the continuous phase evolution, thus avoiding entrapment in local minima. We introduce several graph structures that pose challenges for XY minimisation and use them to benchmark CoVeGA against single-dimension XY solvers, highlighting the benefits of higher-dimensional operation. In Chapter 5 we discuss the application of gain-based analogue computing to portfolio optimisation. Portfolio optimisation is a ubiquitous problem in financial mathematics that relies on accurate covariance matrices. However, estimates of pairwise covariance are notoriously poor and calculating time-sensitive optimal portfolios is energy-intensive for digital computers. We present an energy-efficient, fast, and fully analogue pipeline for solving portfolio optimisation problems that overcomes these limitations. The analogue paradigm leverages the fundamental principles of physics to recover accurate optimal portfolios in a two-step process. Firstly, we utilise equilibrium propagation, an analogue alternative to backpropagation, to train linear autoencoder neural networks to calculate low-rank covariance matrices. Secondly, analogue continuous Hopfield networks output the minimum variance portfolio for a given desired expected return. The entire efficient frontier may then be recovered, and an optimal portfolio selected based on risk appetite. In Chapter 6 we investigate another application of gain-based computing: constraint satisfaction problems. In particular, we consider the NP-complete excluded diagonals N-queens problem due to its computational difficulty and direct relevance to a broad spectrum of real-world applications. We encode the problem constraints into the architecture of optical systems, as described by the Stuart-Landau equation. This gain-based approach is compared to the powerful classical heuristic parallel tempering algorithm. We utilise the time-to-solution metric to analyse and compare the expected time to achieve an N-queens solution when each method is implemented on its natural hardware. This allows us to examine the possibility of an analogue speedup for the N-queens problem.