Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Stochastic Approach to a Class of Convex Optimization Problems

Pavel Shcherbakov, Boris T. Polyak

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

We propose a new approach to solving a wide class of optimization problems which fall into the broad framework of linear matrix inequalities and semidefinite programming. This approach based on randomization and cutting hyperplane ideology also covers robust statements of the problem. The proposed method is easy to implement, and it might be particularly useful in various aspects of functioning and applications of quantum computers.

Related papers

A quantum view on convex optimization

Joran van Apeldoorn

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.

•Feb 6, 2020•4 citations

Variational Quantum Algorithms for Semidefinite Programming

Dhrumil Patel, Patrick J. Coles, Mark M. Wilde

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

arXiv:2112.08859•Quantum•Jun 17, 2024•25 citations

Randomized stochastic approximation algorithms

Амелин Константин Сергеевич, Oleg Nikolaevich Granichin, Olga A. Granichina

Multidimensional stochastic optimization plays an important role in analysis and control of many technical systems. To solve the challenging problems of multidimensional optimization, it was suggested to use the randomized algorithms of stochastic approximation with perturbed input which have simple forms and provide consistent estimates of the unknown parameters for observations under “almost arbitrary” noise. They are easily “incorporated” in the design of quantum devices to estimate gradient vector of a multi-variable function.

European Control Conference (ECC)•Jun 1, 2014•0 citations

A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices

Jakub Mareček, Albert Akhriev

There is an increasing interest in quantum algorithms for optimization problems. Within convex optimization, interior-point methods and other recently proposed quantum algorithms are non-trivial to implement on noisy quantum devices. Here, we discuss how to utilize an alternative approach to convex optimization, in general, and semidefinite programming (SDP), in particular. This approach is based on a randomized variant of the cutting-plane method. We show how to leverage quantum speed-up of an eigensolver in speeding up an SDP solver utilizing the cutting-plane method. For the first time, we demonstrate a practical implementation of a randomized variant of the cutting-plane method for semidefinite programming on instances from SDPLIB, a well-known benchmark. Furthermore, we show that the RCP method is very robust to noise in the boundary oracle, which may make RCP suitable for use even on noisy quantum devices.

arXiv:2110.03400•Oct 7, 2021•6 citations

A randomized stochastic optimization algorithm: Its estimation accuracy

Alexander Vakhitov, Oleg Nikolaevich Granichin, S. S. Sysoev

For a randomized stochastic optimization algorithm, consistency conditions of estimates are slackened and the order of accuracy for a finite number of observations is studied. A new method of realization of this algorithm on quantum computers is developed.

Automation and Remote Control•Apr 1, 2006•9 citations

Slack-variable approach for variational quantum semidefinite programming

Jingxuan Chen, Hanna Westerheim, Zoë Holmes +6 more

Solving optimization problems is a key task for which quantum computers could possibly provide a speedup over the best known classical algorithms. Particular classes of optimization problems including semidefinite programming (SDP) and linear programming (LP) have wide applicability in many domains of computer science, engineering, mathematics, and physics. Here we focus on semidefinite and linear programs for which the dimensions of the variables involved are exponentially large, so that standard classical SDP and LP solvers are not helpful for such large-scale problems. We propose the QSlack and CSlack methods for estimating their optimal values, respectively, which work by (1) introducing slack variables to transform inequality constraints to equality constraints, (2) transforming a constrained optimization to an unconstrained one via the penalty method, and (3) replacing the optimizations over all possible nonnegative variables by optimizations over parameterized quantum states and parameterized probability distributions. Under the assumption that the SDP and LP inputs are efficiently measurable observables, it follows that all terms in the resulting objective functions are efficiently estimable by either a quantum computer in the SDP case or a quantum or probabilistic computer in the LP case. Furthermore, by making use of SDP and LP duality theory, we prove that these methods provide a theoretical guarantee that, if one could find global optima of the objective functions, then the resulting values sandwich the true optimal values from both above and below. Finally, we showcase the QSlack and CSlack methods on a variety of example optimization problems and discuss details of our implementation, as well as the resulting performance. We find that our implementations of both the primal and dual for these problems approach the ground truth, typically achieving errors of the order 10-2.

Physical Review A•Jun 20, 2025•8 citations
We propose a new approach to solving a wide class of optimization problems which fall into the broad framework of linear matrix inequalities and semidefinite programming. This approach based on randomization and cutting hyperplane ideology also covers robust statements of the problem. The proposed method is easy to implement, and it might be particularly useful in various aspects of functioning and applications of quantum computers.
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.
A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.
Multidimensional stochastic optimization plays an important role in analysis and control of many technical systems. To solve the challenging problems of multidimensional optimization, it was suggested to use the randomized algorithms of stochastic approximation with perturbed input which have simple forms and provide consistent estimates of the unknown parameters for observations under “almost arbitrary” noise. They are easily “incorporated” in the design of quantum devices to estimate gradient vector of a multi-variable function.
There is an increasing interest in quantum algorithms for optimization problems. Within convex optimization, interior-point methods and other recently proposed quantum algorithms are non-trivial to implement on noisy quantum devices. Here, we discuss how to utilize an alternative approach to convex optimization, in general, and semidefinite programming (SDP), in particular. This approach is based on a randomized variant of the cutting-plane method. We show how to leverage quantum speed-up of an eigensolver in speeding up an SDP solver utilizing the cutting-plane method. For the first time, we demonstrate a practical implementation of a randomized variant of the cutting-plane method for semidefinite programming on instances from SDPLIB, a well-known benchmark. Furthermore, we show that the RCP method is very robust to noise in the boundary oracle, which may make RCP suitable for use even on noisy quantum devices.
Solving optimization problems is a key task for which quantum computers could possibly provide a speedup over the best known classical algorithms. Particular classes of optimization problems including semidefinite programming (SDP) and linear programming (LP) have wide applicability in many domains of computer science, engineering, mathematics, and physics. Here we focus on semidefinite and linear programs for which the dimensions of the variables involved are exponentially large, so that standard classical SDP and LP solvers are not helpful for such large-scale problems. We propose the QSlack and CSlack methods for estimating their optimal values, respectively, which work by (1) introducing slack variables to transform inequality constraints to equality constraints, (2) transforming a constrained optimization to an unconstrained one via the penalty method, and (3) replacing the optimizations over all possible nonnegative variables by optimizations over parameterized quantum states and parameterized probability distributions. Under the assumption that the SDP and LP inputs are efficiently measurable observables, it follows that all terms in the resulting objective functions are efficiently estimable by either a quantum computer in the SDP case or a quantum or probabilistic computer in the LP case. Furthermore, by making use of SDP and LP duality theory, we prove that these methods provide a theoretical guarantee that, if one could find global optima of the objective functions, then the resulting values sandwich the true optimal values from both above and below. Finally, we showcase the QSlack and CSlack methods on a variety of example optimization problems and discuss details of our implementation, as well as the resulting performance. We find that our implementations of both the primal and dual for these problems approach the ground truth, typically achieving errors of the order 10-2.