Improving Variational Quantum Optimization using CVaR

Abstract

Hybrid quantum/classical variational algorithms can be implemented on noisy intermediate-scale quantum computers and can be used to find solutions for combinatorial optimization problems. Approaches discussed in the literature minimize the expectation of the problem Hamiltonian for a parameterized trial quantum state. The expectation is estimated as the sample mean of a set of measurement outcomes, while the parameters of the trial state are optimized classically. This procedure is fully justified for quantum mechanical observables such as molecular energies. In the case of classical optimization problems, which yield diagonal Hamiltonians, we argue that aggregating the samples in a different way than the expected value is more natural. In this paper we propose the Conditional Value-at-Risk as an aggregation function. We empirically show -- using classical simulation as well as quantum hardware -- that this leads to faster convergence to better solutions for all combinatorial optimization problems tested in our study. We also provide analytical results to explain the observed difference in performance between different variational algorithms.

11 pages, 9 figures, accepted in Quantum

References in corpus (7)

• A variational eigenvalue solver on a quantum processor
• Quantum Mechanics helps in searching for a needle in a haystack
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Quantum optimization using variational algorithms on near-term quantum devices
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• qTorch: The Quantum Tensor Contraction Handler

Cited by in corpus (90)

• Noisy intermediate-scale quantum (NISQ) algorithms
• The Variational Quantum Eigensolver: a review of methods and best practices
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Computing for Finance: State of the Art and Future Prospects
• Warm-starting quantum optimization
• Challenges and Opportunities in Quantum Optimization
• Resource-Efficient Quantum Algorithm for Protein Folding
• Differentiable Quantum Architecture Search
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Filtering variational quantum algorithms for combinatorial optimization
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Variational Quantum Boltzmann Machines
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• A case study of variational quantum algorithms for a job shop scheduling problem
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms
• Variational Quantum Singular Value Decomposition
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• Quantum variational optimization: The role of entanglement and problem hardness
• Graph neural network initialisation of quantum approximate optimisation
• Low depth mechanisms for quantum optimization
• Challenges of variational quantum optimization with measurement shot noise
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem
• Hybrid quantum-classical optimization for financial index tracking
• Quantum State Discrimination Using Noisy Quantum Neural Networks
• Noise robustness and experimental demonstration of a quantum generative adversarial network for continuous distributions
• Approximating the quantum approximate optimization algorithm with digital-analog interactions
• An evolving objective function for improved variational quantum optimisation
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Provable bounds for noise-free expectation values computed from noisy samples
• Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection
• The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization
• Quantum Optimization for Training Quantum Neural Networks
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
• Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Variational quantum solutions to the Shortest Vector Problem
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• How to enhance quantum generative adversarial learning of noisy information
• Non-Markovian feedback for optimized quantum error correction
• Quantum-Enhanced Simulation-Based Optimization
• A blueprint for a Digital-Analog Variational Quantum Eigensolver using Rydberg atom arrays
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Variational quantum eigensolver with linear depth problem-inspired ansatz for solving portfolio optimization in finance
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization
• Supervised learning of random quantum circuits via scalable neural networks
• Enhancing VQE Convergence for Optimization Problems with Problem-specific Parameterized Quantum Circuits
• A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems
• Photonic counterdiabatic quantum optimization algorithm
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer
• An approach to solve the coarse-grained Protein folding problem in a Quantum Computer
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• Random Natural Gradient
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems
• Demonstration of Hardware Efficient Photonic Variational Quantum Algorithm
• Charged particle reconstruction for future high energy colliders with Quantum Approximate Optimization Algorithm
• Tabu-driven Quantum Neighborhood Samplers
• Pitfalls when tackling the exponential concentration of parameterized quantum models
• Utility of NISQ devices: optimizing experimental parameters for the fabrication of Au atomic junction using gate-based quantum computers
• Adiabatic quantum computing with parameterized quantum circuits
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Investigating Techniques to Optimise the Layout of Turbines in a Windfarm using a Quantum Computer
• Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems
• Gaussian Boson Sampling for binary optimization
• Surrogate Modeling via Factorization Machine and Ising Model with Enhanced Higher-Order Interaction Learning
• Challenges and opportunities in the supervised learning of quantum circuit outputs
• The Quantum Ensemble Variational Optimization Algorithm: Applications to Molecular Inverse Design
• Improving the trainability of VQE on NISQ computers for solving portfolio optimization using convex interpolation
• Pangenome-guided sequence assembly via binary optimisation