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

arXiv:1402.1436

Bundle-based pruning in the max-plus curse of dimensionality free method

Stéphane Gaubert, Zheng Qu, Srinivas Sridharan

Published Feb 6, 2014• 5 citations
arXivHTMLPDF

Abstract

Recently a new class of techniques termed the max-plus curse of dimensionality-free methods have been developed to solve nonlinear optimal control problems. In these methods the discretization in state space is avoided by using a max-plus basis expansion of the value function. This requires storing only the coefficients of the basis functions used for representation. However, the number of basis functions grows exponentially with respect to the number of time steps of propagation to the time horizon of the control problem. This so called "curse of complexity" can be managed by applying a pruning procedure which selects the subset of basis functions that contribute most to the approximation of the value function. The pruning procedures described thus far in the literature rely on the solution of a sequence of high dimensional optimization problems which can become computationally expensive. In this paper we show that if the max-plus basis functions are linear and the region of interest in state space is convex, the pruning problem can be efficiently solved by the bundle method. This approach combining the bundle method and semidefinite formulations is applied to the quantum gate synthesis problem, in which the state space is the special unitary group (which is non-convex). This is based on the observation that the convexification of the unitary group leads to an exact relaxation. The results are studied and validated via examples.

DOI
10.48550/arxiv.1402.1436

Related papers

Reduced-complexity numerical method for optimal gate synthesis

Srinivas Sridharan, Mile Gu, M. R. James +1 more

Although quantum computers have the potential to efficiently solve certain problems considered difficult by known classical approaches, the design of a quantum circuit remains computationally difficult. It is known that the optimal gate-design problem is equivalent to the solution of an associated optimal-control problem; the solution to which is also computationally intensive. Hence, in this article, we introduce the application of a class of numerical methods (termed the max-plus curse of dimensionality-free techniques) that determine the optimal control, thereby synthesizing the desired unitary gate. The application of this technique to quantum systems has a growth in complexity that depends on the cardinality of the control-set approximation rather than the much larger growth with respect to spatial dimensions in approaches based on gridding of the space, which is used in previous research. This technique is demonstrated by obtaining an approximate solution for the gate synthesis on SU(4)---a problem that is computationally intractable by grid-based approaches.

arXiv:1011.6013•Physical Review A•Oct 20, 2010•21 citations

An efficient computational method for the optimal control of higher dimensional quantum systems

Srinivas Sridharan, Mile Gu, M. R. James +1 more

The process of obtaining solutions to optimal control problems via mesh based techniques suffers from the well known problem of the curse of dimensionality. This issue is especially severe in quantum systems whose dimensions grow exponentially with the number of interacting elements (qubits) that they contain. In this article we develop a modification of recently introduced curse-of-dimensionality-free max-plus techniques, to the control of quantum systems. This method yields a more manageable growth that is related to the cardinality of the control set. Its efficacy is demonstrated by obtaining an approximate solution to a previously intractable problem on a 2 qubit system.

IEEE Conference on Decision and Control (CDC)•Dec 1, 2010•4 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

Computational techniques for optimal control of quantum systems

Evangelos A. Coutsias, G. von Winckel

The control of matter and energy at a fundamental level will be a cornerstone of new technologies for years to come. This idea is exemplified in a distilled form by controlling the dynamics of quantum mechanical systems via a time-dependent potential. The contributions detailed within this work focus on the computational aspects of formulating and solving quantum control problems efficiently. The accurate numerical computation of optimal controls of infinite dimensional quantum control problems is a very difficult task that requires to take into account the features of the original infinite dimensional problem. An important issue is the choice of the functional space where the minimization process is defined. A systematic comparison of L2 versus H1 based minimization shows that the choice of the appropriate functional space matters and has many consequences in the implementation of some optimization techniques. A matrix-free cascadic BFGS algorithm is introduced in the L 2 and H1 settings and it is demonstrated that the choice of H1 over L2 results in a substantial performance and robustness increase. A comparison between optimal control resulting from function space minimization and the control obtained by minimization over Chebyshev and POD basis function coefficients is presented. A theoretical and computational framework is presented to obtain accurate controls for fast quantum state transitions that are needed in a host of applications such as nano electronic devices and quantum computing. This method is based on a reduced Hessian Krylov-Newton scheme applied to a norm-preserving discrete model of a dipole quantum control problem. The use of second-order numerical methods for solving the control problem is justified proving existence of optimal solutions and analyzing first- and second-order optimality conditions. Criteria for the discretization of the non-convex optimization problem and for the formulation of the Hessian are given to ensure accurate gradients and a symmetric Hessian. Robustness of the Newton approach is obtained using a globalization strategy with a robust linesearch procedure. Results of numerical experiments demonstrate that the Newton approach presented in this dissertation is able to provide fast and accurate controls for high-energy state transitions. Control of bound-to-bound and bound-to-continuum transitions in open quantum systems and vector field control of two-dimensional systems is presented. An efficient space-time spectral discretization of the time-dependent Schrodinger equation and preconditioning strategy for a fast approximate solution with Krylov methods is outlined.

•Jan 1, 2011•0 citations

A reduced complexity min-plus method for synchronisation of qubits

Zibo Miao, Peter M. Dower

Solutions to optimal control problems can be obtained via grid-based dynamic programming iterations. However, such an approach is prohibitively expensive for problems with higher state dimensions, due to the exponential increase in grid points required in approximating the state space. This issue is especially severe in quantum systems whose dimensions grow exponentially with the number of interacting subsystems therein. In this paper, we study state synchronisation of two coupled qubits as an optimal control problem by tuning the interaction Hamiltonian of the system, whose dynamic programming equation is solved via a min-plus curse-of-dimensionality-free method. An illustration in the context of numerical examples is also provided.

Australian Control Conference•Nov 1, 2016•0 citations

Quantum-Inspired Sparse Optimization Algorithms for High-Dimensional Problems

K.Madhan

The curse of dimensionality in high-dimensional optimization: It is inherently seen that the dimensionality of feature space presents a fundamental challenge to high-dimensional optimization: as dimensionality increases, feature space becomes computationally inefficient, overfitted and model interpretability declines, thus requiring highly robust sparsity-based solutions. To find a solution to these problems, a new quantum-inspired framework of sparse optimization is proposed in this study, which combines probabilistic Q-bit representation and L1-regularized optimization to efficiently consider large solution spaces but with a sparsity constraint. The suggested method builds on quantum-inspired search algorithms such as initiation by superposition and rotation gate updates to the search to improved exploration and exploitation ratio, leading to a better convergence process. Experimental analyses show that the framework produces better optimization accuracy, indicated by much lower Mean Squared Error (MSE) and convergence rates than classical and met heuristic baselines, with the framework also having a higher level of sparsity in the solution space. These results highlight the effectiveness of the proposed method in handling high-dimensional problems, making it particularly suitable for applications in signal processing, machine learning-based feature selection, and large-scale scientific computing tasks.

Frontiers in Computational Science and Engineering•May 13, 2026•0 citations
Recently a new class of techniques termed the max-plus curse of dimensionality-free methods have been developed to solve nonlinear optimal control problems. In these methods the discretization in state space is avoided by using a max-plus basis expansion of the value function. This requires storing only the coefficients of the basis functions used for representation. However, the number of basis functions grows exponentially with respect to the number of time steps of propagation to the time horizon of the control problem. This so called "curse of complexity" can be managed by applying a pruning procedure which selects the subset of basis functions that contribute most to the approximation of the value function. The pruning procedures described thus far in the literature rely on the solution of a sequence of high dimensional optimization problems which can become computationally expensive. In this paper we show that if the max-plus basis functions are linear and the region of interest in state space is convex, the pruning problem can be efficiently solved by the bundle method. This approach combining the bundle method and semidefinite formulations is applied to the quantum gate synthesis problem, in which the state space is the special unitary group (which is non-convex). This is based on the observation that the convexification of the unitary group leads to an exact relaxation. The results are studied and validated via examples.
Although quantum computers have the potential to efficiently solve certain problems considered difficult by known classical approaches, the design of a quantum circuit remains computationally difficult. It is known that the optimal gate-design problem is equivalent to the solution of an associated optimal-control problem; the solution to which is also computationally intensive. Hence, in this article, we introduce the application of a class of numerical methods (termed the max-plus curse of dimensionality-free techniques) that determine the optimal control, thereby synthesizing the desired unitary gate. The application of this technique to quantum systems has a growth in complexity that depends on the cardinality of the control-set approximation rather than the much larger growth with respect to spatial dimensions in approaches based on gridding of the space, which is used in previous research. This technique is demonstrated by obtaining an approximate solution for the gate synthesis on SU(4)---a problem that is computationally intractable by grid-based approaches.
The process of obtaining solutions to optimal control problems via mesh based techniques suffers from the well known problem of the curse of dimensionality. This issue is especially severe in quantum systems whose dimensions grow exponentially with the number of interacting elements (qubits) that they contain. In this article we develop a modification of recently introduced curse-of-dimensionality-free max-plus techniques, to the control of quantum systems. This method yields a more manageable growth that is related to the cardinality of the control set. Its efficacy is demonstrated by obtaining an approximate solution to a previously intractable problem on a 2 qubit system.
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.
The control of matter and energy at a fundamental level will be a cornerstone of new technologies for years to come. This idea is exemplified in a distilled form by controlling the dynamics of quantum mechanical systems via a time-dependent potential. The contributions detailed within this work focus on the computational aspects of formulating and solving quantum control problems efficiently. The accurate numerical computation of optimal controls of infinite dimensional quantum control problems is a very difficult task that requires to take into account the features of the original infinite dimensional problem. An important issue is the choice of the functional space where the minimization process is defined. A systematic comparison of L2 versus H1 based minimization shows that the choice of the appropriate functional space matters and has many consequences in the implementation of some optimization techniques. A matrix-free cascadic BFGS algorithm is introduced in the L 2 and H1 settings and it is demonstrated that the choice of H1 over L2 results in a substantial performance and robustness increase. A comparison between optimal control resulting from function space minimization and the control obtained by minimization over Chebyshev and POD basis function coefficients is presented. A theoretical and computational framework is presented to obtain accurate controls for fast quantum state transitions that are needed in a host of applications such as nano electronic devices and quantum computing. This method is based on a reduced Hessian Krylov-Newton scheme applied to a norm-preserving discrete model of a dipole quantum control problem. The use of second-order numerical methods for solving the control problem is justified proving existence of optimal solutions and analyzing first- and second-order optimality conditions. Criteria for the discretization of the non-convex optimization problem and for the formulation of the Hessian are given to ensure accurate gradients and a symmetric Hessian. Robustness of the Newton approach is obtained using a globalization strategy with a robust linesearch procedure. Results of numerical experiments demonstrate that the Newton approach presented in this dissertation is able to provide fast and accurate controls for high-energy state transitions. Control of bound-to-bound and bound-to-continuum transitions in open quantum systems and vector field control of two-dimensional systems is presented. An efficient space-time spectral discretization of the time-dependent Schrodinger equation and preconditioning strategy for a fast approximate solution with Krylov methods is outlined.
Solutions to optimal control problems can be obtained via grid-based dynamic programming iterations. However, such an approach is prohibitively expensive for problems with higher state dimensions, due to the exponential increase in grid points required in approximating the state space. This issue is especially severe in quantum systems whose dimensions grow exponentially with the number of interacting subsystems therein. In this paper, we study state synchronisation of two coupled qubits as an optimal control problem by tuning the interaction Hamiltonian of the system, whose dynamic programming equation is solved via a min-plus curse-of-dimensionality-free method. An illustration in the context of numerical examples is also provided.
The curse of dimensionality in high-dimensional optimization: It is inherently seen that the dimensionality of feature space presents a fundamental challenge to high-dimensional optimization: as dimensionality increases, feature space becomes computationally inefficient, overfitted and model interpretability declines, thus requiring highly robust sparsity-based solutions. To find a solution to these problems, a new quantum-inspired framework of sparse optimization is proposed in this study, which combines probabilistic Q-bit representation and L1-regularized optimization to efficiently consider large solution spaces but with a sparsity constraint. The suggested method builds on quantum-inspired search algorithms such as initiation by superposition and rotation gate updates to the search to improved exploration and exploitation ratio, leading to a better convergence process. Experimental analyses show that the framework produces better optimization accuracy, indicated by much lower Mean Squared Error (MSE) and convergence rates than classical and met heuristic baselines, with the framework also having a higher level of sparsity in the solution space. These results highlight the effectiveness of the proposed method in handling high-dimensional problems, making it particularly suitable for applications in signal processing, machine learning-based feature selection, and large-scale scientific computing tasks.