Quantum Annealing via Path-Integral Monte Carlo With Data Augmentation

Abstract

This article considers quantum annealing in the Ising framework for solving combinatorial optimization problems. The path-integral Monte Carlo simulation approach is often used to approximate quantum annealing and implement the approximation by classical computers, which refers to simulated quantum annealing (SQA). In this article, we introduce a data augmentation scheme into SQA and develop a new algorithm for its implementation. The proposed algorithm reveals new insights on the sampling behaviors in SQA. Theoretical analyses are established to justify the algorithm, and numerical studies are conducted to check its performance and to confirm the theoretical findings. Supplementary materials for this article are available online.

Keywords:

• Combinatorial optimization
• Hamming distance
• Parallel Ising model
• Simulated quantum annealing
• Strong ergodicity

Supplementary Materials

Code and data: An R package which consists of datasets and programs for all methods used in the numerical studies, along with an example code file necessary to reproduce the results in this article. (zip file).

Acknowledgments

The authors thank Editor Tyler McCormick, an associate editor, and two anonymous referees for helpful comments and suggestions which led to significant improvements of the article.

Additional information

Funding

The research of Yazhen Wang was supported in part by NSF grants DMS-15-28375 and DMS-17-07605.