QSlack: A slack-variable approach for variational quantum semi-definite programming

Abstract

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 semi-definite programming (SDP) and linear programming (LP) have wide applicability in many domains of computer science, engineering, mathematics, and physics. Here we focus on semi-definite 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 non-negative 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 order $10^{-2}$.

arXiv comment66 pages, 11 figures

References in corpus (68)

• Quantum entanglement
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A computable measure of entanglement
• A variational eigenvalue solver on a quantum processor
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum computational chemistry
• Quantum Circuit Learning
• Quantum Chemistry in the Age of Quantum Computing
• On the volume of the set of mixed entangled states
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum optimization using variational algorithms on near-term quantum devices
• Efficient variational quantum simulator incorporating active error minimisation
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Quantum Error Mitigation
• A rigorous and robust quantum speed-up in supervised machine learning
• Quantum Natural Gradient
• Tools for quantum simulation with ultracold atoms in optical lattices
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• A generative modeling approach for benchmarking and training shallow quantum circuits
• Quantum Boltzmann Machine
• Semiconductor Qubits In Practice
• Qulacs: a fast and versatile quantum circuit simulator for research purpose
• Differentiable Learning of Quantum Circuit Born Machine
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• Unsupervised Generative Modeling Using Matrix Product States
• Effect of barren plateaus on gradient-free optimization
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Superconductor-semiconductor hybrid cavity quantum electrodynamics
• Efficient estimation of Pauli observables by derandomization
• The SWAP test and the Hong-Ou-Mandel effect are equivalent
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Barren plateaus preclude learning scramblers
• Tree Tensor Networks for Generative Modeling
• Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
• Information Perspective to Probabilistic Modeling: Boltzmann Machines versus Born Machines
• Engineering of Microfabricated Ion Traps and Integration of Advanced On-Chip Features
• Quantum SDP-Solvers: Better upper and lower bounds
• Hamiltonian Simulation with Optimal Sample Complexity
• Semidefinite Programming in Quantum Information Science
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Noiseless Quantum Circuits for the Peres Separability Criterion
• Quantum algorithms: A survey of applications and end-to-end complexities
• Detecting and quantifying entanglement on near-term quantum devices
• Semidefinite programs for completely bounded norms
• Solving condensed-matter ground-state problems by semidefinite relaxations
• Trainability barriers and opportunities in quantum generative modeling
• Efficient description of many-body systems with Matrix Product Density Operators
• Adaptive estimation of quantum observables
• Estimating distinguishability measures on quantum computers
• Noisy intermediate-scale quantum algorithm for semidefinite programming
• Quantum Mixed State Compiling
• Bell sampling from quantum circuits
• A Semidefinite Programming algorithm for the Quantum Mechanical Bootstrap
• Quantum Neural Estimation of Entropies
• Variational Quantum Algorithms for Semidefinite Programming
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
• Entropy Constraints for Ground Energy Optimization
• Near-term Efficient Quantum Algorithms for Entanglement Analysis
• Efficient quantum algorithms for testing symmetries of open quantum systems

Cited by in corpus (5)

• Dual-VQE: A quantum algorithm to lower bound the ground-state energy
• Evolved Quantum Boltzmann Machines
• Quantum natural gradient with thermal-state initialization
• Resource-Efficient Quantum Optimization via Higher-Order Encoding
• Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems