Combinatorial Optimization on Gate Model Quantum Computers: A Survey

Abstract

The advent of quantum computing processors with possibility to scale beyond experimental capacities magnifies the importance of studying their applications. Combinatorial optimization problems can be one of the promising applications of these new devices. These problems are recurrent in industrial applications and they are in general difficult for classical computing hardware. In this work, we provide a survey of the approaches to solving different types of combinatorial optimization problems, in particular quadratic unconstrained binary optimization (QUBO) problems on a gate model quantum computer. We focus mainly on four different approaches including digitizing the adiabatic quantum computing, global quantum optimization algorithms, the quantum algorithms that approximate the ground state of a general QUBO problem, and quantum sampling. We also discuss the quantum algorithms that are custom designed to solve certain types of QUBO problems.

References in corpus (21)

• Quantum Machine Learning
• Elementary gates for quantum computation
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Towards Quantum Chemistry on a Quantum Computer
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Grover's quantum searching algorithm is optimal
• Towards fault-tolerant quantum computing with trapped ions
• Robustness of adiabatic quantum computation
• Digitized adiabatic quantum computing with a superconducting circuit
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Quantum Metropolis Sampling
• A case study in programming a quantum annealer for hard operational planning problems
• Quantum Optimization of Fully-Connected Spin Glasses
• Quantum Annealing Implementation of Job-Shop Scheduling
• Nested quantum search and NP-complete problems
• Evolutionary Algorithms for Hard Quantum Control
• Introduction to Quantum Algorithms
• Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
• Quantum Optimization

Cited by in corpus (6)

• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
• Representation of binary classification trees with binary features by quantum circuits
• Hybrid Quantum-Classical Unit Commitment
• A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing
• AEQUAM: Accelerating Quantum Algorithm Validation through FPGA-Based Emulation