Quantum Optimization for Linear Algebra Problems

Author/Creator

Author/Creator ORCID

Date

2022-01-01

Department

Computer Science and Electrical Engineering

Program

Computer Science

Citation of Original Publication

Rights

This item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://aok.lib.umbc.edu/specoll/repro.php or contact Special Collections at speccoll(at)umbc.edu
Distribution Rights granted to UMBC by the author.
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan thorugh a local library, pending author/copyright holder's permission.

Abstract

We have entered the age of noisy intermediate-scale quantum (NISQ) computers. However, these devices are not fault-tolerant to run the traditional quantum algorithms (like Shor's or Grover's Algorithm) for doing computation on a useful scale. In this dissertations work, we examine the potential of NISQ era quantum optimization, such as quantum annealing implemented for the Ising model and the gate-model quantum approximate optimization algorithm (QAOA), for solving problems in linear algebra. This is especially relevant as many of the other quantum algorithms (such as the Harrow Hassidim Lloyd algorithm) for linear algebra have a list of assumptions that may not be addressed in the near-term future. The discrete quantum optimization approach is an alternative to those techniques that while not being as fast as the more traditional quantum algorithms for linear algebra, may still perform better than the conventional classical techniques in the near-term and beyond. We start with a study of quantum annealing for solving linear least squares problems. Here, we show how quantum annealing can be faster than some of the most prominent direct (classical) methods, given certain assumptions. Our adiabatic simulations give an indication that quantum computing can have an advantage for problems where matrix $A \in \mathbb{R}^{m\times n}$ has dimensions $m \gg n$ and also where $A$ may be ill-conditioned. We followed it up with experiments on least squares problems and compared it to the best classical results. Next, we take a look at a few different ways in which post-processing results from quantum optimizers with classical techniques can impact the quality of the solution. We consider the single-qubit correction (SQC) and the multi-qubit correction (MQC) techniques, two promising techniques and study their effectiveness for the domain of linear algebra. In our work, we found SQC performs much better than MQC for domains where the problem graphs are densely connected, such as in linear algebra. In this context, we can think of numerical iterative techniques such as least squares MINRES (LSMR) for linear least squares and bi-conjugate gradient (BiCG) for linear systems of equations as highly effective domain specific post-processing techniques. When using the outputs from D-wave and SQC as the initial guess $x_0$ for these techniques (instead of an all-zero vector), we found an improvement in a majority of the cases. This improvement was measured in terms of the number of iterations for reaching the termination condition and/or the absolute error in the residual $b-Ax$ for a fixed number of iterations. This implies that a hybrid quantum-classical iterative solver may provide advantages against a purely classical one. And finally, we worked on applying and studying QAOA for binary linear least squares (BLLS), a problem that can serve as a building block for other hard problems in linear algebra. Our experiments were done on the QISKIT simulator and two IBM Q 5 qubit machines. To the best of our knowledge, this is the first work done on applying BLLS on a gate-model quantum computer. We highlight the possibilities of using QAOA and QAOA-like variational algorithms for solving such problems, where the outputs produced are classical, unlike the other gate model algorithms that produce amplitude encoded results. Our simulations indicate that QAOA can scale well with problem size for good approximate solutions but getting an optimal solution is more challenging. We show how Simulated Annealing can outperform QAOA for BLLS at a circuit depth of $p\leq3$ for the probability of sampling the ground state. Finally, we point out some of the challenges involved in current-day experimental implementations of this technique on a cloud-based gate-model quantum computer.