Построение квантового компьютера в симуляции

Если кто-то хочет начать строить квантовый компьютер с нуля внутри симуляции (например, как люди строят классический компьютер с нуля в курсе Nand2Tetris ), возможно ли это?

Если да, каковы будут возможные подходы?

Кроме того, каковы будут ограничения такой моделируемой машины, учитывая определенное количество классической вычислительной мощности? Например, если мы выберем ваш средний рабочий стол / ноутбук, какой будет предел? Если мы возьмем суперкомпьютер (например, Titan), то какой будет предел?

Первая часть вашего вопроса кажется дубликатом существующего поста QC SE: есть ли эмуляторы для квантовых компьютеров? ,

Я не совсем уверен, что вы подразумеваете под созданием квантового компьютера с нуля внутри симуляции . Однако, да, вы можете делать программные симуляции квантового компьютера, используя обычный ноутбук / рабочий стол. Точный «предел» будет зависеть от технических характеристик компьютера.

Поскольку квантовый компьютер не нарушает тезис Черча-Тьюринга , теоретически определенно можно смоделировать квантовый компьютер, используя идеальную машину Тьюринга. Очевидный подход к моделированию такой системы требует экспоненциального времени на классическом компьютере, а сложность пространства является экспоненциальной функцией числа симулируемых квантовых битов. Скажем, вы моделируете битный квантовый компьютер, вам нужно будет хранить около 2 n бит информации на вашем классическом компьютере в любой момент. Более того, реализация квантовых вентилей снова потребует огромного количества ресурсов с точки зрения временной и пространственной сложности. Реализация квантового вентиля, работающего на $n$$2^{n}$$n$ кубитах, должна хранить около (поскольку вы можете представить все операции с квантовыми затворами в виде матрицы размером 2 n × 2 n ) битов информации.$4^{n}$$2^{n}\times2^{n}$

Вы можете сортировать оценку «предела» в зависимости от характеристик классического компьютера. Например, если (доступный) объем памяти вашего классического компьютера составляет около ТБ, я ожидаю, что вы можете смоделировать журнал 4 ( 8 × 10 12 ) ≈ 21- битный квантовый компьютер (скажем, на всякий случай 20 ). Однако имейте в виду, что классическим компьютерам потребуется гораздо больше времени для доступа ко всем отдельным битам информации по сравнению с реальным квантовым компьютером (в зависимости от аппаратного обеспечения квантового компьютера). Так что будет медленнее$1$$\log_4(8\times 10^{12})\approx 21$$20$ чем к настоящему квантовому компьютеру! Некоторые другие ограничения заключаются в том, что после каждого действия кубитного гейта вы должны отслеживать, какие выходные кубиты запутаны, что является NP-трудной проблемой. Также,$n$ измерение не может быть точно смоделировано на классическом компьютере, потому что классически нет действительно генератора случайных чисел.

Ну, я сейчас работаю над симулятором квантового компьютера. Конечно, основная идея квантовых вычислений - это ворота, представленные матрицами, примененными к кубитам, представленным векторами. Используя простой пакет Python, это не так сложно программировать в самом простом смысле.

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

Затем вы попадаете на сильно неизведанную территорию. Как вы строите набор инструкций для квантового компьютера? Кто знает. Вы должны выяснить. Вам также придется выяснить вашу версию сборки и даже вашу версию языков программирования более высокого уровня.

Итак, ограничения классического компьютера в этом? Ну, это действительно сложный вопрос (и его стоит задать отдельно, imho), но вот краткое резюме:

• мы не знаем, действительно ли квантовые компьютеры лучше классических компьютеров; алгоритмы для классических компьютеров просто не могут быть достаточно хорошими (квантовое превосходство)
• скажем, как это кажется прилично , вероятно, что квантовые компьютеры могут лучше , чем классические компьютеры. это улучшение будет сильно зависеть от проблемы - например, квантовые компьютеры могут увидеть гораздо более быстрое улучшение при поиске простых факторизаций, чем при проверке электронной почты. (см. также это P.SE q / a.)
• чтобы обеспечить какое-то числовое значение, если мы рассмотрим текущий самый быстрый алгоритм для классического простого поиска факторизации, т. е. общее число сито, у нас есть O-время $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$что явно довольно грубо. Алгоритм Шора, с другой стороны, работает в $O((\log N)^2(\log \log N)(\log \log \log N))$ что, очевидно, намного быстрее.
• Я могу запустить кучу кубитов на моем компьютере, пока я держу их в $|0\rangle$ или $|1\rangle$состояния - т. е. фактически классические. Так что, в некотором смысле, ваш вопрос опять-таки нечеткий.

Я чувствую, что этот ответ в основном основан на неправильном понимании того, что значит «симулировать» что-то.

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

Поэтому вопрос о том, можно ли «симулировать квантовый компьютер в классическом компьютере», несколько некорректен. Если вы имеете в виду, что хотите воспроизвести каждый возможный аспект «квантового компьютера», то этого никогда не произойдет, точно так же, как вы никогда не сможете смоделировать каждый аспект любой классической системы (если вы не используете один и тот же идентичный система конечно).

С другой стороны, вы, безусловно, можете моделировать многие аспекты сложного устройства, такого как «квантовый компьютер». Например, можно моделировать эволюцию состояния в квантовой цепи. Действительно, это может быть чрезвычайно легко сделать! Например, если у вас есть Python на вашем компьютере, просто запустите следующее

import numpy as np
identity_2d = np.diag([1, 1])
pauliX_gate = np.array([[0, 1], [1, 0]])
hadamard_gate = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

cnot_gate = np.kron(identity_2d, pauliX_gate)
H1_gate = np.kron(hadamard_gate, identity_2d)

awesome_entangling_gate = np.dot(cnot_gate, H1_gate)

initial_state = np.array([1, 0, 0, 0])
final_state = np.dot(awesome_entangling_gate, initial_state)
print(final_state)

Поздравляем, вы просто «смоделировали» эволюцию сепарабельного состояния с двумя кубитами в состояние Белла!

Однако, если вы попытаетесь сделать то же самое, скажем, с 40 кубитами и нетривиальными воротами, вы не сможете легко справиться с этим. Наивная причина в том, что даже просто сохранить состояние$n$-qubit (не разреженное) состояние, которое нужно указать ~$2^n$комплексные числа, и это начинает занимать много памяти очень быстро. Я говорю «наивный» здесь, потому что во многих случаях могут быть хитрости, которые позволяют вам избежать этой проблемы$^{(1)}$, Вот почему многие люди пытаются найти хитрые уловки для моделирования квантовых цепей (и других типов квантовых систем) на классических компьютерах, и почему это далеко не тривиально$^{(2)}$,

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

(1) Интересным примером этого является проблема моделирования устройства отбора проб бозона (это не квантовый алгоритм в смысле состояния, развивающегося через серию затворов, но, тем не менее, это пример нетривиального квантового устройства). BosonSampling - это проблема сэмплирования , в которой стоит задача выборки.из конкретного распределения вероятности, и это было показано (при вероятных предположениях), что невозможно сделать эффективно с классическим устройством. Хотя никогда не было показано, что он является фундаментальным аспектом этой твердости, безусловно, нетривиальная проблема, связанная с моделированием устройства для отбора проб бозона, заключалась в том, что ему приходилось вычислять экспоненциально большое число вероятностей, из которых можно производить выборку. Однако недавно было показано, что действительно не нужно вычислять весь набор вероятностей для выборки из них ( 1705.00686 и 1706.01260). В принципе, это недалеко от моделирования эволюции большого количества кубитов в квантовой цепи без необходимости хранить все состояние системы в любой заданной точке. Что касается более непосредственно квантовых цепей, примеры недавнего прорыва в возможностях моделирования - 1704.01127 и 1710.05867 (также суперсовременная, еще не опубликованная, - 1802.06952 ).

(2) На самом деле, было показано (или, скорее, были представлены убедительные доказательства этого факта), что невозможно эффективно моделировать большинство квантовых цепей, см. 1504.07999 .