Пазл на квантовой шахматной доске

Физики предлагают новую модель, которая могла бы продемонстрировать превосходство квантовых компьютеров над классическими суперкомпьютерами при решении задач оптимизации. Они демонстрируют, что всего нескольких квантовых частиц было бы достаточно для решения математически сложной проблемы N-королев в шахматах даже для больших шахматных досок.

Задача королевы — это математическая задача, которой уже занимался великий математик Карл Фридрих Гаусс, но для которой он неожиданно не нашел правильного решения. Задача здесь состоит в том, чтобы расположить восемь королев на классической шахматной доске с 8 × 8 квадратами, чтобы никакие две королевы не угрожали друг другу. Математически относительно легко определить, что существует 92 различных способа расстановки королев. На шахматной доске с 25 x 25 квадратами уже есть более 2 миллиардов возможностей. Только для расчета этого числа потребовалось 53 года процессорного времени.

Задача становится еще более сложной, если некоторые королевы уже находятся на поле и некоторые диагонали могут не быть заняты. Недавно было показано, что с этими дополнительными ограничениями проблема с 21 королевой больше не может быть решена классическими математическими алгоритмами в разумные сроки. «Я случайно наткнулся на эту тему и подумал, что квантовая физика действительно может сыграть здесь свои преимущества», — говорит Вольфганг Лехнер из Отдела теоретической физики Университета Инсбрука и Института квантовой оптики и квантовой информации Австрийской академии наук. Вместе с Хельмутом Ритчем и аспирантами Валентином Торгглером и Филиппом Ауманном Лехнер разработал квантовую шахматную доску, на которой головоломка с ферзями может быть решена экспериментально с помощью квантовой физики.

От атомов к шахматным королевам

«Оптическая решетка лазерных лучей, в которую помещены отдельные атомы, может быть использована в качестве шахматной доски», — объясняет Хельмут Ритч, который также является членом кафедры теоретической физики в Инсбруке. «Регулируя взаимодействие между атомами, мы можем сделать шахматные королевы из атомов, которые ведут себя согласно шахматным правилам, то есть избегают друг друга во всех направлениях игрового поля». Это отталкивание частиц генерируется с помощью лазеров, которые применяются вдоль направлений движения. Через оптический резонатор — два зеркала выше и ниже оптической решетки — это взаимодействие еще более усиливается и, таким образом, становится эффективным на гораздо больших расстояниях.

«Можно также играть в эту игру с соответственно отталкивающими бильярдными шарами», — говорит Рич. «Но поскольку существует так много возможностей, это займет очень очень много времени. Поэтому очень важно, чтобы атомы очень сильно охлаждались и чтобы их квантовые свойства вступили в силу. Потому что тогда они ведут себя как волны и могут проверить множество возможностей». в то же время. Тогда быстро становится очевидно, существует ли правильное решение по шахматным правилам для данных условий.

Квантовое превосходство на горизонте

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

Моделирование на классических компьютерах убедительно свидетельствует о том, что эксперимент, разработанный теоретиками Инсбрука, приведет к результату намного быстрее, чем любой математический алгоритм на классическом компьютере. «Это позволило бы впервые наглядно доказать превосходство квантовых компьютеров для расчета некоторых задач оптимизации», — резюмирует Вольфганг Лехнер. «Контроль нескольких десятков атомов уже является стандартной практикой в лаборатории, поэтому реализация этой идеи может вскоре стать реальностью».