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

Первые результаты применения этой методики были опубликованы в статье в научном журнале Science Advances.

«Задачи комбинаторной оптимизации хорошо подходят для демонстрации превосходства квантовых компьютеров над их классическими аналогами, однако до настоящего времени это не удавалось сделать. Мы создали <…> алгоритм, способный решать задачи комбинаторной оптимизации, и реализовали его на практике при помощи набора из 72 кубитов. Наша разработка оказалась быстрее ее классических аналогов, что указывает на наличие квантового ускорения», – пишут исследователи.

Этот алгоритм был разработан группой ученых под руководством вице-президента квантового стартапа Rigetti Computing Мэттью Ригора.