Квантовый компьютер победит классический в игре «Магический квадрат»

Ученые теоретически проанализировали квантовый алгоритм для игры в «Магический квадрат» и показали, что даже небольшие шумные квантовые компьютеры способны превзойти классические аналоги. Работа представлена в журнале Nature Physics.

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

В прошлом году компании Google удалось продемонстрировать явное превосходство в решении задачи эмуляции случайно квантовой цепи, но такую задачу нельзя назвать очень полезной. К тому же, для этого использовался очень мощный квантовый компьютер. С тех пор ученые активно ищут задачи, для эффективного решения которых достаточно современных шумных и не очень больших квантовых устройств. 

Ученые из IBM и научных центров Австралии, Германии, Канады и Сингапура под руководством профессора Марко Томамичела (Marco Tomamichel) исследовали квантовое превосходство с помощью математической игры «Магический квадрат». 

В этой игре два участника заполняют квадрат числами +1 и −1. Один из игроков должен случайно выбрать строку и заполнить ее числами так, чтобы количество −1 было четным, другой игрок в это время заполоняет случайный столбец так, чтобы количество −1 было нечетным. Игроки не знают какой столбец (строку) выбрал другой игрок. Числа, которые оказываются на пересечении строки и столбца, перемножаются — цель игры заполнить квадрат так, чтобы хотя бы одна клетка дала +1. Очевидно, что либо оба игрока выиграют, либо проиграют.

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

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

При демонстрации превосходства очень важна верификация ответа. Например, в эксперименте Google 53-кубитный процессор решал задачу, результат которой проверить невозможно даже на суперкомпьютерах. В случае же «Магического квадрата» суммы, по которым можно определить наличие клетки с +1, считаются менее чем за секунду на обычном ноутбуке, таким образом подтвердить ответ вычислительно просто даже для миллиона кубитов.

Ученым еще предстоит проверить экспериментально разработанную теорию, однако результаты выглядят многообещающими. Недавно мы писали про то, как определяется мощность квантовых компьютеров на примере компьютера компании Honeywell. Больше про кубиты и квантовые компьютеры читайте в нашем материале «Квантовая азбука».

Михаил Перельштейн