Как отслеживать запутанность при эмуляции квантовых вычислений?

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

Я знаю, что кубитов можно хранить с помощью сложного массива из элементов. Кроме того, кубитные ворота - это 2D-массив. Итак, мои сомнения следующие (в основном связанные с запутанностью):$n$$2^n$$n$$2^n \times 2^n$

1. Когда мне нужно найти тензорное произведение вентилей (например, , для кубитной системы)? Всегда ли необходимо вычислять тензорное произведение порядка , даже если кубиты не запутаны?$I \otimes H \otimes I$$3$$2^n \times 2^n$

2. Имея только элемента массива (в котором я храню коэффициенты), могу ли я как-то вычислить, какие кубиты запутаны? Или мне нужно создать другую структуру данных для хранения информации о запутанности моих кубитов (о том, какие кубиты запутаны)?$2^n$$n$

3. Мой второй вопрос актуален? Нужно ли вообще отслеживать информацию о запутанности? Я имею в виду, я не знаю, достаточно ли умножения вентилей на коэффициенты (даже если система запутана). Может быть, это актуально только во время измерения.

Конечно, всегда достаточно рассчитать полную унитарную матрицу, а затем применить ее к вектору входных состояний. Если это то, что вы решили сделать, это все , что вам нужно сделать, поскольку вся информация о запутанности содержится в этом векторе. Быстрый и простой способ узнать, запутался ли конкретный кубит, - это взять частичный след вашего (чистого) вектора состояния над всеми другими кубитами. Если полученная матрица имеет ранг 1, этот кубит находится в отделимом состоянии, в противном случае он запутан.$2^n\times 2^n$$2^n$

Я предполагаю, что смысл вашего вопроса на самом деле «Как избежать этих огромных вычислительных затрат?». В общем, это невозможно - если вы используете всю мощь квантового компьютера, вам всегда понадобится вектор состояния входа. Тем не менее, существуют различные приемы, которые снижают вычислительные затраты, такие как отсрочка необходимости в таком большом векторе состояния путем отслеживания запутывания.$2^n$

Улучшения эффективности

Самая большая экономия, которую вы можете сделать по сравнению с наивной реализацией выше, состоит в том, чтобы избежать унитарных матриц. Например, если вы используете только 1- или 2-кубитные гейты, простое использование разреженности матриц означает, что вам нужно только хранения вместо .$2^n\times 2^n$$O(2^n)$$O(2^{2n})$

Тогда есть другая тактика, которую вы можете использовать. Например, представьте, что вы хотите применить двухкубитный унитарный вентиль к кубитам и . Вы можете взять наборы из 4 элементов из вашего вектора состояния ( для фиксированного , взяв все различные ) и просто применив унитарного на этот 4-элементный вектор. Повторение этого для каждого вернет введенный в исходный вектор состояния.$U$$i$$j$$|x\rangle_{1,2,\ldots n\setminus i,j}|y\rangle_{i,j}$$x\in\{0,1\}^{n-2}$$y\in\{0,1\}^2$$4\times 4$$U$$x$$U$

Я предполагаю, что есть другие стратегии, которые можно придумать. Тот, который предложил себя из первоначального вопроса, был отслеживанием запутанности. Это дает улучшения памяти и скорости в начале вычисления, но в конечном итоге оказывается эквивалентным, потому что (предположительно) все в квантовом компьютере запутается.

Отслеживание запутанности

Предположим, что ваше вычисление состоит только из унитарной эволюции и измерения на множестве из кубитов, т.е. нет декогеренции, вероятностных карт и т. Д. Предположим, что вы начинаете с полностью разделяемого состояния, такого как . На этом этапе каждый кубит отделим, и достаточно сохранить разных регистров, каждый из которых передает состояние сепарабельного кубита. Если ваши первые ворота - это просто операция одного кубита на кубите , то вы просто обновляете состояние, хранящееся на кубите как , и вам не нужно ничего трогать остальное.$n$$|0\rangle^{\otimes n}$$n$$U$$i$$i$$|\psi_i\rangle\mapsto U|\psi_i\rangle$

Если вы хотите сделать , скажем, два-кубитные ворота между кубитами и , то вам нужно объединить состояния в обоих узлах. Таким образом, вы заменяете два регистра каждого измерения 2 на один регистр измерения 4, содержащий состояние . Проблема в том, что теперь вы не можете снова разделить это состояние, поэтому вы должны всегда сохранять эти два кубита в регистре. Конечно, если у вас когда-либо есть 1-кубитный вентиль для применения к кубиту , теперь вам нужно применить . Затем в следующий раз, когда вам понадобятся 2-кубитные вентили, скажем, между и$V$$i$$j$$V|\psi_i\rangle|\psi_j\rangle$$U$$i$$|\psi_{i,j}\rangle\mapsto U\otimes\mathbb{I}|\psi_{i,j}\rangle$$j$$k$, вам придется объединить пробелы для и . Эти пространства будут расти, но если ворота локализованы только на одном пространстве, вам нужно только применить их там (используя операторы чтобы заполнить их на остальных кубитах), и вам не нужно сделать что-нибудь с другими местами.$(i,j)$$k$$\mathbb{I}$

Если вы делаете такие вещи, у вас не будет (по крайней мере, для первых нескольких шагов вашего алгоритма) одного элемента регистра. Вам нужно будет иметь несколько разных регистров, и отслеживать, какие кубиты описаны, какими регистрами в отдельном массиве. Каждый раз, когда вы объединяете пространства некоторых кубитов, вы обновляете этот дополнительный массив.$2^n$

Вот некоторый очень грубый псевдокод, который может помочь передать мое значение:

#initialise variables
entangled_blocks={{1},{2},{3},...,{n}}
quantum_states={{1,0},{1,0},...,{1,0}}

#apply action of each gate
for each gate
   for each gate_target
       target_block=entangled_blocks entry containing gate_target
   next gate_target
   if all target_blocks equal then
      apply gate on target_block (pad with identity on other qubits)
   else
      new_entangled_block=union(target_blocks)
      new_state_vec=tensor_product(quantum_states for each target block)
      apply gate on new_state_vec (pad with identity on other qubits)
      replace all target_blocks in entangled_blocks with new_entangled_block
      replace all quantum_states(all target blocks) with new_state_vec
   end if
next gate

Другие опции

(Отнюдь не исчерпывающий)

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