量子コンピュータでなぜ巡回セールスマン問題がうまく解けないか

 量子コンピュータで Ising モデルや QUBO に定式化して問題を解く、というときに例題として巡回セールスマン問題を定式化するのは良くあるパターンだと思うが、実際に「量子コンピュータで巡回セールスマン問題を上手く解けた」という話はあまり聞いたことが無い。

ちょっと調べてみたら、ちょっと面白い話があって、 

「物理現象で巡回セールスマン問題として定式化できるものがほとんどない」 

 というのがあった。確かに「N個の頂点を順番に巡る原子」とか、あまりイメージしづらい。

 

一方で、通常のコンピュータ（古典コンピュータ）に使われる電気とかも、「N個の頂点を順番に巡る電気」とかあまり聞いたことが無いので、上の話をそのまま鵜吞みにするのも良くないとは思う。ただ、量子コンピュータのほうが純粋な量子状態を維持する必要があるから、古典コンピュータほど人間が介入できないのかも、とは思ったりもする。