Combinatorial Optimization on Gate Model Quantum Computers: A Survey

By Ehsan Zahedinejad & Arman Zaribafiyan
The advent of quantum computing processors with the 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 adiabatic quantum computing, global quantum optimization algorithms, 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.

Most Recent Papers

Variationally Scheduled Quantum Simulation

By Shunji Matsuura, Samantha Buck, Valentin Senicourt, & Arman Zaribafiyan Eigenstate preparation is ubiquitous in quantum computing, and a standard approach for generating the lowest-energy states of a given system is by employing adiabatic state preparation...

A Quantum Annealing-Based Approach to Extreme Clustering

By Tim Jaschek, Marko Bucyk, & Jaspreet S. Oberoi Clustering, or grouping, dataset elements based on similarity can be used not only to classify a dataset into a few categories, but also to approximate it by a relatively large number of representative elements. In...