The starting point of my thesis work was the study of optimization algorithms based on cavity method. These algorithms have been developed to a high degree of complexity in the last decade and they are also known as message passing algorithms (MPAs). My work has started by a question posed by my supervisor: what links can be found between those different approaches to the same problems? The starting aim of the PhD project was to explore the new ideas and algorithms that could result from a cross-fertilization between different approaches. During the first years we made a long and accurate comparison between different algorithms on a specific COP: the prize collecting Steiner tree problem. Looking to MPAs as an evolution of probability distributions of discrete variables led me to find some possible links with many body quantum physics, where typically we deal with probability amplitudes over discrete variables. In the recent years several results have appeared concerning the extension of the cavity method and message passing technics to quantum context. In 2012 Ramezanpour proposed a method, the variational quantum cavity method (VQCM), for finding approximate ground state wave functions based on a new messages passing algorithm used in stochastic optimization. Ramezanpour and I have extended this approach to find low excited states. In the last year of my Ph.D. I simplify the VQCM using imaginary time evolution operator. Moreover I extend this approach to find finite temperature density matrix
The starting point of my thesis work was the study of optimization algorithms based on cavity method. These algorithms have been developed to a high degree of complexity in the last decade and they are also known as message passing algorithms (MPAs). My work has started by a question posed by my supervisor: what links can be found between those different approaches to the same problems? The starting aim of the PhD project was to explore the new ideas and algorithms that could result from a cross-fertilization between different approaches. During the first years we made a long and accurate comparison between different algorithms on a specific COP: the prize collecting Steiner tree problem. Looking to MPAs as an evolution of probability distributions of discrete variables led me to find some possible links with many body quantum physics, where typically we deal with probability amplitudes over discrete variables. In the recent years several results have appeared concerning the extension of the cavity method and message passing technics to quantum context. In 2012 Ramezanpour proposed a method, the variational quantum cavity method (VQCM), for finding approximate ground state wave functions based on a new messages passing algorithm used in stochastic optimization. Ramezanpour and I have extended this approach to find low excited states. In the last year of my Ph.D. I simplify the VQCM using imaginary time evolution operator. Moreover I extend this approach to find finite temperature density matrix
This thesis is focused on the application and development of numerical methods for studying quantum many- body spin systems. Part I sets the stage for research projects. In chapter 1, I go over major milestones in the field of frustrated magnetism, how it fits into a larger category of condensed matter physics, and recent developments that provide context for the research projects presented in part II. Chapters 2 3 provide the reader with necessary concepts in physics of phase transitions and numerical methods that are often employed when studying ground states of quantum many body systems. Part II focuses on the research projects carried out during my PhD research. In chapter 4 I present a machine-learning inspired method for solving quantum many body problems. This method addresses issues of representation of variational wave functions and their optimization. In chapter 5, I present a numerical study on the embedding of an exactly solvable point in a phase diagram of an extended Heisenberg model on a kagome lattice. Chapter 6 studies a quantum Heisenberg model on the stuffed honeycomb lattice. Phase transitions in quantum many body systems manifest themselves as a reorganization of low energy spectra of the system. They come in a variety of forms ranging from symmetry breaking transitions, where a local order parameter is formed and to topological phase transitions where the change of the ground state can be attributed to non-local changes in the entanglement patterns. In chapter 2, I review classic models studied in the context of frustrated magnetism and briefly go over the formulation of Landau symmetry breaking theory and common order parameters. The breakdown of Landau symmetry-breaking theory for topological phase transition is discussed using the example of Resonance Valence Bond (RVB) state, which serves as a qualitative exemplification of spin liquid phases. I discuss means of detecting phase transitions with a focus on methods that are applicable in a numerical setting. Chapter 3 presents elements of the numerical machinery that the rest of the thesis employs and builds upon. I discuss traditional trade-offs and provide rough metrics used for analysis of strengths and drawbacks of different approaches. Then I focus on Exact Diagonalization (ED) and Variational Monte Carlo (VMC) methods that are used in later chapters. In chapter 4, I describe the application of machine learning techniques to the variational approach to the quantum many body problem. I introduce Computational Graph States (CGS), a new class of variational wave functions based on the dataflow programming paradigm. The use of computational graphs makes composing new wave functions easy due to its modular structure. Automatic differentiation allows us to obtain efficient derivatives with respect to variational parameters automatically. We also develop a novel optimization scheme, Supervised Wave-function Optimization. It combines ideas of supervised learning and imaginary time evolution. Our method resolves a number of technical challenges and allows seamless optimization of complicated variational models. During the exploration process we constructed a new class of system size invariant model wave functions that can be trained on one system size and generalized to other system sizes with high accuracy. In chapter 5, we study the phase diagram of the kagome antiferromagnet in the J2, Jz plane, which corresponds to second nearest neighbor interactions and spin anisotropy. We report an exactly solvable point with macroscopic degeneracy at J2 = 0, Jz = −0.5 and show that many phases emanate from around this point. In addition, we find a previously unknown transition within the spin-liquid region suggesting a possibility of two distinct spin liquids. In chapter 6, we consider a Heisenberg model on the stuffed honeycomb lattice which interpolated between the triangular and honeycomb lattices. Using exact diagonalization we compute the phase diagram of this model. We find that for this model, the triangular lattice J1-J2 spin liquid region is extended to a larger domain that has lower symmetries than that of the triangular lattice. We perform a variational study of projected BCS wave functions which we directly compare to exact ground states on 36 site cluster as well as consider variational energies from larger system sizes. We argue that construction of symmetric states is essential to obtain good variational energies and give evidence that Dirac spin-liquid state is likely to characterize the spin liquid phase.
In this thesis we have implemented three many-body methods in quantum mechanics on quantum computers, namely the Quantum Phase Estimation (QPE) algorithm, the Variational Quantum Eigensolver (VQE) algorithm and the Quantum Adiabatic Time Evolution (QATE) algorithm.We utilized these methods to approximate the ground state energy of the pairing model Hamiltonian.We provided a comparison between the ideal simulation of a quantum computer and a simulation including the noise model from some of IBM's actual quantum devices.For the VQE algortihm, we also run the method on the IBM Q London five-qubit device.As the time complexity (circuit depth) of a quantum algorithm (quantum circuit) is often the bottleneck on current quantum computers, we also introduced a circuit optimization scheme, called Recursive Circuit Optimization, which can be utilized to approximate the action of a quantum circuit by learning the parameters of a parametrized unitary operation and only evaluating small parts of the circuit at a time.We tested out the method by trying to optimize a random circuit, the QATE algorithm and the unitary coupled cluster doubles (UCCD) ansatz.Finally, we implemented a quantum circuit that allows us to encode a real data set into the amplitudes of a quantum state, and we utilized this circuit to implement several realizations of dense and recurrent neural networks on quantum computers.We proposed neural network layers that are consisting of hardware-and parameter-efficient parametrized quantum circuits, and we have made a Python framework to construct and train deep quantum neural networks.We then tested the neural networks by trying to learn a simple non-linear function as well as finding the smallest eigenvalue of the pairing Hamiltonian Full Configuration Interaction (FCI) matrix.We found that all the quantum many-body methods showed promise in providing an upper bound on the ground state energy for the ideal simulation of a quantum computer.When performing the simulation with noise and the execution on the real quantum device however, we found that only the VQE algorithm was able to yield reasonable results due to short circuit depth.Still, the success of the method was found to be dependent on the interaction strength g of the quantum system, as the approximation of the ground state energy started to deviate from the actual value as we increased g.For the recursive circuit optimization of a random circuit, we found that we were able to approximate the state given by the random circuit, and we learned that we should expect some error in the approximation due to finite measurements and the flexibility of the parametrized unitary.When utilizing the recursive optimization scheme to approximate the QATE algorithm, we found that although we were not able to exactly reproduce the action of the operator, we did provide an upper bound to the ground state energy close to the one given by the actual QATE algorithm.In the same time, the circuit depth of the algorithm was drastically decreased.When utilizing the scheme for the VQE algorithm, we got promising results while reducing the circuit depth of the UCCD ansatz.Over to the neural networks, we managed to approximate a non-linear function utilizing a hardware-efficient three layered network, with only three qubits in the intermediate layers.We showed that our proposed neural network are suitable for near-term quantum computers by successfully approximating the lowest eigenvalue of the FCI matrix when running a simulation with the noise model from the IBM Q London five-qubit computer.i I would first like to thank my supervisor, Morten Hjorth-Jensen, for being helpful and motivational throughout my time at the University of Oslo.Your door has always been open when help is needed, which has been a great relief in stressful times.I would also like to thank my friends and family for believing in me and providing emotional support.Your continuous interest in my studies and well-being has meant a lot to me.My next thanks goes to Heidi K. J.I highly appreciate your never-ending support.Finally I would like to thank the computational physics study group.You have been invaluable to me in both a social and educational manner.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.
T his thesis studies quantum communication complexity and quantum error correction, two fundamental areas in the theory of quantum computation, and is divided into two parts.The first part focuses on generalising three central problems in quantum communication complexity, often by the introduction of more general Boolean functions.The first studied problem is the one of approximating the Hamming distance in the simultaneous message passing model in communication complexity -a natural generalisation of the Equality problem.An efficient quantum communication protocol is established and later used as the basis for approximating other useful distance measures, e.g.graph distance and ℓ 1 -distance.The second generalised problem is the Boolean Hidden Matching problem, the first proposed one to exhibit an exponential quantum-classical communication separation in the one-way model.Originally defined as a task of matching bits using the Parity function, the problem is generalised by replacing the Parity function with any Boolean function.The hardness of the resulting problem, both classical and quantumly, is characterised in terms of two properties of the Boolean function used, its sign degree and pure high degree.The first part of the thesis is completed by studying the generalisation of random access codes where the parties are no longer interested in recovering any initial bit, but the value of a fixed Boolean function on any subset of the initial bits with constant size.Different random access codes are defined by means of different accessible classical and quantum resources and their efficiency analysed and compared.The second part of the thesis is devoted to the study of quantum error correction and the toric code.Even though unrealistic for some physical platforms, most decoders proposed for the toric code assume that stabilizer measurements can always be performed deterministically.This second part aims to study the effect of probabilistic stabilizer measurements, i.e., asynchronism, on the toric code.A few different decoders, based on gradually more refined approximations, are proposed in order to handle the asynchronism and it is numerically shown that they are able to maintain a high threshold even in the limit where stabilizer measurements are performed continuously.i Dedication and acknowledgements M y deepest thanks goes to my supervisor, Ashley Montanaro, who supported and motivated me during these last three years.Coming from a physics background, I am grateful to Ashley for introducing me to the field of Quantum Computation, and also for helping me to mature both academically and intellectually since my Masters.I also thank Ashley for incentivising my taste for literature by lending me his copy of John Milton's Paradise Lost.I thank my co-authors, Naomi Nickerson and Hugo Cable, for all the help and discussions behind Chapter 6 about quantum error correction and the toric code, and for their kind welcome at the time of my visit at PsiQuantum.I also thank Ryan Mann for many useful discussions, most of them about concepts from Chapter 6 and self-avoiding walks; Ronald de Wolf for having reliably improved all my papers so far with valuable suggestions and comments, for suggesting the block-encoding scheme in Chapter 4, originally with the 2, 3 → 1 QRACs, for pointing out Refs. [119,121,177] and for the precise reviewing of the thesis; Noah Linden for the precise reviewing of the thesis and for testing me throughout my PhD with interesting questions; Raphaël Clifford for helpful discussions related to Chapter 2; Makrand Sinha for useful discussions about the hypercontractive inequality; Máté Farkas and Mark Howard for pointing out Refs. [4,72,73, 190] and [69], respectively.These last four years would not be the same without all the support from QE-CDT (Center for Doctoral Training in Quantum Engineering) and QET Labs (Quantum Engineering Technology Labs) and all the people behind them, both the management and the academic teams.And not less important, my time in Bristol would definitely not be the same without my cohort:
Quantum computing is a rapidly developing field that has seen a huge amount of interest in the last couple of decades due to its promise of revolutionizing several domains of business and science. It presents a new way of doing computations by making use of fundamental properties of quantum mechanics such as superposition and entanglement. Optimization, on the other hand, is a field that is omnipresent in the industry and where small improvements can have a significant impact. This thesis aims to tackle optimization problems using quantum algorithms.NP-hard optimization problems are not believed to be exactly solvable through general polynomial time algorithms. Variational quantum algorithms (VQAs) to address such combinatorial problems have been of great interest recently. Such algorithms are heuristic and aim to obtain an approximate solution. The hardware, however, is still in its infancy and the current Noisy Intermediate Scale Quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions.An issue with contemporary quantum optimization algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) is that they scale linearly with problem size. To tackle this issue, we present the LogQ encoding, using which we can design quantum variational algorithms that scale logarithmically with problem size - opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. We show how this algorithm can be applied to several combinatorial optimization problems such as Maximum Cut, Minimum Partition, Maximum Clique and Maximum Weighted Independent Set (MWIS). Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.Next, we apply the LogQ encoding to two use-cases for large companies such as TotalEnergies. Fleet conversion is the process of transitioning a fleet of vehicles to more sustainable and environmentally friendly alternatives. It is modeled as a column generation scheme with the MWIS problem as the sub-problem or worker problem. We use the LogQ method to solve the MWIS Workers and demonstrate how quantum and classical solvers can be used together in a hybrid manner to approach an industrial-sized use-case. Mesh segmentation refers to the process of dividing a complex mesh (composed of vertices, edges, and faces) into meaningful and semantically coherent parts or regions. Mesh segmentation plays an important part in computer modeling, which is extensively used in the core domains of TotalEnergies' activities such as Earth imaging, physical modeling for reservoirs, and others. We define the problem as a graph optimization problem and use the LogQ encoding to solve it.