Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems

Abstract

Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. The quality of the solution obtained by QAOA for a given problem instance depends on the performance of the classical optimizer used to optimize the variational parameters. In this paper, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances. To this end, we develop two machine-learning-based approaches. Our first approach adopts a reinforcement learning (RL) framework to learn a policy network to optimize QAOA circuits. Our second approach adopts a kernel density estimation (KDE) technique to learn a generative model of optimal QAOA parameters. In both approaches, the training procedure is performed on small-sized problem instances that can be simulated on a classical computer; yet the learned RL policy and the generative model can be used to efficiently solve larger problems. Extensive simulations using the IBM Qiskit Aer quantum circuit simulator demonstrate that our proposed RL- and KDE-based approaches reduce the optimality gap by factors up to 30.15 when compared with other commonly used off-the-shelf optimizers.

To appear in the proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI), New York, USA, February 2020

Cited by in corpus (34)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Warm-starting quantum optimization
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• QuASeR -- Quantum Accelerated De Novo DNA Sequence Reconstruction
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• Benchmarking quantum co-processors in an application-centric, hardware-agnostic and scalable way
• Quantum approximate optimization via learning-based adaptive optimization
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Symmetry enhanced variational quantum spin eigensolver
• Exploiting Symmetry Reduces the Cost of Training QAOA
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Quantum imaginary time evolution steered by reinforcement learning
• Surrogate-based optimization for variational quantum algorithms
• Reinforcement Learning Assisted Recursive QAOA
• Performance Evaluation and Acceleration of the QTensor Quantum Circuit Simulator on GPUs
• Quantum Approximate Multi-Objective Optimization
• Quantum Optimization for Training Quantum Neural Networks
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization
• Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey
• A quantum information theoretic analysis of reinforcement learning-assisted quantum architecture search
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• QCEDA: Using Quantum Computers for EDA
• Reinforcement learning to learn quantum states for Heisenberg scaling accuracy
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Unsupervised strategies for identifying optimal parameters in Quantum Approximate Optimization Algorithm