Алгоритмическое охлаждение: различия между версиями

Шульман и Вазирани [13] определили важность сжатия данных без потерь на месте и битов с низкой энтропией, создаваемых в этом процессе: физические двухуровневые системы (например, ядра с половинными спинами) могут быть аналогичным образом охлаждены алгоритмами сжатия данных. Авторы проанализировали охлаждение такой системы с помощью различных инструментов сжатия данных. Сжатие без потерь n-битной двоичной строки, распределенной в соответствии с тепловым равновесным распределением согласно уравнению (2), легко анализируется с помощью теоретико-информационных инструментов: в идеальной схеме сжатия (не обязательно реализуемой) при достаточно большом n вся случайность – и, следовательно, вся энтропия – битовой строки переносится в n - m бит; оставшиеся m бит, таким образом, с чрезвычайно высокой вероятностью остаются в известном детерминированном состоянии, скажем, в состоянии строки «000...0». Энтропия H всей системы равна <math>H(system) = nH(single-bit) = nH(1/2 + \epsilon/2)</math>. Любая схема сжатия не может уменьшить эту энтропию, поэтому энтропийный предел Шеннона для кодирования источника дает <math>m \le n[1 - H(1/2 + \epsilon/2)]</math>. Простой расчет по высшему порядку показывает, что m ограничено (приблизительно) <math>\frac{\epsilon^2}{2 \; ln \; 2} n</math> для малых значений начального смещения <math>\epsilon</math>. Таким образом, при типичном <math>e \backsim 10^{-5}</math> для охлаждения одного спина до околонулевой температуры требуются молекулы, содержащие порядка <math>10^{10}</math> спинов.

Некоторые идеи Шульмана и Вазирани уже были исследованы несколькими годами ранее Соренсеном [14] – физхимиком, анализировавшим эффективное охлаждение спинов. Он рассмотрел энтропию нескольких спиновых систем и ограничения, накладываемые на охлаждение этих систем переносом поляризации и более общими манипуляциями с ней. Кроме того, он рассмотрел процессы охлаждения спинов, в которых использовались только унитарные операции, в которых унитарные матрицы применяются к матрицам плотности; такие операции реализуемы, по крайней мере, с концептуальной точки зрения. Соренсен вывел более строгое ограничение на унитарное охлаждение, которое сегодня носит его имя. Однако, в отличие от Шульмана и Вазирани, он не делал выводов о связи со сжатием данных и не отстаивал алгоритмы сжатия.

Следующее значительное событие произошло, когда Бойкин, Мор, Ройчоудхури, Ватан и Вриен изобрели новую технику спинового охлаждения, которую они назвали ''алгоритмическим охлаждением'' [2] или, более конкретно, алгоритмическим охлаждением в тепловом резервуаре, в ходе которого использование контролируемых взаимодействий с тепловым резервуаром значительно усиливает технику охлаждения. Алгоритмическое охлаждение (AC) расширяет эффективные методы охлаждения за счет манипуляций с энтропией в ''открытых системах''. Оно сочетает шаги этапы обратимого поляризационного сжатия ''//в случае, когда весь процесс представляет собой обратимое поляризационное сжатие, то есть речь идет о любом из процессов, реализующих идеи Шульмана и Вазирани, его можно называть обратимым алгоритмическим охлаждением или алгоритмическим охлаждением с закрытой системой//'' с быстрой релаксацией (а именно, термализацией) ''более горячих спинов'', что позволяет откачивать энтропию за пределы системы и охлаждать ее ''намного сильнее, чем позволяет энтропийный предел Шеннона''. Чтобы откачать энтропию из системы, алгоритмическое охлаждение использует обычные спины (далее называемые «вычислительными» спинами) вместе со спинами, подвергающимися быстрой релаксации. Последние представляют собой вспомогательные спины, которые очень быстро возвращаются в состояние теплового равновесия. Эти спины были названы «сбрасывающими спинами», или, что эквивалентно, сбрасывающими битами. Контролируемое взаимодействие с тепловым резервуаром происходит за счет переноса поляризации или стандартных алгоритмических приемов (сжатия данных), которые переносят энтропию на сбрасывающие спины, а те впоследствии сбрасывают избыточную энтропию в окружающую среду.

Доказательство: повторяйте следующие действия, пока энтропия всех вычислительных спинов не станет равной нулю: (i) перегоните энтропию из вычислительных спинов на сбрасывающие спины; (ii) дайте сбрасывающим спинам остыть до комнатной температуры. Очевидно, что каждое применение шага (i), кроме последнего, переносит одно и то же количество энтропии на сбрасывающие спины, а затем на шаге (ii) эта энтропия удаляется из системы. Разумеется, реалистичный сценарий должен учитывать и другие параметры, такие как соотношения конечного времени релаксации, реалистичная среда и физические операции над спинами. Как только это будет сделано, охлаждение до нулевой температуры станет недостижимым. Если конечное время релаксации и реалистичная среда зависят от системы, то ограничение на использование физических операций является концептуальным.

Поэтому Бойкин, Мор, Ройчоудхури, Ватан и Вриен разработали алгоритм, который следует некоторым физическим правилам, выполняется с помощью унитарных операций и шагов сброса – и при этом успешно обходит энтропийный предел Шеннона. Упомянутый алгоритм охлаждения достигает значительного охлаждения сверх энтропийного предела за счет использования очень длинных молекул, несущих сотни или даже тысячи спинов, поскольку его анализ опирается на закон больших чисел.

'''Практичное алгоритмическое охлаждение'''

Практичное алгоритмическое охлаждение (PAC), предложенное Фернандесом, Ллойдом, Мором и Ройчоудхури в [8], показало потенциал для применения в ЯМР-спектроскопии в ближайшем будущем. В частности, авторы представили алгоритм под названием PAC2, который использует любое (нечетное) число спинов n, такое, что один из них является сбрасывающим спином, а (n - 1) – вычислительными. Алгоритм PAC2 охлаждает спины так, что самый холодный из них может (приблизительно) достичь усиления смещения в <math>(3/2)^{(n - 1)/2}</math> раз. Приближение справедливо до тех пор, пока конечное смещение <math>(3/2)^{(n - 1)/2} \epsilon</math> много меньше 1. В противном случае необходимо проводить более точную обработку. Это доказывает экспоненциальное преимущество алгоритмического охлаждения перед наилучшим возможным обратимым вариантом алгоритмического охлаждения, поскольку такие обратимые методы охлаждения, например, из [13, 14], ограничены улучшением смещения не более чем в <math>\sqrt{n}</math> раз. PAC можно применять при малых n (например, в диапазоне 10–20), и поэтому он потенциально подходит для перспективного применения [6, 8, 10] в химической и медико-биологической ЯМР-спектроскопии.

Далее был проанализирован алгоритм охлаждения, в котором этапы охлаждения (сброс и обратимое поляризационное сжатие) повторяются произвольное число раз. Фактически это идеализация, когда неограниченное число шагов сброса и логических шагов может быть применено без ошибок или рассогласования, а вычислительные кубиты не теряют своих поляризационных смещений. Фернандес [7] рассмотрел два вычислительных спина и один сбрасываемый спин (наименьший значащий бит, а именно кубит с правой стороны в нотации матрицы плотности тензорного произведения) и проанализировал оптимальное охлаждение этой системы. Исчерпывающим образом повторяя сброс и сжатие, он обнаружил, что граница конечных смещений трех спинов приблизительно равна {2, 1, 1} в единицах <math>\epsilon</math> – поляризационного смещения сбрасывающего спина.

 

'''Теорема 1 (нижняя граница)'''. Когда <math>\epsilon^2 \gg 1</math> (а именно, для достаточно длинных молекул), теорема 3 из [12] гарантирует, что может быть извлечено <math>n - log(1/ \epsilon)</math> холодных кубитов. Этот случай актуален для масштабируемых квантовых вычислений на базе ЯМР.  

 

Впоследствии Элиас, Фернандес, Мор и Вайнштейн [6] более тщательно проанализировали случай n < 15 (при комнатной температуре), когда самый холодный спин (на всех стадиях) все еще имеет поляризационное смещение намного меньше 1. Этот случай наиболее актуален для применения в ЯМР-спектроскопии. Они обобщили принцип Фибоначчи-охлаждения на алгоритмы, дающие ряды Фибоначчи более высокого порядка, такие как трибоначчи (также известный как 3-кратный ряд Фибоначчи), {... 81, 44, 24, 13, 7, 4, 2, 1, 1} и т. д. Конечный предел этих многочленных рядов Фибоначчи имеет место, когда каждый член ряда равен сумме всех предыдущих. Полученный ряд в точности является экспоненциальным {... 128, 64, 32,16, 8, 4, 2, 1, 1}, так что самый холодный спин охлаждается в <math>2^{n - 2}</math> раз. Более того, анализ высшего порядка вышеупомянутого верхнего предела (раздел 4.2 в [12]), показывает, что ни один спин не может быть охлажден больше, чем в <math>2^{n - 1}</math> раз; см. следствие 1 в [6].

Два основных направления применения для отдаленного и близкого будущего уже упомянуты в разделе «Постановка задачи». Здесь важно добавить, что хотя конкретные алгоритмы, проанализированные до сих пор, обычно являются классическими, практическая реализация алгоритмического охлаждения на ЯМР-спектрометре должна быть осуществлена путем анализа универсальных квантовых вычислений с использованием определенных вентилей, допустимых в таких системах. Таким образом, алгоритмическое охлаждение может стать первым ближайшим механизмом применения квантовых вычислительных устройств.

Основная открытая проблема практического применения алгоритмического охлаждения лежит в технологической области: можно ли увеличить соотношение времен релаксации таким образом, чтобы можно было применять много ступеней охлаждения для соответствующих ЯМР-систем? Другие методы, например механизм спиновой диффузии [1], также могут быть полезны для различных сфер применения.

Различные идеи алгоритмического охлаждения уже привели к нескольким экспериментам с использованием 3-4-кубитных квантовых вычислительных устройств:  

 

1. Эксперимент [4], в котором был реализован один проход обратимого поляризационного сжатия.  

 

2. Эксперимент [3], в котором были обойдены границы сохранения энтропии (действующие в любой замкнутой системе).  

 

3. Полномасштабный эксперимент с алгоритмическим охлаждением [1], в котором три ядра углерода инициализируются смещением спина водорода, а затем выполняется один шаг сжатия этих трех ядер углерода.