Лазеры, магнетики и коммивояжеры.

А вернемся еще раз к теме квантового компьютера) В предыдущих постах я уже и достоинства, и недостатки описывал, но ни разу не привел пример задачи, которую мог бы решить только квантовый компьютер.

К таким задачам относится известная задача коммивояжера (Travelling salesman problem), которая в соответствии с названием действительно была поставлена странствующим торговцем в пособии для начинающих аж в 1832 году. Суть проблемы в следующем: требуется найти самый выгодный маршрут такой, чтобы посетить указанные города хотя бы по одному разу и вернуться в исходный город. В условиях задачи обычно указывают дополнительные критерии выгодности маршрута – кратчайший, самый дешёвый, совокупный критерий и тому подобное – и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз. Никакой классический компьютер неспособен решить такую задачу перебором различных вариантов уже при относительно небольшом числе городов (66 и более) за время, меньшее нескольких миллиардов лет!

Вот в такие моменты на помощь математикам приходят физики, предлагая нетрадиционные методы) Обычно в качестве такого решения выступает создание модельной физической системы, которая за счет собственных свойств позволят отказаться от прямого перебора. В данном случае физики предлагают воспользоваться упрощенной спиновой «XY-моделью», описывающей магнетики, чьи спины ориентированы в основном в одной плоскости. В «XY-модели» спиновой системы частицы образуют вихревые узоры вокруг нескольких фокальных точек. Представьте себе несколько стоков в большой ванне с однонаправленными потоками воды, стекающими по каждому стоку. Решить сложную задачу по определению направления движения стекающей в стоки воду можно, лишь создав физическую систему, которая эмулирует такую «XY-модель». Кстати говоря, такая физическая система может быть использована, например, и в прогнозировании углов между связями в белке, что важно в синтезе лекарств. Это может значительно сократить время, необходимое для проведения сложных вероятностных вычислений.

Недавно физик Ютака Такэда из Токийского университета науки и его коллеги улучшили экспериментальную установку, которая эмулирует «XY-модель». В конструкции они используют лазерную систему, которая генерирует импульсы оптическом резонаторе длиной в один километр. Импульсы генерируются с использованием невырожденной сети оптических параметрических генераторов, которая в конечном итоге симулирует 5000 спинов, то есть поток фотонов проходит внутри резонатора сквозь 5000 различных «стоков». Такая установка позволила существенно увеличить время стабильного моделирования с нескольких миллисекунд до нескольких минут.

В результате, получили, конечно, не квантовый компьютер, но вполне себе что-то около модель на 5000 узловых точек, с помощью которой можно и задачу коммивояжера решать.

Y Takeda et al. Boltzmann sampling for an XY model using a non-degenerate optical parametric oscillator network, Quantum Science and Technology (2017). DOI: 10.1088/2058-9565/aa923b

Комментарии: