A Quantum View on Convex Optimization
Joran van Apeldoorn

Abstract:
Every day we need to make many decisions: what we should have for dinner, what to vote for, or whether to kiss that special person for the first time.  There are also many decisions that need to be made at a larger scale, for example, groups, governments, and corporations have to make decisions in order to use their resources wisely.  Every decision asks us to consider many possibilities and to try to get the optimal outcome (or more often than not, to simply avoid disaster).  Making these decisions is further complicated by the constraints that are put on us.  Even though people have become quite good at making decisions, the increasing complexity of the world around us means that `going with our guts' is often an ill-advised optimization strategy.

The field of mathematics allows us to formulate an abstract version of some of the more complex problems we encounter, and allows us to quantify what the objectives and constraints are.  For some problems mathematics even gives us a simple closed-form solution, e.g. many of us have learned in school how find the extreme points on a parabola.  However, for many problems there is no such simple closed-form solution, the best we can do is to use a method, or algorithm, to construct a solution.  This puts us in the realm of computer science.

Computer science considers how to solve problems systematically, and more importantly how many steps the decision-making process has to take.  Most optimization problems can be solved by simply listing all possible combinations of decisions and then searching for the best option, but as the number of decisions increases, so does the number of combinations.  In fact, for many situations the number of possible combinations increases exponentially, making the process of writing down all the options impractical.  Instead we often look for a smarter, more efficient algorithm, one that scales better with the problem size.

It is not always easy (or even possible) to find an efficient algorithm.  Consider the problem of finding the lowest place in the Swiss Alps.  We may walk down into what seems the deepest valley, only to learn later that a farmer three valleys over has dug a really deep well.  One of the problems in such a scenario is that we may find a local minimum, but due to a lack of structure in the problem we have no clear way of finding a global minimum.  Some problems do have more structure, an important class of these is the class of convex optimization problems.  Convex optimization problems have the useful property that local minima are also global minima.  For our example about the Alps this means that, as long as we keep going down, we will always reach the lowest point.  However, as anyone who ever went snowboarding can tell you, how you go down matters a lot for how fast you will get there.

Apart from considering the structure of the problem we are trying to solve we should also consider what steps we can take to solve it.  We may want to use pen and paper, use our laptop, or use a supercomputer, all of which function differently.  However, these methods are not inherently different, with enough time we could perform the same computation as a supercomputer with nothing more than a pen and a piece of paper.  Although this would be significantly slower, the scaling with the problem size would stay the same since the basic steps we can use are the same, only slower.  What basic steps we may perform is ultimately dictated by the laws of physics: we can only change the state of our piece of paper, or our computer, in ways that are allowed by physics.  Specifically, our piece of paper and our computers both follow the laws of classical physics, the physics that we see around us every day.

During the 20th century our understanding of physics has changed and we now know that classical physics does not give a full description of the natural world.  One of the places where classical physics breaks down is at the scale of atoms and elementary particles, at this small scale the universe is governed by the laws of quantum physics.  Quantum physics predicts behavior that is not possible in classical physics.  Particles might be in a superposition of many different classical states, only becoming a specific one of those states at random when interacting with our classical world via a measurement.  Miraculously, and contrary to classical randomness, this quantum randomness does not stem from our inherent lack of knowledge about the particle, the different parts of the superposition are all present until we measure and can interfere with each other.  A natural question to ask is whether these phenomena can be used to our benefit when performing computations.  A computer that works according to the rules of quantum physics is called a Quantum computer, such devices have a wider range of basic operations that they can perform than classical computers do.

This thesis asks the following central question
can quantum computers solve convex optimization problems faster?

In order to answer this question we consider a few different types of problem that we may encounter in convex optimization.

If we have some black-box procedure to evaluate how good a proposed solution to a convex optimization problem is, for example a way of estimating the height of a point in the Alps or a method of estimating our profits given a business strategy, then a classical computer would have to try a lot of small changes in order to find the change that improves our objective the most.  However, we show that a quantum computer can find the optimal direction for improvement exponentially faster.

We then consider specific categories of convex optimization problems, mainly linear programming and semidefinite programming.  These problem categories include many natural problems and have been widely used both for theoretical and practical purposes.  For example, linear programming can be used for finding the optimal strategies of zero-sum games, coming up with a diet plan, or planning resources.  Semidefinite programming is a generalization of linear programming and can additionally be useful for designing optimal experiments, approximately solving hard problems, or optimize processes involving quantum mechanics.  Our quantum algorithms for these problems use a natural connection between quantum physics and semidefinite programming: the solutions to a semidefinite programming problem correspond to the states of a quantum system.  We show that quantum computers can solve semidefinite programming problems and linear programming problems quadratically faster than a classical computer can.  In fact, our algorithms take less time to solve the problem than that it would take to read through the whole input.

We also take a more negative view and discuss the limitations of quantum computers.  We show that, even though quantum computers can find the optimal direction of improvement exponentially faster, there is no general exponential speedup for finding the optimal value. We also show that in many ways our methods for solving linear and semidefinite programming problems are optimal: faster methods would not be able to read enough of the input to still get a good solution.

To conclude, we showed that in a few different settings the answer to our central question is yes. The results in this dissertation show that quantum computers can solve some convex optimization problems faster, but there are also limits to this. There are still many open questions regarding convex optimization on quantum computers and we regard this topic as an important direction of future research.