Проблема королевы – это математическая задача, которой уже занимался великий математик Карл Фридрих Гаусс, но для которой он, к удивлению, не нашел правильного решения. Задача состоит в том, чтобы расположить восемь ферзей на классической шахматной доске с полями 8 x 8, чтобы никакие две ферзя не угрожали друг другу.
Математически относительно легко определить, что существует 92 различных способа расстановки ферзей. На шахматной доске размером 25 х 25 клеток уже есть более 2 миллиардов возможностей.
На расчет только этого числа ушло в общей сложности 53 года процессорного времени.
Задача усложняется, если на поле уже находятся ферзевые и некоторые диагонали могут быть не заняты.
Недавно было показано, что с этими дополнительными ограничениями проблема с 21 ферзей больше не может быть решена классическими математическими алгоритмами за разумное время. «Я случайно натолкнулся на эту тему и подумал, что квантовая физика действительно может раскрыть здесь свои преимущества», – говорит Вольфганг Лехнер с факультета теоретической физики Университета Инсбрука и Института квантовой оптики и квантовой информации Австрийской академии наук. Наук.
Вместе с Гельмутом Ричем и аспирантами Валентином Торгглером и Филиппом Ауманном Лехнер разработал квантовую шахматную доску, на которой головоломка королевы может быть решена экспериментально с помощью квантовой физики.
От атомов до шахматных королев
«Оптическую решетку из лазерных лучей, в которую помещены отдельные атомы, можно использовать как шахматную доску», – объясняет Хельмут Ритч, который также является членом факультета теоретической физики в Инсбруке. «Регулируя взаимодействие между атомами, мы можем сделать из атомов шахматных королев, которые ведут себя в соответствии с шахматными правилами, i.е. избегайте друг друга во всех направлениях игрового поля."Это отталкивание частиц создается с помощью лазеров, которые применяются вдоль направлений движения. Через оптический резонатор – два зеркала над и под оптической решеткой – это взаимодействие еще больше усиливается и, таким образом, становится эффективным на гораздо больших расстояниях.
«В эту игру можно было бы также играть с соответственно отталкивающими бильярдными шарами», – говорит Ритч. "Но поскольку существует так много возможностей, это займет очень, очень много времени.
Поэтому очень важно, чтобы атомы очень сильно охлаждались и чтобы их квантовые свойства вступали в силу. Потому что тогда они ведут себя как волны и могут одновременно проверять множество возможностей. Тогда быстро становится очевидным, существует ли правильное решение согласно шахматным правилам для данных условий.
Квантовое превосходство на горизонте
Ответ на вопрос, существует ли решение при данных ограничениях, очень легко прочитать по свету, излучаемому резонатором.
Но конкретное расположение атомных ферзей можно было определить только с помощью атомной микроскопии, метода, недавно успешно примененного в связанных экспериментах.
Моделирование на классических компьютерах убедительно свидетельствует о том, что эксперимент, разработанный теоретиками Инсбрука, приведет к результату намного быстрее, чем мог бы любой математический алгоритм на классическом компьютере. «Это позволило бы впервые четко доказать превосходство квантовых компьютеров для решения определенных задач оптимизации», – резюмирует Вольфганг Лехнер. «Контроль нескольких десятков атомов уже является стандартной практикой в лаборатории, поэтому реализация этой идеи может вскоре стать реальностью."