Quantum annealing and tensor networks: a powerful combination to solve optimization problems

Abstract

Quantum computing has long promised to revolutionize the way we solve complex problems. At the same time, tensor networks are widely used across various fields due to their computational efficiency and capacity to represent intricate systems. While both technologies can address similar problems, the primary aim of this thesis is not to compare them. Such comparison would be unfair, as quantum devices are still in an early stage, whereas tensor network algorithms represent the state-of-the-art in quantum simulation. Instead, we explore a potential synergy between these technologies, focusing on how two flagship algorithms from each paradigm, the Density Matrix Renormalization Group (DMRG) and quantum annealing, might collaborate in the future. Furthermore, a significant challenge in the DMRG algorithm is identifying an appropriate tensor network representation for the quantum system under study. The representation commonly used is called Matrix Product Operator (MPO), and it is notoriously difficult to obtain for certain systems. This thesis outlines an approach to this problem using finite automata, which we apply to construct the MPO for our case study. Finally, we present a practical application of this framework through the quadratic knapsack problem (QKP). Despite its apparent simplicity, the QKP is a fundamental problem in computer science with numerous practical applications. In addition to quantum annealing and the DMRG algorithm, we implement a dynamic programming approach to evaluate the quality of our results. Our results highlight the power of tensor networks and the potential of quantum annealing for solving optimization problems. Moreover, this thesis is designed to be self-explanatory, ensuring that readers with a solid mathematical background can fully understand the content without prior knowledge of quantum mechanics.