Knapsack Problem variants of QAOA for battery revenue optimisation

Abstract

We implement two Quantum Approximate Optimisation Algorithm (QAOA) variants for a battery revenue optimisation problem, equivalent to the weakly NP-hard Knapsack Problem. Both approaches investigate how to tackle constrained problems with QAOA. A first 'constrained' approach introduces a quadratic penalty to enforce the constraint to be respected strictly and reformulates the problem into an Ising Problem. However, simulations on IBM's simulator highlight non-convergent results for intermediate depth ($p\le 50$). A second 'relaxed' approach applies the QAOA with a non-Ising target function to compute a linear penalty, running in time $O(p({\log }_{2}n{)}^3)$ and needing $O(n\log n)$ qubits. Simulations reveal an exponential improvement over the number of depth levels and obtain approximations about $0.95$ of the optimum with shallow depth ($p\le 10$).

References in corpus (9)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Quantum Approximate Optimization Algorithm
• Quantum Networks for Elementary Arithmetic Operations
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• An Elementary Proof of the Quantum Adiabatic Theorem
• Adiabatic quantum computing solution of the knapsack problem

Cited by in corpus (6)

• Noisy intermediate-scale quantum (NISQ) algorithms
• NISQ Computers: A Path to Quantum Supremacy
• Elementary Proof of QAOA Convergence
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers