Наконец появилась задача, которую смогут решить только квантовые компьютеры

а мне показалось всё логичным: «путь, проходящий через определённые города, более короткий, чем заданное расстояние» означает любой путь из подмножества
а «является ли это расстояние наикратчайшим путём через эти города» ответ: Да / Нет без допущений