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

9

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

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

  1. Когда мне нужно найти тензорное произведение вентилей (например, , для кубитной системы)? Всегда ли необходимо вычислять тензорное произведение порядка , даже если кубиты не запутаны?IHI32n×2n

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

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

Midhun XDA
источник
1
Это зависит от ли оптимизации , чтобы следить за запутанности рисунка преждевременно или нет. Если у вас есть только 3 кубита, вы не получите много, вкладывая эти усилия, так что это будет «преждевременная оптимизация». Поэтому спросите себя, насколько масштабируемым вам это действительно нужно. n
AHusain
1
@MidhunXDA «Я знаю, что происходит физически, но я не могу преобразовать это в математическую форму». Насколько я знаю, существует множество физических процессов, которые приводят к квантовым вычислениям. Я думаю, что было бы неплохо, если бы вы точно описали один из тех физических процессов, которые вы хотите подражать (или все они, если вы думаете, что это все еще будет в рамках вопроса). Я думаю, что указание этого делает вопрос более ясным и на него легче ответить.
Дискретная ящерица
1
Пожалуйста, разбейте это на несколько вопросов - я вижу по крайней мере три разных вопроса.
Хизер
3
@heather Я согласен с постером, что это действительно все вопросы, которые являются разными аспектами одного и того же. Я действительно не вижу, как улучшить вопрос, но я думаю, что понимаю его достаточно хорошо, чтобы дать ответ.
DaftWullie
2
@heather Я настоятельно рекомендую модераторам не ставить вопросы самостоятельно, за исключением крайних случаев (читай: явно не по теме или спам). На этот вопрос, хотя и немного широкий, можно разумно ответить в одном посте. FWIW здесь в основном два вопроса: 1) Когда вычислять тензорные произведения вентилей? 2) Как учесть эффект запутанности при этом?
Санчайан Датта

Ответы:

5

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

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

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

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

Тогда есть другая тактика, которую вы можете использовать. Например, представьте, что вы хотите применить двухкубитный унитарный вентиль к кубитам и . Вы можете взять наборы из 4 элементов из вашего вектора состояния ( для фиксированного , взяв все различные ) и просто применив унитарного на этот 4-элементный вектор. Повторение этого для каждого вернет введенный в исходный вектор состояния.Uij|x1,2,ni,j|yi,jx{0,1}n2y{0,1}24×4UxU

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

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

Предположим, что ваше вычисление состоит только из унитарной эволюции и измерения на множестве из кубитов, т.е. нет декогеренции, вероятностных карт и т. Д. Предположим, что вы начинаете с полностью разделяемого состояния, такого как . На этом этапе каждый кубит отделим, и достаточно сохранить разных регистров, каждый из которых передает состояние сепарабельного кубита. Если ваши первые ворота - это просто операция одного кубита на кубите , то вы просто обновляете состояние, хранящееся на кубите как , и вам не нужно ничего трогать остальное.n|0nnUii|ψiU|ψi

Если вы хотите сделать , скажем, два-кубитные ворота между кубитами и , то вам нужно объединить состояния в обоих узлах. Таким образом, вы заменяете два регистра каждого измерения 2 на один регистр измерения 4, содержащий состояние . Проблема в том, что теперь вы не можете снова разделить это состояние, поэтому вы должны всегда сохранять эти два кубита в регистре. Конечно, если у вас когда-либо есть 1-кубитный вентиль для применения к кубиту , теперь вам нужно применить . Затем в следующий раз, когда вам понадобятся 2-кубитные вентили, скажем, между иVijV|ψi|ψjUi|ψi,jUI|ψi,jjk, вам придется объединить пробелы для и . Эти пространства будут расти, но если ворота локализованы только на одном пространстве, вам нужно только применить их там (используя операторы чтобы заполнить их на остальных кубитах), и вам не нужно сделать что-нибудь с другими местами.(i,j)kI

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

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

#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, которые являются хорошим способом инкапсулировать информацию о не слишком запутанных состояниях и могут предоставить вам альтернативный маршрут, в зависимости от того, чего именно вы пытаетесь достичь.

DaftWullie
источник
То, чего я пытаюсь достичь - это, конечно, эффективность. Кроме того, я хочу точно знать, как все эти процессы работают (потому что я новичок). Таким образом, на практике лучший выбор - просто хранить все коэффициенты кубитов вместе в одном массиве (записи), верно? Спасибо, что ответили.
Midhun XDA
@DaftWullie Ваше первое предложение создает впечатление, что в общем случае потребуется хранить все унитарных, а не только вектор . 2n×2n2n
Норберт Шух
@MidhunXDA С точки зрения эффективности все по существу эквивалентно, потому что квантовый компьютер в конечном итоге приведет к запутыванию всего. Чтобы узнать, что происходит, вам, вероятно, лучше начать с одного массива, соответствующего вектору состояний. Но, используя отслеживание запутывания, вы можете получить некоторые улучшения скорости и памяти, которые должны позволить немного более длительное моделирование.
DaftWullie
@NorbertSchuch Я сказал, что этого достаточно, что правда. Я добавил некоторые подробности о том, как этого избежать. Вы, наверное, знаете о другой, лучшей тактике.
DaftWullie