An evolving objective function for improved variational quantum optimisation

Abstract

A promising approach to useful computational quantum advantage is to use variational quantum algorithms for optimisation problems. Crucial for the performance of these algorithms is to ensure that the algorithm converges with high probability to a near-optimal solution in a small time. In Barkoutsos et al (Quantum 2020) an alternative class of objective functions, called Conditional Value-at-Risk (CVaR), was introduced and it was shown that they perform better than standard objective functions. Here we extend that work by introducing an evolving objective function, which we call Ascending-CVaR and that can be used for any optimisation problem. We test our proposed objective function, in an emulation environment, using as case-studies three different optimisation problems: Max-Cut, Number Partitioning and Portfolio Optimisation. We examine multiple instances of different sizes and analyse the performance using the Variational Quantum Eigensolver (VQE) with hardware-efficient ansatz and the Quantum Approximate Optimization Algorithm (QAOA). We show that Ascending-CVaR in all cases performs better than standard objective functions or the "constant" CVaR of Barkoutsos et al (Quantum 2020) and that it can be used as a heuristic for avoiding sub-optimal minima. Our proposal achieves higher overlap with the ideal state in all problems, whether we consider easy or hard instances -- on average it gives up to ten times greater overlap at Portfolio Optimisation and Number Partitioning, while it gives an 80% improvement at Max-Cut. In the hard instances we consider, for the number partitioning problem, standard objective functions fail to find the correct solution in almost all cases, CVaR finds the correct solution at 60% of the cases, while Ascending-CVaR finds the correct solution in 95% of the cases.

arXiv comment20 pages, 13 figures; v3 published version

References in corpus (34)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Barren plateaus in quantum neural network training landscapes
• A Quantum Approximate Optimization Algorithm
• Adiabatic Quantum Computing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Towards Practical Quantum Variational Algorithms
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum computing for finance: overview and prospects
• Quantum optimization using variational algorithms on near-term quantum devices
• Generalized Unitary Coupled Cluster Wavefunctions for Quantum Computation
• Training variational quantum algorithms is NP-hard
• A generative modeling approach for benchmarking and training shallow quantum circuits
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Layerwise learning for quantum neural networks
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Improving Variational Quantum Optimization using CVaR
• Sequential minimal optimization for quantum-classical hybrid algorithms
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Information Perspective to Probabilistic Modeling: Boltzmann Machines versus Born Machines
• Reinforcement Learning assisted Quantum Optimization
• Quantum walk-based portfolio optimisation
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems

Cited by in corpus (8)

• Graph neural network initialisation of quantum approximate optimisation
• Challenges of variational quantum optimization with measurement shot noise
• Variational quantum solutions to the Shortest Vector Problem
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization
• Variational quantum eigensolver with linear depth problem-inspired ansatz for solving portfolio optimization in finance
• Random Natural Gradient
• Adiabatic quantum computing with parameterized quantum circuits
• Pangenome-guided sequence assembly via binary optimisation