Могут ли классические решатели линейной алгебры реализовать квантовые алгоритмы с аналогичным ускорением?
Квантовый алгоритм начинается с регистра кубитов в начальном состоянии, унитарный оператор (алгоритм) манипулирует состоянием этих кубитов, а затем считывается состояние кубитов (или, по крайней мере, некоторая информация о состоянии одного запуск алгоритма).
Мне кажется, что квантовый компьютер отвечает на вопрос об унитарных воздействиях на квантовое состояние. Это «всего лишь» вопрос линейной алгебры. Поэтому мне кажется, что квантовые компьютеры можно рассматривать как вычислители линейной алгебры.
Зачем тогда нам нужна квантовая механика? Можем ли мы не найти классическую систему, реализующую операции линейной алгебры, и использовать ее для реализации алгоритмов, разработанных для квантовых компьютеров? Конечно, классических цифровых компьютеров будет недостаточно, эти машины основаны на двоичной обработке информации, а не на манипуляции векторами в многомерном пространстве.
Вопрос: Существуют ли какие-либо кандидаты в решатели классической линейной алгебры (классические аналоговые компьютеры), которые могли бы реализовать алгоритмы «квантового компьютера», обладая при этом аналогичным ускорением по сравнению с цифровыми классическими компьютерами?
Вопрос 2: Возможно, я слишком упрощаюсь, сводя квантовый компьютер к простому решателю линейной алгебры. Так ли это? Какую сложность я замалчиваю?
Ответы
Сложность, которую вы замалчиваете, заключается в том, что в общем случае вам нужно хранить $2^n$ комплексные амплитуды, чтобы даже представить $n$кубитная система классически. Следовательно, для квантового компьютера на 1000 кубитов вам нужно хранить$2^{1000}$комплексные амплитуды. Даже если для этого вы будете использовать один атом на амплитуду, у вас все равно кончатся атомы в наблюдаемой Вселенной.
Насколько мне известно, приведенный выше аргумент является общим. Тем не менее, все еще могут быть способы представить определенные квантовые алгоритмы в классически управляемой манере, используя некоторые умные идеи, чтобы сэкономить на репрезентативных потребностях алгоритма, тем самым опустившись ниже$2^n$требование. Но это, вероятно, связано с конкретной проблемой и вряд ли сработает в общем случае.
Согласно формулировке вопроса относительно цифровых и аналоговых вычислений, на этом сайте есть и другие темы, в которых запрашиваются аналогичные предложения. См., Например, здесь и здесь . Помимо прочего, классические аналоговые системы не могут быть запутанными; таким образом, преобразование квантового компьютера в аналоговый компьютер не приведет к такому же наблюдаемому ускорению.
Тем не менее, в дополнение к ответу @Attila Kun существуют определенные проблемы в линейной алгебре / машинном обучении, в которых были быстрые квантовые алгоритмы, но которые были преобразованы в классические алгоритмы с аналогичным ускорением.
Например, проблема рекомендации, используемая Netflix / Amazon / etc. имеет быстрый алгоритм на квантовом компьютере. Этот алгоритм показал экспоненциальное улучшение по сравнению с (тогда) самым известным классическим алгоритмом.
Однако, пытаясь доказать, что квантовый алгоритм действительно превосходен, Э. Танг показал, что действительно существует «классическая система, которая реализует операции линейной алгебры и использует это для реализации алгоритмов, которые были разработаны для квантовых компьютеров».
Работа Тана положила начало программе деквантования, то есть преобразования быстрых квантовых алгоритмов в линейной алгебре / машинного обучения в быстрые классические алгоритмы. Quanta Magazine статья описывает проблему и подход Тана.
Какие проблемы можно решить с помощью этого деквантования, является активной областью исследований, как обсуждается в этой ветке . Это может зависеть от ранга рассматриваемых матриц.