Quantum Speed-ups for Boolean Satisfiability and Derivative-Free Optimization

Srinivasan Arunachalam

Published Apr 21, 2014• 6 citations

Abstract

In this thesis, we have considered two important problems, Boolean satisfiability (SAT) and derivative free optimization in the context of large scale quantum computers. In the first part, we survey well known classical techniques for solving satisfiability. We compute the approximate time it would take to solve SAT instances using quantum techniques and compare it with state-of-the heart classical heuristics employed annually in SAT competitions. In the second part of the thesis, we consider a few classically well known algorithms for derivative free optimization which are \nubiquitously employed in engineering problems. We propose a quantum speedup to this classical algorithm by using techniques of the quantum minimum finding algorithm. In the third part of the thesis, we consider practical applications in the fields of bio-informatics, petroleum refineries and civil engineering which involve solving either satisfiability or derivative free optimization. We investigate if using known quantum techniques to speedup these algorithms directly translate to \nthe benefit of industries which invest in technology to solve these problems. In the last section, we propose a few open problems which we feel are immediate hurdles, either from an algorithmic or architecture perspective to getting a convincing speedup for the practical problems considered.

Related papers

Applying quantum algorithms to constraint satisfaction problems

Earl T. Campbell, Ankur Khurana, Ashley Montanaro

Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over 105 relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over 103 . However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.

arXiv:1810.05582QuantumJul 18, 201976 citations

Quantum random walk search on satisfiability problems

Stephan Hoyer

Using numerical simulation, we measured the performance of several potential quantum algorithms, based on quantum random walks, to solve Boolean satisfiability (SAT) problems. We develop the fundamentals of quantum computing and the theory of classical algorithms to indicate how these algorithms could be implemented. We also discuss the development of quantum random walks and the principles that go into creating them, presenting existing work on search algorithms using coined discrete-time quantum random walks. Although our quantum algorithms do not solve SAT problems faster than may be done classically, as a step toward that objective, we present the first example of a quantum walk on a directed graph that has a significant increase in speed over the analogous classical walk.

Jan 1, 20086 citations

Speeding up search algorithms with Quantum Computing

Jose J. Paulet

This thesis focuses on algorithms over Quantum computing applied over NP hard search problems on domains lacking of any order. The partition problem has been addressed as first stage so providing a piece of quantum computing code which amplifies the amplitude of the solution state noticeably. This work continues addressing the problem of the satisfiability of Boolean formulas, in particular 3-SAT, from hybrid computation perspectives over both classical / quantum and purely quantum computing. There have been proposed strategies which include the definition of own heuristics and own metrics. The application of these strategies has meant a review of Grover's algorithm that has led to propose different methods of modifying it.

Jan 1, 20230 citations

Quantum Algorithms for Machine Learning and Optimization

P. Sangeetha, Prameela Kumari

Improvising the performance of machine learning for applications in the field of computer science leads to create new algorithms. As these are being optimized, using the algorithms of the classical machine learning in the area of quantum computing are being widely researched. First, we can consider general optimization problems with only functional Evaluations. Quantum Speedups of the problems can be improved compared to the classical algorithms. A frame work for quantum inspired classical algorithms can be introduced. To study the various problems on quantum computers on testing properties and compare the quantum speed ups with the classical counter parts.

PhD Colloquium on Ethically Driven Innovation and Technology for Society (PhD EDITS)Nov 8, 20209 citations

Quantum algorithms for machine learning and optimization

Tongyang Li

The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including L1-distance, L2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.

Jan 1, 20202 citations

Hybrid quantum computing : on the role of classical computing in scaling up quantum computing

Arman Zaribafiyan

In this thesis, we aim to answer one research question: What is the algorithmic role of classical computing in scaling up quantum computing applicability? Quantum computers have promising potential in offering more efficient solutions to some of the most demanding computational problems in the industry. There has been phenomenal progress in the theory and realization of quantum computers in the last few decades. However, quantum computing is a nascent field of technology and scaling up its computing capacity remains impeded by many open engineering/scientific challenges. One emerging solution to alleviate some of the present limitations is finding clever use of classical pre- and post-processing techniques in tandem with quantum algorithms. This helps to advantageously use scarce quantum computing resources for only a portion of a problem that benefits the most from a quantum computer. In other words, it leads to a hybrid framework in which quantum computers are considered special-purpose co-processors for accelerating specific computational tasks. We aim to develop a hybrid theoretical framework for the role of classical algorithms in scaling up quantum computing. We investigate this by focusing on three distinct limitations. We review each limitation in the context of a different application and propose an original hybrid classical-quantum solution to it. First, we focus on classical algorithms' role in a more resource-efficient compilation and embedding of quantum programs. We propose a classical algorithm that helps to embed larger optimization problems in a quantum annealer. Then we explore how a problem decomposition technique and preprocessing of the input problem can help solve significantly larger optimization problems on a quantum computer. Finally, we propose a completely hybrid quantum algorithm for preparing ground states of quantum Hamiltonians. We achieve orders of magnitude faster convergence by combining classical optimization with variational quantum state preparation.

Jan 1, 20210 citations