  Considerable effort has been made recently in the development of heuristic
quantum algorithms for solving combinatorial optimization problems. Meanwhile,
these problems have been studied extensively in classical computing for
decades. In this paper, we explore a natural approach to leveraging existing
classical techniques to enhance quantum optimization. Specifically, we run a
classical algorithm to find an approximate solution and then use a quantum
circuit to search its "neighborhood" for higher-quality solutions. We propose
the Classically-Boosted Quantum Optimization Algorithm (CBQOA) that is based on
this idea and can solve a wide range of combinatorial optimization problems,
including all unconstrained problems and many important constrained problems
such as Max Bisection, Maximum Independent Set, Minimum Vertex Cover, Portfolio
Optimization, Traveling Salesperson and so on. A crucial component of this
algorithm is an efficiently-implementable continuous-time quantum walk (CTQW)
on a properly-constructed graph that connects the feasible solutions. CBQOA
utilizes this CTQW and the output of an efficient classical procedure to create
a suitable superposition of the feasible solutions which is then processed in
certain way. This algorithm has the merits that it solves constrained problems
without modifying their cost functions, confines the evolution of the quantum
state to the feasible subspace, and does not rely on efficient indexing of the
feasible solutions. We demonstrate the applications of CBQOA to Max 3SAT and
Max Bisection, and provide empirical evidence that it outperforms previous
approaches on these problems.
