BACHELOR’S DEGREE IN MATHEMATICS
BACHELOR’S DEGREE IN COMPUTER SCIENCE AND SOFTWARE ENGINEERING · 2024
Read BACHELOR’S DEGREE IN MATHEMATICS by BACHELOR’S DEGREE IN COMPUTER SCIENCE AND SOFTWARE ENGINEERING (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-05595.txt.
Introduction
Miquel Alberti Binimelis wrote a bachelor's thesis in twenty twenty-four on joining two quantum technologies. One is quantum annealing, a method that lets a quantum device settle into the best answer to an optimization problem. The other is tensor networks, efficient math structures that simulate quantum systems on classic computers.
The thesis does not pit the two against each other, since quantum hardware is young. It asks how flagship methods from each side, the DMRG algorithm and quantum annealing, might one day work together. A hard sub-problem is building the right network form for a system, and the thesis uses finite automata to build it. A case study solves the quadratic knapsack problem three ways.
Catalog record
| CREATOR | BACHELOR’S DEGREE IN COMPUTER SCIENCE AND SOFTWARE ENGINEERING |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-05595
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
BACHELOR’S DEGREE IN MATHEMATICS BACHELOR’S DEGREE IN COMPUTER SCIENCE AND SOFTWARE ENGINEERING Abstract Abstract † † 2020 Mathematics Subject Classification. 15A18, 47B02, 68Q12, 68W01, 81T32, 90C20, 90C27 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. Keywords: Tensor networks, quantum computing, quantum annealing, Matrix Product Operators, DMRG algorithm, finite automata, QUBO formulation, quadratic knapsack problem, optimization, dynamic programming. 0.1 Introduction Quantum computers and Tensor Networks are engaged in an exciting battle to simulate and understand the intricate nature of quantum systems. The remarkable capacity of tensor networks to represent and manipulate the quantum realm is impressive [ 3 , 9 , 5 , 24 ] . Algorithms such as the Density Matrix Renormalization Group (DMRG) have captured considerable attention [ 20 , 21 ] , and will be one of the main focuses of this thesis. However, the implications of tensor networks extend beyond physics, as many industrial problems can be solved using these techniques when cast as optimization problems. On the other hand, we find ourselves in the Noisy Intermediate-Scale Quantum (NISQ) era [ 15 ] , in which quantum computers still cannot outperform classical ones in real-world applications. Among the various types of quantum computers, quantum annealers exhibit faster scalability in terms of qubit count due to their relative ease of construction [ 2 , 6 ] . Although these devices are not universal quantum computers, they excel at solving specific optimization tasks formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. In this project, the reader will obtain an overview of all of these concepts, with a particular emphasis on their synergies. Our technical contributions are: • The QUBO formulation of the quadratic knapsack problem with the unbalanced penalization technique [ 17 ] , that allows the encoding of inequality constraints without adding more variables. • The creation of the Matrix Product Operator (MPO) that describes the quantum system used in quantum annealing: the annealing Hamiltonian of an Ising model. This enables the use of the DMRG algorithm to study the evolution performed in quantum annealing. • A proposal of an annealing scheduling time evolution based on the study of the minimum gap with the DMRG. Other valuable insights of the thesis are: • An introduction to quantum computing and tensor networks for people with no physics background. • An explanation of how the DMRG and quantum annealing algorithms work. • A detailed description of how to create MPOs using finite automata. • A Python implementation of all these algorithms, along with notebooks demonstrating their use. The thesis is organized into five chapters. The first two chapters introduce the basics of quantum computing and tensor networks, respectively. The third chapter integrates this knowledge to explore how tensor networks can be used to simulate quantum mechanics, and consequently quantum annealing, to study their performance and combine efforts for better results. The fourth chapter focuses on a methodology using finite automata to create MPOs, which describe a quantum system with tensor networks for use in DMRG. This methodology is then applied to derive the expression for the system of interest. Finally, chapter five applies all the concepts learned to tackle the quadratic knapsack problem using different algorithms: dynamic programming, DMRG, and simulated quantum annealing. The main abbreviatures that will be used are: • QUBO: Quadratic Unconstrained Binary Optimization • AQC: Adiabatic Quantum Computing • QA: Quantum Annealing • TN: Tensor Network • SVD: Singular Value Decomposition • MPS: Matrix Product State • MPO: Matrix Product Operator • DMRG: Density Matrix Renormalization Group • QKP: Quadratic Knapsack Problem • DP: Dynamic Programming All the Python code can be accessed from the corresponding GitHub public repository 2 2 2 https://github.com/MiquelAlberti2/Quantum-annealing-and-tensor-networks . An explanation of the structure of the code can be found on the README page. Chapter 1 Mathematical framework of quantum mechanics and quantum computing When we talk about classical computing, we know that boolean algebra is the mathematical framework that perfectly describes the structure and patterns to manipulate the minimum unit of information: bits. However, with quantum computing, we need a framework that captures the complexity of quantum mechanics, and it turns out that linear algebra does just that in a surprisingly natural way. In this section, we will explain how linear algebra is used in this context so that people with no physics background can follow this thesis simply by understanding the maths. The minimum unit of information in quantum computing is a qubit (quantum bit), which encapsulates the state of a two-level quantum system. By two-level, we mean it has two distinguishable elemental states, denoted as |0\rangle and |1\rangle . However, unlike classical bits (which also have two distinguishable states), qubits can be in a mixture of these two states, a phenomenon known as superposition [ 22 ] . Mathematically, a superposition is just a complex linear combination: |\psi\rangle=\alpha_{0}|0\rangle+\alpha_{1}|1\rangle=\binom{\alpha_{0}}{\alpha_{1}}\;;\;\alpha_{0},\alpha_{1}\in\mathbb{C},\;\left|\alpha_{0}\right|^{2}+\left|\alpha_{1}\right|^{2}=1, where |\alpha|^{2}=\alpha\cdot\bar{\alpha} denotes the modulus of \alpha . The coefficients \alpha_{0} and \alpha_{1} , called amplitudes, reflect how close the state |\psi\rangle is to the elemental states |0\rangle or |1\rangle , and they are normalized because it is, indeed, a probability distribution. We can manipulate these superposition states, but once we measure them they have to collapse to an elemental state, with a probability given by the amplitudes: we will measure the state |0\rangle with probability \left|\alpha_{0}\right|^{2} or the state |1\rangle with probability \left|\alpha_{1}\right|^{2} . 1.1 Hilbert space We have already introduced the symbol |\;\rangle . This is known as a ket and is just the standard notation to designate a vector representing a quantum state (a state vector). In a one-qubit system, we have the basis |0\rangle=\binom{1}{0} |1\rangle=\binom{0}{1}\;\;. but we can have systems with many