Embedding penalties for quantum hardware architectures and performance of simulated quantum annealing

Abstract

Quantum computing aims to harness the properties of quantum systems to more effectively solve certain kinds of computational tasks. Among quantum computers, quantum annealers are special-purpose machines whose main appeal is their ability to solve hard optimization problems while giving certain theoretical guarantees for correctness. Hard optimization problems can be found in many fields, making good and fast solvers highly sought after. While classical annealing algorithms have been established as very successful heuristics, a potential scaling advantage of a quantum annealer produced great interest. The possibility to manifest those quantum advantages in real devices however remain speculative. In short, the inability to create arbitrary large all-to-all connected graph like structures in hardware forces the use of embeddings, mappings of the original problem onto a quantum system with only short range interactions. Currently there is one main commercial quantum annealer, which uses such an embedding to map the optimization problem onto the hardware. In more recent time, an alternative embedding was proposed, which we will study as well. In order to study the different embeddings, we need a class of optimization problems with potential for quantum annealing. This means picking problems where classical computing does not yet have fast and optimal solvers. We simulate the different embeddings and analyze their scaling compared to simulated quantum annealing, since a classical simulation of quantum annealing has no real world constraints and can realize all-to-all connectivity without any embedding necessary. Our research suggests that there might be an exponential penalty when using these embeddings for finding the embedded ground-state. In a next step, we analyze the ability of quantum annealing to find degenerate ground-states with equal probabilities, a property called fair sampling. With a simple transverse field driver, quantum annealing is known to not sample fairly, i.e. some degenerate ground-states are suppressed exponentially. We will address the conjecture that more advanced drivers will lead to fair sampling. Throughout this thesis, much emphasis is placed on clean software design that maximizes reusability, flexibility and maintainability of the scientific software. This entire thesis should be reproducible with very little effort, since no external data sources are necessary.