Ученые теоретически проанализировали квантовый алгоритм для игры в «Магический квадрат» и показали, что даже небольшие шумные квантовые компьютеры способны превзойти классические аналоги. Работа представлена в журнале Nature Physics.
Теоретически квантовые компьютеры способны решить многие важные задачи эффективно, в то время как классическим устройствам понадобится экспоненциально большое время для их решения. Однако большинство современных квантовых компьютеров недостаточно мощны, чтобы показать превосходство в решении каких-то полезных задач.
В прошлом году компании Google удалось продемонстрировать явное превосходство в решении задачи эмуляции случайно квантовой цепи, но такую задачу нельзя назвать очень полезной. К тому же, для этого использовался очень мощный квантовый компьютер. С тех пор ученые активно ищут задачи, для эффективного решения которых достаточно современных шумных и не очень больших квантовых устройств.
Ученые из IBM и научных центров Австралии, Германии, Канады и Сингапура под руководством профессора Марко Томамичела (Marco Tomamichel) исследовали квантовое превосходство с помощью математической игры «Магический квадрат».
В этой игре два участника заполняют квадрат числами +1 и −1. Один из игроков должен случайно выбрать строку и заполнить ее числами так, чтобы количество −1 было четным, другой игрок в это время заполоняет случайный столбец так, чтобы количество −1 было нечетным. Игроки не знают какой столбец (строку) выбрал другой игрок. Числа, которые оказываются на пересечении строки и столбца, перемножаются — цель игры заполнить квадрат так, чтобы хотя бы одна клетка дала +1. Очевидно, что либо оба игрока выиграют, либо проиграют.
Игра «Магический квадрат», в которую играют два участника Алиса и Боб.
В то время как классические методы не могут гарантированно обеспечить выигрыш, даже если игроки заранее договорятся о стратегии (ведь выбор столбца/строки происходит случайно), квантовый алгоритм, использующий запутанные состояния, может помочь участникам игры всегда выигрывать. Квантовое решение позволяет игрокам разделить запутанное состояние, которое несет в себе информацию о действиях другого участника.
Ученые показали, что с точки зрения теории сложности квантовое решение даже на шумных устройствах эффективней классического угадывания, при этом исследователи не опирались на недоказанные предположения о несуществовании эффективных классических алгоритмов. Более того, для решения этой задачи можно использовать неглубокие квантовые цепи, на которые не так сильно влияют внутренние ошибки квантового компьютера. Авторы оценили сложность таких цепей и пришли к выводу, что решение можно реализовать на современных квантовых компьютерах и показать квантовые превосходство.
Топология квантовой цепи для создания запутанных состояний, необходимых для безусловной победы в игре.
При демонстрации превосходства очень важна верификация ответа. Например, в эксперименте Google 53-кубитный процессор решал задачу, результат которой проверить невозможно даже на суперкомпьютерах. В случае же «Магического квадрата» суммы, по которым можно определить наличие клетки с +1, считаются менее чем за секунду на обычном ноутбуке, таким образом подтвердить ответ вычислительно просто даже для миллиона кубитов.
