Почему бы не реализовать квантовые схемы на классических компьютерах?

Умножение матриц полиномиально по количеству матричных элементов. В квантовых вычислениях количество матричных элементов — это, по сути, количество элементов в векторе квантового состояния, которое экспоненциально зависит от размера входных данных (количества кубитов).

Ложная точка зрения состоит в том, что композиция однокубитных и двухкубитных вентилей будет представлена ​​какой-то композицией матриц 2×2 и 4×4. В самом деле, если однокубитный вентиль (для двухкубитного аналогично) действует на$i$-й кубит из$n$, матрица должна быть приведена к

Хотя тензорное произведение с тождествами выглядит тривиально, давайте просто вспомним, что оно означает для приложения на векторе состояния, использующего самый простой алгоритм:

for each index u, 0 ≤ u < 2^n:
  define u_i = bit value of i-th bit of u
  define v = u XOR 2^i
  if u_i = 0:
    new (psi[u], psi[v]) = a*psi[u] + b*psi[v]
  else:
    new (psi[u], psi[v]) = d*psi[u] + c*psi[v]

Да, в основе этого псевдоалгоритма как раз двумерное умножение. Но это сделано$2^n$раз.

Даже до того , как кто-то сможет выполнить фактическое классическое моделирование, у вас может закончиться доступная память даже для сохранения состояния в любой конкретный момент. Брать$n = 100$кубиты, это$2^{100}$сложные амплитуды двойной точности (каждая по 128 бит). Я получаю оценку, превышающую емкость хранения данных всех компьютеров на Земле примерно на 14 порядков, так что мы не увидим этого в ближайшее время. Между тем, квантовый компьютер со 100 битами почти начал бы представлять интерес для приложений, теоретически нередко можно увидеть гораздо больше, чем предполагалось.

Другими словами, гильбертово пространство (H) для вашей квантовой схемы растет экспоненциально ($\text{dim H} = 2^n$), где n — количество кубитов. Существует класс квантовых схем, которые могут быть реализованы за полиномиальное время, но они требуют, чтобы вентили в квантовой схеме были ограничены группой Паули и/или нормализатором группы Паули (теорема Готтсмана-Книла). Это также ограничивает модели ошибок, используемые в квантовой схеме. Основная причина в том, что существует изоморфизм, который можно определить между группой Паули и векторным пространством над конечным полем с элементами. Умножение элементов группы Паули становится симплектическим произведением элементов векторного пространства.

Потому что матрицы больше, чем вы думаете.

Рассмотрим простую схему на 8 кубитах; возможно преобразование Фурье. Он использует около 40 вентилей, и каждый вентиль умножает вектор состояния 8-кубитной системы на некоторую матрицу. Смоделировать эту систему классически. вы можете ожидать, что нам придется инвестировать что-то вроде$40\cdot 8=320$условные единицы вычислительной работы (AUCW).

Но вектор состояния системы имеет амплитуду для каждого возможного классического состояния системы. Восемь бит могут быть назначены$2^8 = 256$возможные значения, поэтому наш вектор состояния должен иметь 256 элементов, а не восемь или шестнадцать. Соответственно матрица, преобразующая эту систему, должна иметь размер$256 \times 256$, хотя просто$256$на самом деле это гораздо лучшая грубая оценка «размера работы», поскольку матрица одного вентиля будет разреженной. Наше предположение$40 \cdot 8 = 320$AUCW был далеко! Гораздо лучше предположить,$40 \cdot 2^8 = 40 \cdot 256 = 10240$. Так$10$килоAUCW.

Эта проблема усугубляется по мере увеличения числа кубитов. С 50 кубитами вектор состояния имеет$2^{50}$элементы, матрицы$2^{50} \times 2^{50}$, преобразование Фурье использует ~1250 вентилей, и нам нужно потратить миллион миллионов миллионов AUCW, чтобы выполнить классическое моделирование. В то время как квантовый компьютер делает всего 1250 AUQW.