Software and Hardware Design of Digital Quantum Annealing Emulators

Quantum annealing has been proposed as an alternative to classical computing algorithms for solving combinatorial Quadratic Unconstrained Binary Optimization (QUBO) problems, which are employed for describing many real-world problems, as the analysis of new drugs and integrated circuits routing. QUBO formulation involves unipolar binary variables and cost functions show constraints on at most couples of variables, equivalently to the Ising model, describing the energy of a spins system depending on their orientations. In this case, the problem cost function is encoded onto the system energy profile, so the optimal solution corresponds to the lowest-energy configuration. The main difference between quantum annealing and classical approaches is that it uses quantum fluctuation instead of thermal one, as in simulated annealing, to overcome the energy barriers of the profile, thus permitting an easier exploration of problems showing high and narrow peaks. QUBO variables are mapped onto the physical qubits of a quantum annealer, whose correct functioning requires cryogenic temperature, shielding systems and a well-insulated environment, which rapidly increase the cost of the whole system. Furthermore, hardware solves problems with at most some thousands of binary variables and it is not fully-connected, thus requiring embedding techniques for mapping a generic problem on qubits. A compromise between physical limitations and computational advantages of quantum annealers can be achieved by their emulation on classical devices. Hardware emulators are preferable to software ones because they can mimic more accurately the parallel nature of quantum computation. Field Programmable Gate Arrays (FPGAs) are the most suitable devices for this purpose, since they are flexible and reconfigurable. The goal of this thesis is to design an FPGA implementation of a quantum annealer emulator. The state of art of digital quantum annealing emulation algorithms has been initially analyzed; two main families have been identified and compared in software: Path Integral Quantum Monte Carlo (PI) and Simulated Bifurcation (SB). The first one emulates quantum superposition and tunneling effects, through a set of correlated replicas of the spins system representing the problems and performing a set of Monte Carlo steps; the other maps the problems onto a network of Kerr oscillators, whose evolution, according to motion equations, permits to find the optimal solution. In addition to these approaches, hybrid algorithms, where classical strategies and PI are combined, and different evolutions of oscillators network in SB were also considered for improving the performance. For each analyzed algorithm, a software implementation in both fixed and floating-point number representation was obtained, to study performance and to establish the most convenient number representation for a hardware emulator. Hybrid algorithms represented a significant improvement for a large set of problems and the discrete evolution in SB provided the most reliable results with max-cut ones. After software development, a digital architecture for Simulated Bifurcation, described in VHDL language, has been designed and then tested on FPGA through an interface with an on-board processor, employed for setting algorithm parameters at the beginning and reading the results at the end of the execution. Synthesis results depending on the complexity of the problem were also evaluated.