Load Balancing For High Performance Computing Using Quantum Annealing: Quantum Annealing

Table of Links

Abstract and Introduction

Methods

• Quantum Annealing
• Adaptive Mesh Refinement
• Smoothed Particle Hydrodynamics

Results

• Grid Based Application
• Particle Based Application

Conclusions and Outlook, Acknowledgements, and References

Quantum Annealing

Of the myriad possibilities[42] when it comes to implementing a quantum computer, currently the two leading paradigms are gate based quantum computing (QC)[43, 44] and adiabatic quantum computing (AQC)[45, 46]. In principle the two approaches have been shown[47] to be equivalent if allowing a polynomial overhead. Gate based QC can be thought of as the quantum analogue to classical computing where instead of logical gates acting on bits, the computation is performed by applying unitary gates to qubits. Alternatively, AQC relies on adiabatic time evolution of a quantum state from an initial, easy to prepare state to a final observed value as modelled by the Schrödinger equation.

Moreover by operating under the umbrella of the adiabatic theorem, the protocol is guaranteed to obtain the ground state solution, at least in theory. However, in practice the requirements of true adiabacity and changing the Hamiltonian slowly enough can be excessively stringent. This is clearly evident in current architecture where thermal coupling with the environment is strong enough such that the timescales are of the order ∼ 10−100ns[53]. Furthermore the requirements on how quickly the Hamiltonian can be evolved (i.e. the annealing schedule) is dependant on the gap between the ground state and first excited solution, which is not usually known a priori.

QA is thus a relaxation of these conditions that follows the same principles as AQC, but forms a distinctly separate algorithm, with the annealing schedule determined heuristically and strictly adiabatic conditions not guaranteed. The same time dependant Hamiltonian of Equation 1 is used to evolve the quantum state, however the system can no longer accurately be modeled by the Schrödinger equation, but would require master-equation based descriptions. As a result, QA forms a heuristic quantum algorithm that should be viewed as a statistical sampler rather than a deterministic solver, with the intended goal of maintaining a relatively high probability of remaining in the ground state or to at least be sufficiently close. The theory of quantum annealing is much less developed than AQC, partially due to the more complex setting. However, some progress has been made, for example in the topic of diabatic computing which considers rapid quenches far from the adiabatic limit[54]. In particular, in this regime a mechanism related to energy conservation provides an important guarantee on average optimality[55].

The expectation that Quantum Annealing (QA) might surpass classical algorithms is tied to the potential impact of quantum mechanical phenomena such as superposition, tunneling, and entanglement[31], [45] [57–59]. Fundamentally, quantum superposition and tunneling can enable transitions between states, even those separated by high energy barriers[60]. This suggests that a search algorithm utilizing QA could overcome local minima more easily by tunneling through these energy barriers as illustrated in Figure 1.

QA is thus grounded in a model that more closely reflects the behavior of real quantum systems when compared to AQC. However, the potential for non-adiabatic effects complicates the distinction between its computational complexity and that of conventional computing. QA often involves the non-adiabatic evolution of mixed quantum states within an open system, and this approach is generally considered heuristic. Thus, it lacks the provable computational advantages that AQC provides[61].

The general approach to employing a quantum annealer shares many similarities across different architectures. This research, however, utilises D-Wave systems, which consist of superconducting qubits. Although there are several promising alternatives[62–64], these technologies are comparatively nascent in their development. Meanwhile D-Wave is the largest and most commonly used commercial QA platform currently and has been used extensively for both industry and research purposes. For a detailed, step-by-step guide on using a quantum annealer, interested readers are encouraged to consult the numerous introductory articles available on this topic[31], [61], [65]. In summary, the primary steps involved in utilizing an annealer include problem formulation, minor embedding, and sampling (i.e. the anneal itself). Problem formulation and how the classical simulations were run is described next, with the influence of embedding and sampling discussed as part of the results.