В своей знаменитой лекции 1982 года нобелевский лауреат Ричард Фейнман высказал идею квантовых вычислений.
Он рассуждал, что объем классической информации, необходимой для описания квантовой системы, масштабируется экспоненциально с ее размерами и, таким образом, не может быть эффективно смоделирован классическим компьютером.
Действительно, довольно скромная система из 100 квантовых битов уже потребовала бы больше информации для описания, чем все существующие хранилища данных на Земле.
Учитывая это, вероятно, будут вычислительные задачи, которые достигают квантового превосходства - невозможно выполнить практически без помощи квантового информационного процессора.
За последние 37 лет эти первоначальные идеи укрепились, так как открытие ряда квантовых алгоритмов - от эффективного факторинга больших чисел до моделирования химических реакций - привело к гонке за квантовым превосходством.
Тем не менее, даже теоретически, окончательное решение - было ли достигнуто квантовое превосходство - нетривиально.
Оценка того, какие проблемы могут быть эффективно решены с помощью классических компьютеров, сама по себе оказывается чрезвычайно сложной.
Взять, к примеру, факторинг. Это действительно классическая неразрешимая проблема, или это просто то, что еще не найдены эффективные классические средства для факторинга?
Чтобы лучше понять, как квантовые компьютеры обрабатывают информацию, надо лучше находить классические методы для их моделирования. Это, в свою очередь, вдохновляет к новым эффективным классическим алгоритмам в неожиданных ситуациях.
Профессор Ман-Хонг Юнг, доцент Южного научно-технического университета, и его коллеги представили прекрасную иллюстрацию такого открытия. В их работе рассматривается специализированный тип линейного оптического квантового процессора.
Вход и выход кодируются в массиве оптических мод путем регулировки их начального числа фотонов. Вычисление достигается путем вмешательства в эти моды через сеть светоделителей, так что фотоны в одном режиме переносятся в другой.
Такие процессоры привлекли научное внимание благодаря своей способности выполнять задачу, известную как выборка бозонов. Когда каждая мода инициализируется одним фотоном, выходная статистика позволяет эффективно оценивать постоянные матрицы - вычислительную проблему с очень убедительным доказательством классической сложности. Это, в сочетании с их относительной простотой проектирования, сделало этот специализированный тип квантового процессора идеальным святым Граалем для демонстрации квантового превосходства.
Учитывая это, можно ожидать, что классические компьютеры мало что могут сказать о том, что будут производить такие процессоры. В конце концов, число путей, которые фотон может пройти, чтобы достичь одной моды из другой, экспоненциально масштабируется с размером сети светоделителя. Поэтому можно предположить, что для отслеживания этих путей потребуются экспоненциальные ресурсы для определения вероятности перехода фотона из режима А в режим В.
Однако Юнг и его коллеги показали, что классический алгоритм может эффективно оценивать вероятности перехода - до тех пор, пока допускает аддитивную ошибку.
Этот результат представляет собой значительное обобщение предыдущих результатов Скотта Ааронсона, который рассматривает случай, когда существует не более одного фотона в каждой моде. Напротив, решение Юнга работает независимо от количества фотонов, закодированных в каждом режиме.
Результат не только приносит пользу симуляции бозонных помех, но также имеет серьезные последствия в вычислительной технике.
Предположим, что такие специализированные квантовые процессоры используются для принятия бинарных решений.
То есть, в зависимости от входных данных, мы вводим определенные распределения фотонов, а затем решаем предпринять конкретное действие в зависимости от того, есть ли вероятность увидеть x-фотоны в конкретном выходе выше некоторого порога.
В таких условиях классического алгоритма, который оценивает эту вероятность с точностью до ограниченной аддитивной ошибки, достаточно для принятия решений, идентичных самому квантовому процессору.
Таким образом, алгоритм Юнга позволяет классическому компьютеру эффективно имитировать решения своего специализированного линейного оптического аналога.
Это, несомненно, будет иметь важные последствия в нынешней гонке за квантовое превосходство. В настоящее время много усилий затрачивается на демонстрацию квантового превосходства с помощью бозонной выборки, и полученные здесь результаты указывают на то, что нужно будет ввести более сложные квантовые архитектуры, чтобы продемонстрировать такое превосходство при принятии правильных решений.
Если вам было интересно – ставьте лайк и подписывайтесь на мой канал!
