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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Quantum optimization and maximum clique problems

Vitaliy A. Yatsenko, Pãnos M. Pardalos, Bruno H. Chiarini

Published Aug 24, 2004• 2 citations
Publisher

Abstract

This paper describes a new approach to global optimization and control uses geometric methods and modern quantum mathematics. Polynomial extremal problems (PEP) are considered. PEP constitute one of the most important subclasses of nonlinear programming models. Their distinctive feature is that an objective function and constraints can be expressed by polynomial functions in one or several variables. A general approach to optimization based on quantum holonomic computing algorithms and instanton mechanism. An optimization method based on geometric Lie - algebraic structures on Grassmann manifolds and related with Lax type flows is proposed. Making use of the differential geometric techniques it is shown that associated holonomy groups properly realizing quantum computation can be effectively found concerning polynomial problems. Two examples demonstrating calculation aspects of holonomic quantum computer and maximum clique problems in very large graphs, are considered in detail.

DOI
10.1117/12.546845

Related papers

Introduction to Grassmann manifolds and quantum computation

Kazuyuki Fujii

Geometrical aspects of quantum computing are reviewed elementarily for nonexperts and/or graduate students who are interested in both geometry and quantum computation. We show how to treat Grassmann manifolds which are very important examples of manifolds in mathematics and physics. Some of their applications to quantum computation and its efficiency problems are shown. An interesting current topic of holonomic quantum computation is also covered. Also, some related advanced topics are discussed.

arXiv:quant-ph/0103011•Journal of Applied Mathematics•Jan 1, 2002•64 citations

Quantum computing in control and optimization

Vitaliy A. Yatsenko, Nikita Boyko, Petros Xanthopoulos +1 more

This paper deals with the progress made in applications of quantum computing in control and optimization. It concentrates on applying the geometric technique in order to investigate a finite control problem of a two-level quantum system, resonance control of a three-level system, simulation of bilinear quantum control systems, and optimal control using the Bellman principle. We show that a quantum object described by a Schroedinger equation can be controlled in an optimal way by electromagnetic modes. We also demonstrate an application of these techniques and an algebra-geometric approach to the study of dynamic processes in nonlinear systems. The information processing by means of controlled quantum lattices is discussed: we present new mathematical models of classical (CL) and quantum-mechanical lattices (QML) and their application to information processing. system-theoretical results on the observability, controllability and minimal realizability theorems are formulated for cl. The cellular dynamaton (CD) based on quantum oscillators is presented. Cellular's quantum computational search procedure can provide the basis for implementing adaptive global optimization algorithms. A brief overview of the procedure is given and a framework called lattice adaptive search is set up. A method of Yatsenko and one introduced by the authors fit into this framework and are compared.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 27, 2007•3 citations

Quantum algorithms for the polynomial eigenvalue problems.

Changpeng Shao, Jin-Peng Liu

Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with $A,B$ symmetric, and $B$ positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when $B$ is invertible, $B^{-1}A$ is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when $B$ is singular, any quantum algorithm uses at least $\Omega(\sqrt{n})$ queries to compute the eigenvalues, where $n$ is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.

•Oct 28, 2020•0 citations

Optimal control of quantum systems using dynamic programming

Srinivas Sridharan

This thesis focuses on the optimal control of a class of closed 1 quantum systems. It encompasses and addresses the following themes 1. The theoretical underpinnings of the dynamic programming method for quantum spin systems. 2. The efficient numerical implementation of algorithms to generate optimal control laws. The use of the dynamic programming principle from optimal control theory for the control of quantum systems is introduced, while taking into account the properties of the manifolds on which they evolve. This enables the unified application of dynamic programming to disparate problems which were previously approached using distinct tools. Moreover the approach herein is applicable, in principle, to an arbitrarily large quantum system - thereby overcoming the limitations present in some other commonly used methods in the literature, on the size of the quantum system being analyzed. As the optimal cost function is non-differentiable in several cases of interest, this thesis provides a rigorous interpretation of this cost function in terms of viscosity solutions of the associated Hamilton-Jacobi-Bellman (HJB) partial differential equation (PDE) over the manifolds of interest. This framework is applied to explore optimal control strategies for drift and drift-less quantum systems that arise in various applications - thus demonstrating the efficacy of a unified approach to address problems on qualitatively different systems. This thesis also investigates, via two distinct avenues, the efficient numerical solution to optimal control problems of interest. Firstly, it brings together the Markov chain ap- proximation methods of Kushner-Dupuis and the triangulation of manifolds introduced by Munkres, in order to numerically solve the optimal control problem on quantum systems via a value iteration approach. Secondly, the exponential growth in computational resources required - termed the curse of dimensionality (COD) -inherent in any spatial discretization approach to solving the HJB PDE is drastically lessened via a new reduced complexity method motivated by the COD free max-plus technique recently developed by McEneaney et al. The dramatic speedup obtained by this approach enables an approximate solution to a previously intractable optimal control problem for a two qubit2 spin system evolving on a 15 dimensional Lie group.

•Jan 1, 2010•0 citations

GRADIENT FLOWS FOR OPTIMIZATION IN QUANTUM INFORMATION AND QUANTUM DYNAMICS: FOUNDATIONS AND APPLICATIONS

THOMAS SCHULTE-HERBRÜGGEN, Steffen J. Glaser, Gunther Dirr +1 more

Many challenges in quantum information and quantum control root in constrained optimization problems on finite-dimensional quantum systems. The constraints often arise from two facts: (i) quantum dynamic state spaces are naturally smooth manifolds (orbits of the respective initial states) rather than being Hilbert spaces; (ii) the dynamics of the respective quantum system may be restricted to a proper subset of the entire state space. Mathematically, either case can be treated by constrained optimization over the reachable set of an underlying control system. Thus, whenever the reachable set takes the form a smooth manifold, Riemannian optimization methods apply. Here, we give a comprehensive account on the foundations of gradient flows on Riemannian manifolds including new applications in quantum information and quantum dynamics. Yet, we do not pursue the problem of designing explicit controls for the underlying control systems. The framework is sufficiently general for setting up gradient flows on (sub)manifolds, Lie (sub)groups, and (reductive) homogeneous spaces. Relevant convergence conditions are discussed, in particular for gradient flows on compact and analytic manifolds. This is meant to serve as foundation for new achievements and further research. Illustrative examples and new applications are given: we extend former results on unitary groups to closed subgroups with tensor-product structure, where the finest product partitioning relates to SUloc(2n) := SU(2) ⊗ ⋯ ⊗ SU(2) — known as (qubit-wise) local unitary operations. Such applications include, e.g., optimizing figures of merit on SUloc(2n) relating to distance measures of pure-state entanglement as well as to best rank-1 approximations of higher-order tensors. In quantum information, our gradient flows provide a numerically favorable alternative to standard tensor-SVD techniques.

arXiv:0802.4195•Reviews in Mathematical Physics•Jul 1, 2010•54 citations

Quantum gradient algorithm for general polynomials

Pan Gao, Keren Li, Shijie Wei +2 more

Gradient-based algorithms provide the fundamental tools for the optimizations and are the essential components of many modern technologies. Theoretically, the extreme points of a cost function can be found by iterative descent(ascent) of the variable along the direction of the gradient. However, the time complexity to calculate a gradient is at a level of $O(poly(d))$ for the $d$-dimension problems. For processing the high-dimension case, especially modern machine-learning engineering with the number of optimized parameters being in billions, quantum techniques are introduced. Via the dressed amplitude encoding and nonunitary module, a gradient-based quantum optimization algorithm for general polynomials is proposed, aiming at solving the fast-convergence problems with both time and memory complexity in $O(poly(logd))$. Furthermore, numerical simulations are carried out to inspect the performance of the newly born protocol by considering the noises or perturbations during the initialization, operations, and truncations. For the potential values in high-dimension optimizations, this gradient-based quantum optimization algorithm is supposed to facilitate the polynomial optimizations, being a subroutine for future practical quantum computers.

arXiv:2004.11086•Physical Review A•Apr 1, 2021•17 citations
This paper describes a new approach to global optimization and control uses geometric methods and modern quantum mathematics. Polynomial extremal problems (PEP) are considered. PEP constitute one of the most important subclasses of nonlinear programming models. Their distinctive feature is that an objective function and constraints can be expressed by polynomial functions in one or several variables. A general approach to optimization based on quantum holonomic computing algorithms and instanton mechanism. An optimization method based on geometric Lie - algebraic structures on Grassmann manifolds and related with Lax type flows is proposed. Making use of the differential geometric techniques it is shown that associated holonomy groups properly realizing quantum computation can be effectively found concerning polynomial problems. Two examples demonstrating calculation aspects of holonomic quantum computer and maximum clique problems in very large graphs, are considered in detail.
Geometrical aspects of quantum computing are reviewed elementarily for nonexperts and/or graduate students who are interested in both geometry and quantum computation. We show how to treat Grassmann manifolds which are very important examples of manifolds in mathematics and physics. Some of their applications to quantum computation and its efficiency problems are shown. An interesting current topic of holonomic quantum computation is also covered. Also, some related advanced topics are discussed.
This paper deals with the progress made in applications of quantum computing in control and optimization. It concentrates on applying the geometric technique in order to investigate a finite control problem of a two-level quantum system, resonance control of a three-level system, simulation of bilinear quantum control systems, and optimal control using the Bellman principle. We show that a quantum object described by a Schroedinger equation can be controlled in an optimal way by electromagnetic modes. We also demonstrate an application of these techniques and an algebra-geometric approach to the study of dynamic processes in nonlinear systems. The information processing by means of controlled quantum lattices is discussed: we present new mathematical models of classical (CL) and quantum-mechanical lattices (QML) and their application to information processing. system-theoretical results on the observability, controllability and minimal realizability theorems are formulated for cl. The cellular dynamaton (CD) based on quantum oscillators is presented. Cellular's quantum computational search procedure can provide the basis for implementing adaptive global optimization algorithms. A brief overview of the procedure is given and a framework called lattice adaptive search is set up. A method of Yatsenko and one introduced by the authors fit into this framework and are compared.
Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with A,BA,BA,B symmetric, and BBB positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when BBB is invertible, B−1AB^{-1}AB−1A is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when BBB is singular, any quantum algorithm uses at least Ω(n)\Omega(\sqrt{n})Ω(n​) queries to compute the eigenvalues, where nnn is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.
This thesis focuses on the optimal control of a class of closed 1 quantum systems. It encompasses and addresses the following themes 1. The theoretical underpinnings of the dynamic programming method for quantum spin systems. 2. The efficient numerical implementation of algorithms to generate optimal control laws. The use of the dynamic programming principle from optimal control theory for the control of quantum systems is introduced, while taking into account the properties of the manifolds on which they evolve. This enables the unified application of dynamic programming to disparate problems which were previously approached using distinct tools. Moreover the approach herein is applicable, in principle, to an arbitrarily large quantum system - thereby overcoming the limitations present in some other commonly used methods in the literature, on the size of the quantum system being analyzed. As the optimal cost function is non-differentiable in several cases of interest, this thesis provides a rigorous interpretation of this cost function in terms of viscosity solutions of the associated Hamilton-Jacobi-Bellman (HJB) partial differential equation (PDE) over the manifolds of interest. This framework is applied to explore optimal control strategies for drift and drift-less quantum systems that arise in various applications - thus demonstrating the efficacy of a unified approach to address problems on qualitatively different systems. This thesis also investigates, via two distinct avenues, the efficient numerical solution to optimal control problems of interest. Firstly, it brings together the Markov chain ap- proximation methods of Kushner-Dupuis and the triangulation of manifolds introduced by Munkres, in order to numerically solve the optimal control problem on quantum systems via a value iteration approach. Secondly, the exponential growth in computational resources required - termed the curse of dimensionality (COD) -inherent in any spatial discretization approach to solving the HJB PDE is drastically lessened via a new reduced complexity method motivated by the COD free max-plus technique recently developed by McEneaney et al. The dramatic speedup obtained by this approach enables an approximate solution to a previously intractable optimal control problem for a two qubit2 spin system evolving on a 15 dimensional Lie group.
Many challenges in quantum information and quantum control root in constrained optimization problems on finite-dimensional quantum systems. The constraints often arise from two facts: (i) quantum dynamic state spaces are naturally smooth manifolds (orbits of the respective initial states) rather than being Hilbert spaces; (ii) the dynamics of the respective quantum system may be restricted to a proper subset of the entire state space. Mathematically, either case can be treated by constrained optimization over the reachable set of an underlying control system. Thus, whenever the reachable set takes the form a smooth manifold, Riemannian optimization methods apply. Here, we give a comprehensive account on the foundations of gradient flows on Riemannian manifolds including new applications in quantum information and quantum dynamics. Yet, we do not pursue the problem of designing explicit controls for the underlying control systems. The framework is sufficiently general for setting up gradient flows on (sub)manifolds, Lie (sub)groups, and (reductive) homogeneous spaces. Relevant convergence conditions are discussed, in particular for gradient flows on compact and analytic manifolds. This is meant to serve as foundation for new achievements and further research. Illustrative examples and new applications are given: we extend former results on unitary groups to closed subgroups with tensor-product structure, where the finest product partitioning relates to SUloc(2n) := SU(2) ⊗ ⋯ ⊗ SU(2) — known as (qubit-wise) local unitary operations. Such applications include, e.g., optimizing figures of merit on SUloc(2n) relating to distance measures of pure-state entanglement as well as to best rank-1 approximations of higher-order tensors. In quantum information, our gradient flows provide a numerically favorable alternative to standard tensor-SVD techniques.
Gradient-based algorithms provide the fundamental tools for the optimizations and are the essential components of many modern technologies. Theoretically, the extreme points of a cost function can be found by iterative descent(ascent) of the variable along the direction of the gradient. However, the time complexity to calculate a gradient is at a level of O(poly(d))O(poly(d))O(poly(d)) for the ddd-dimension problems. For processing the high-dimension case, especially modern machine-learning engineering with the number of optimized parameters being in billions, quantum techniques are introduced. Via the dressed amplitude encoding and nonunitary module, a gradient-based quantum optimization algorithm for general polynomials is proposed, aiming at solving the fast-convergence problems with both time and memory complexity in O(poly(logd))O(poly(logd))O(poly(logd)). Furthermore, numerical simulations are carried out to inspect the performance of the newly born protocol by considering the noises or perturbations during the initialization, operations, and truncations. For the potential values in high-dimension optimizations, this gradient-based quantum optimization algorithm is supposed to facilitate the polynomial optimizations, being a subroutine for future practical quantum computers.