More Like this

1. Toward perturbation theory methods on a quantum computer

   https://doi.org/10.1126/sciadv.adg4576  

   Li, Junxu; Jones, Barbara A; Kais, Sabre (May 2023, Science Advances)

   Perturbation theory, used in a wide range of fields, is a powerful tool for approximate solutions to complex problems, starting from the exact solution of a related, simpler problem. Advances in quantum computing, especially over the past several years, provide opportunities for alternatives to classical methods. Here, we present a general quantum circuit estimating both the energy and eigenstates corrections that is far superior to the classical version when estimating second-order energy corrections. We demonstrate our approach as applied to the two-site extended Hubbard model. In addition to numerical simulations based on qiskit, results on IBM’s quantum hardware are also presented. Our work offers a general approach to studying complex systems with quantum devices, with no training or optimization process needed to obtain the perturbative terms, which can be generalized to other Hamiltonian systems both in chemistry and physics. 

   more » « less
2. Techniques for blocking the propagation of two simultaneous contagions over networks using a graph dynamical systems framework

   https://doi.org/10.1017/nws.2022.18  

   Carscadden, Henry L.; Kuhlman, Chris J.; Marathe, Madhav V.; Ravi, S. S.; Rosenkrantz, Daniel J. (September 2022, Network Science)

   Abstract We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm. 

   more » « less
3. Decentralized Resilient State-Tracking

   https://doi.org/10.1109/CDC45484.2021.9683313  

   Mao, Yanwen; Tabuada, Paulo (December 2021, 2021 60th IEEE Conference on Decision and Control (CDC))

   We study the decentralized resilient state-tracking problem in which each node in a network has the objective of tracking the state of a linear dynamical system based on its local measurements and information exchanged with its neighboring nodes, despite an attack on some of the nodes. We propose a novel algorithm that solves the decentralized resilient state-tracking problem by relating it to the dynamic average consensus problem. Compared with existing solutions in the literature, our algorithm provides a solution for the most general class of decentralized resilient state-tracking problem instances. 

   more » « less
4. Reinforcement Learning with Sparse Rewards using Guidance from Offline Demonstration

   Rengarajan, D.; Vaidya, G.; Sarvesh, A.; Kalathil, D.; Shakkottai, S (April 2022, International Conference on Learning Representations (ICLR))

   A major challenge in real-world reinforcement learning (RL) is the sparsity of reward feedback. Often, what is available is an intuitive but sparse reward function that only indicates whether the task is completed partially or fully. However, the lack of carefully designed, fine grain feedback implies that most existing RL algorithms fail to learn an acceptable policy in a reasonable time frame. This is because of the large number of exploration actions that the policy has to perform before it gets any useful feedback that it can learn from. In this work, we address this challenging problem by developing an algorithm that exploits the offline demonstration data generated by a sub-optimal behavior policy for faster and efficient online RL in such sparse reward settings. The proposed algorithm, which we call the Learning Online with Guidance Offline (LOGO) algorithm, merges a policy improvement step with an additional policy guidance step by using the offline demonstration data. The key idea is that by obtaining guidance from - not imitating - the offline data, LOGO orients its policy in the manner of the sub-optimal policy, while yet being able to learn beyond and approach optimality. We provide a theoretical analysis of our algorithm, and provide a lower bound on the performance improvement in each learning episode. We also extend our algorithm to the even more challenging incomplete observation setting, where the demonstration data contains only a censored version of the true state observation. We demonstrate the superior performance of our algorithm over state-of-the-art approaches on a number of benchmark environments with sparse rewards and censored state. Further, we demonstrate the value of our approach via implementing LOGO on a mobile robot for trajectory tracking and obstacle avoidance, where it shows excellent performance. 

   more » « less
5. On Global and Local Convergence of Iterative Linear Quadratic Optimization Algorithms for Discrete Time Nonlinear Control

   Roulet, V; Srinivasa, S; Fazel, M; Harchaoui, Z (May 2025, Journal of machine learning research)

   Jaggi, Martin (Ed.)

   A classical approach for solving discrete time nonlinear control on a nite horizon consists in repeatedly minimizing linear quadratic approximations of the original problem around current candidate solutions. While widely popular in many domains, such an approach has mainly been analyzed locally. We provide detailed convergence guarantees to stationary points as well as local linear convergence rates for the Iterative Linear Quadratic Regulator (ILQR) algorithm and its Di erential Dynamic Programming (DDP) variant. For problems without costs on control variables, we observe that global convergence to minima can be ensured provided that the linearized discrete time dynamics are surjective, costs on the state variables are gradient dominated. We further detail quadratic local convergence when the costs are self-concordant. We show that surjectivity of the linearized dynamics hold for appropriate discretization schemes given the existence of a feedback linearization scheme. We present complexity bounds of algorithms based on linear quadratic approximations through the lens of generalized Gauss-Newton methods. Our analysis uncovers several convergence phases for regularized generalized Gauss-Newton algorithms. 

   more » « less