量子コンピュータ、とくに量子アニーリングマシンの適用分野として真っ先に挙げられるのが、巡回セールスマン問題やナップサック問題のような組み合わせ最適化問題である。こうした最適化問題は、問題のサイズが大きくなると解の候補数が爆発的に増加するため、従来の計算機では計算が困難である
