Quantum Optimization

Abstract

We present a quantum algorithm for combinatorial optimization using the cost structure of the search states. Its behavior is illustrated for overconstrained satisfiability and asymmetric traveling salesman problems. Simulations with randomly generated problem instances show each step of the algorithm shifts amplitude preferentially towards lower cost states, thereby concentrating amplitudes into low-cost states, on average. These results are compared with conventional heuristics for these problems.

11 pages, 4 figures

Cited by in corpus (7)

• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Analytical Framework for Quantum Alternating Operator Ansätze
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Solving Random Satisfiability Problems with Quantum Computers
• Towards Efficiently Solving Quantum Traveling Salesman Problem