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

Ключевые слова и синонимы

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

Постановка задачи

Объединение концепций, взятых из областей квантовых вычислений, сжатия данных и термодинамики, недавно привело к появлению новых алгоритмов, которые решают проблемы ядерного магнитного резонанса и, возможно, других областей – алгоритмов, «охлаждающих» физические системы.

Ведущей технологией-кандидатом для создания квантовых компьютеров является ядерно-магнитный резонанс (ЯМР). Преимущество этой технологии заключается в том, что она хорошо зарекомендовала себя в других областях, таких как химия и медицина. Поэтому она не требует нового и экзотического оборудования, в отличие от ионных ловушек, оптических решеток и т. д. Однако при использовании стандартных методов ЯМР (не только для квантовых вычислений) приходится мириться с тем, что состояние может быть инициализировано только очень шумным способом: спины частиц направлены в основном в случайные стороны, с небольшим смещением в сторону желаемого состояния.

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

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

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

Основные положения

Сжатие данных без потерь на месте

Имея на входе битовую строку длины n, распределение вероятностей которой известно и достаточно далеко от равномерного, можно использовать сжатие данных для генерации более короткой строки, скажем, из m бит, в которой энтропия каждого бита будет гораздо ближе к единице. В качестве простого примера рассмотрим строку из четырех бит со следующим распределением: [math]\displaystyle{ p_{0001} = p_{0010} = p_{0100} = p_{1000} = 1/4 }[/math], где [math]\displaystyle{ p_i }[/math] – вероятность строки i. Вероятность любого другого значения строки равна нулю, так что в сумме вероятности равны единице. Затем битовая строка может быть сжата с помощью алгоритма сжатия без потерь в 2-битовую строку, содержащую двоичное описание местоположения «1» в четырех вышеупомянутых строках. Поскольку вероятности всех этих строк равны нулю, можно также представить себе аналогичный процесс, который генерирует выходную строку той же длины n, что и входная, но при этом такую, что с помощью алгоритма сжатия на месте без потерь энтропия упаковывается в последние два бита. Например, логические вентили, оперирующие битами, могут выполнять перестановку [math]\displaystyle{ 0001 \to 0000, 0010 \to 0001, 0100 \to 0010 }[/math] и [math]\displaystyle{ 1000 \to 0011 }[/math], тогда как другие входные строки преобразуются в выходные строки, в которых два старших значащих бита не равны нулю; например, [math]\displaystyle{ 1100 \to 1010 }[/math]. Легко заметить, что энтропия теперь полностью сосредоточена в двух наименьших значащих битах, что полезно при сжатии данных, в то время как два наибольших значащих бита имеют нулевую энтропию.

Чтобы получить некоторое представление о конструкции логических вентилей, выполняющих манипуляции с энтропией, можно ознакомиться с близким к этому процессу сценарием, который впервые был рассмотрен фон Нейманом. Он продемонстрировал метод извлечения честных подбрасываний монеты, если эта монета подделана, предложив взять пару подбрасываний подделанной монеты с результатами [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] и использовать значение [math]\displaystyle{ a }[/math], обусловленное [math]\displaystyle{ a \ne b }[/math]. Простой расчет показывает, что [math]\displaystyle{ a = 0 }[/math] и [math]\displaystyle{ a = 1 }[/math] теперь получаются с равными вероятностями, и поэтому энтропия монеты [math]\displaystyle{ a }[/math] увеличивается в этом случае до 1. Противоположный случай, распределение вероятности [math]\displaystyle{ a }[/math] при [math]\displaystyle{ a = b }[/math], приводит к сильно детерминированному подбрасыванию монеты, а именно к подбрасыванию (обусловленному) с большей погрешностью или меньшей энтропией. Вентили, которые меняют значение [math]\displaystyle{ b }[/math] на противоположное, если (и только если) [math]\displaystyle{ a = 1 }[/math], называются вентилями с контролируемым отрицанием. Если после применения такого вентиля получается [math]\displaystyle{ b = 1 }[/math], это означает, что до операции с вентилем имело место соотношение [math]\displaystyle{ a \ne b }[/math], и теперь энтропия [math]\displaystyle{ a }[/math] равна 1. Если же после применения вентиля получается [math]\displaystyle{ b = 0 }[/math], это означает, что до операции с вентилем имело место [math]\displaystyle{ a = b }[/math], и теперь энтропия [math]\displaystyle{ a }[/math] меньше своего первоначального значения.

Спиновая температура, поляризационное смещение и эффективное охлаждение

В физике двухуровневые системы, а именно системы, допускающие только двоичные значения, полезны во многих отношениях. Часто бывает важно инициализировать такие системы чистым состоянием «0» или распределением вероятности, которое как можно ближе к чистому состоянию «0». В таких физических двухуровневых системах процесс сжатия данных, который приближает некоторые из них к чистому состоянию, можно рассматривать как «охлаждение». Для квантовых двухуровневых систем существует простая связь между температурой, энтропией и вероятностью заселения. Разница вероятностей заселения между этими двумя уровнями известна как поляризационное смещение, [math]\displaystyle{ \epsilon }[/math]. Рассмотрим одиночную частицу с половинным спином – например, ядро водорода – в постоянном магнитном поле. При равновесии с тепловым резервуаром вероятность того, что этот спин окажется направлен вверх или вниз (т. е. параллельно или антипараллельно направлению поля), задается формулой [math]\displaystyle{ p \uparrow = \frac{1 + \epsilon}{2} }[/math] и [math]\displaystyle{ p \downarrow = \frac{1 - \epsilon}{2} }[/math]. Энтропия H спина равна [math]\displaystyle{ H(single-bit) = H( \frac{1}{2} + \frac{\epsilon}{2}) }[/math], где [math]\displaystyle{ H(P) \equiv -P \; log_2 \; P - (1 - P) \; log_2 \; (1 - P) }[/math] измеряется в битах. Два чистых состояния ядра с половинным спином обычно записываются как [math]\displaystyle{ | \uparrow \rangle \equiv '0' }[/math] и [math]\displaystyle{ | \downarrow \rangle \equiv '1' }[/math] //уточнение обозначения [math]\displaystyle{ | \rangle }[/math] можно найти в других статьях, посвященных квантовым вычислениям – например, в статье Квантовое плотное кодирование//. Поляризационное смещение спина при тепловом равновесии задается формулой [math]\displaystyle{ \epsilon = р \uparrow - \; p \downarrow }[/math]. Для такой физической системы смещение получается с помощью соображений квантовой статистической механики, [math]\displaystyle{ \epsilon = tanh \left ( \frac{\hbar \gamma B}{2 K_B T} \right ) }[/math], где [math]\displaystyle{ \hbar }[/math] – постоянная Планка, B – напряженность магнитного поля, [math]\displaystyle{ \gamma }[/math] – зависящая от частицы гиромагнитная постоянная //эта постоянная отвечает за разницу в смещении равновесной поляризации – например, ядро водорода в 4 раза более поляризовано, чем ядро изотопа углерода [math]\displaystyle{ ^{13} C }[/math], но примерно в [math]\displaystyle{ 10^3 }[/math] раз менее поляризовано, чем спин электрона//, [math]\displaystyle{ K_B }[/math] – коэффициент Больцмана, а T – температура теплового резервуара. Для высоких температур или малых значений смещения [math]\displaystyle{ \epsilon \approx \frac{\hbar \gamma B}{2 K_B T} }[/math], таким образом, смещение обратно пропорционально температуре. Типичные значения [math]\displaystyle{ \epsilon }[/math] для ядер с полуцелыми спинами при комнатной температуре (и магнитном поле ~ 10 Тесла) составляют [math]\displaystyle{ 10^{-5} - 10^{-6} }[/math], и поэтому большая часть последующих рассуждений исходит из предположения, что [math]\displaystyle{ \epsilon \ll 1 }[/math]. Таким образом, спиновая температура при равновесии равна [math]\displaystyle{ T = \frac{Const}{\epsilon} }[/math], а ее энтропия по Шеннону составляет [math]\displaystyle{ H= 1 - (\epsilon^2/ln \; 4) }[/math].

Спиновая температура вне состояния теплового равновесия определяется по тем же формулам. Поэтому при выводе системы из теплового равновесия увеличение поляризационного смещения эквивалентно охлаждению спинов без охлаждения всей системы и уменьшению их энтропии. Процесс увеличения смещения (уменьшения энтропии) без уменьшения температуры теплового резервуара называется «эффективным охлаждением». Через определенный период времени, называемый временем термализации или временем релаксации, смещение постепенно возвращается к своему значению теплового равновесия; однако во время этого процесса, обычно составляющего порядка нескольких секунд, эффективно охлажденный спин может быть использован для различных целей, описанных в разделе «Применение».

Рассмотрим молекулу, содержащую n соседних ядер с половинными спинами, расположенных в линию; они образуют биты строки. Эти спины изначально находятся в тепловом равновесии из-за их взаимодействия с окружающей средой. При комнатной температуре биты, находящиеся в тепловом равновесии, не коррелируют со своими соседями по строке; точнее говоря, корреляция очень мала, и ею можно пренебречь. Более того, в жидком состоянии можно пренебречь и взаимодействием между строками (между молекулами). Распределение вероятности одиночного спина в тепловом равновесии удобно записать в нотации «матрицы плотности»

(1) [math]\displaystyle{ \rho_{\epsilon} = \begin{pmatrix} p \uparrow & 0 \\ 0 & p \downarrow \end{pmatrix} = \begin{pmatrix} (1 + \epsilon) / 2 & 0 \\ 0 & (1 - \epsilon) / 2 \end{pmatrix} }[/math]

поскольку эти двухуровневые системы имеют квантовую природу (а именно, это квантовые биты – кубиты) и в общем случае могут иметь состояния, отличные от классического распределения вероятностей над «0» и «1». Далее будет рассмотрен классический случай, когда матрица [math]\displaystyle{ \rho }[/math] содержит только диагональные элементы, которые описывают обычное распределение вероятностей. При тепловом равновесии состояние n = 2 некоррелированных кубитов, имеющих одинаковое поляризационное смещение, описывается матрицей плотности [math]\displaystyle{ \rho_{init}^{ \{n = 2 \}} = \rho_{\epsilon} \otimes \rho_{\epsilon} }[/math], где [math]\displaystyle{ \otimes }[/math] обозначает тензорное произведение. Например, вероятность состояния «00» равна [math]\displaystyle{ (1 + \epsilon)/2 \times (1 + \epsilon)/2 = (1 + \epsilon)^2/4 }[/math] (и т. д.). Аналогичным образом начальное состояние n-кубитной системы такого типа при тепловом равновесии имеет вид

(2) [math]\displaystyle{ \rho_{init}^{ \{ n \} } = \rho_{\epsilon} \otimes \rho_{\epsilon} \otimes \dots \otimes \rho_{\epsilon} }[/math]

Это состояние представляет собой тепловое распределение вероятностей, такое, что вероятность классического состояния «000...0» равна [math]\displaystyle{ P_{000...0} = (1 + \epsilon_0)^n / 2^n }[/math] и т. д. В реальности начальное смещение не одинаково на каждом кубите //кроме того, индивидуальное обращение к каждому спину в процессе работы алгоритма требует несколько иного смещения для каждого из них//, но пока различия между этими смещениями малы (например, все кубиты имеют одинаковое ядро), при обсуждении идеализированного сценария этими различиями можно пренебречь.

Основные результаты

Тепловые двигатели молекулярного масштаба

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

Традиционные методы квантовых вычислений для ЯМР основаны на немасштабируемых схемах инициализации состояний [5, 9] (например, подход «псевдочистого состояния»), в которых отношение сигнал/шум падает экспоненциально с увеличением числа спинов n. Следовательно, эти методы считаются непригодными для будущих квантовых ЯМР-компьютеров. Шульман и Вазирани [13] первыми применили инструменты теории информации для решения задачи масштабирования; они представили схему сжатия, в которой число охлажденных спинов хорошо масштабируется (а именно, как константа, кратная n). Авторы также продемонстрировали схему, приближающуюся к энтропийному пределу Шеннона для очень больших n. Они представили подробный анализ трех алгоритмов охлаждения, каждый из которых полезен для различных режимов значений [math]\displaystyle{ \epsilon }[/math].

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

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

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

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

Отношение [math]\displaystyle{ R_{relax-times} }[/math] между временем релаксации вычислительных спинов и временем релаксации сбрасывающих спинов должно удовлетворять соотношению [math]\displaystyle{ R_{relax-times} \gg 1 }[/math]. Это условие жизненно важно, если необходимо выполнить много шагов охлаждения системы, чтобы получить значительное охлаждение.

С чисто теоретико-информационной точки зрения правомерно предположить, что единственным ограничением на идеальные шаги обратимого поляризационного сжатия является энтропийный предел Шеннона; тогда эквивалентом энтропийного предела Шеннона при использовании алгоритмического охлаждения с идеальной открытой системой является то, что все вычислительные спины могут быть охлаждены до нулевой температуры, то есть до [math]\displaystyle{ \epsilon = 1 }[/math].

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

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

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

Концепция алгоритмического охлаждения привела к созданию практически применимых алгоритмов [8] для охлаждения небольших молекул. Чтобы увидеть влияние практического алгоритмического охлаждения, лучше всего использовать другой вариант энтропийного предела. Рассмотрим систему, содержащую n частиц с полуцелыми спинами с суммарной энтропией, превышающей [math]\displaystyle{ n - 1 }[/math], так что нет возможности охладить даже один спин до нулевой температуры. В этом случае энтропийный предел является результатом сжатия энтропии в [math]\displaystyle{ n - 1 }[/math] полностью случайных спинов, так что оставшаяся на последнем спине энтропия минимальна. Энтропия оставшегося одиночного спина удовлетворяет соотношению [math]\displaystyle{ H(single) \ge 1 - n \epsilon^2 / ln \; 4 }[/math], поэтому его поляризация может быть улучшена, самое большее, до

(3) [math]\displaystyle{ \epsilon_{final} \le \sqrt{n} }[/math]

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

Важно отметить, что в типичных сценариях начальное поляризационное смещение сбрасывающего спина выше, чем у вычислительного. В этом случае коэффициент усиления смещения [math]\displaystyle{ (3/2)^{(n - 1)/2} }[/math] относится к большему смещению сбрасывающего спина.

Исчерпывающее алгоритмическое охлаждение

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

Мор и Вайнштейн обобщили этот анализ и обнаружили, что n - 1 вычислительных спинов и один сбрасывающий спин могут быть охлаждены (приблизительно) до смещений в соответствии с рядом Фибоначчи: {... 34, 21, 13, 8, 5, 3, 2, 1, 1}. Вычислительный спин, наиболее удаленный от сбрасывающего спина, может быть охлажден до соответствующего числа Фибоначчи [math]\displaystyle{ F_n }[/math]. Это приближение справедливо до тех пор, пока наибольший член, кратный [math]\displaystyle{ \epsilon }[/math], все еще намного меньше 1. Затем Шульман предложил «алгоритм сопряжения партнеров» (PPA) и доказал оптимальность PPA среди всех классических и квантовых алгоритмов. Эти два алгоритма, Фибоначчи-охлаждение и PPA, стали основной для двух совместных работ [11, 12], где также были получены верхние и нижние границы для алгоритмического охлаждения. Алгоритм сопряжения партнеров. определяется следующим образом. Повторяйте эти два шага, пока охлаждение не будет достаточно близким к пределу: (а) RESET – применяется к сбрасывающему спину в системе, содержащей n - 1 вычислительных спинов и один (представляющий наименьший значащий бит) сбрасывающий. (b) SORT – перестановка, сортирующая [math]\displaystyle{ 2^n }[/math] диагональных элементов матрицы плотности по убыванию, так что спин с наибольшим значащим битом становится самым холодным. В работе [12] доказаны две важные теоремы:

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

Теорема 2 (верхняя граница). В разделе 4.2 работы [12] доказывается следующая теорема: Ни один алгоритмический метод охлаждения не может увеличить вероятность любого базисного состояния выше [math]\displaystyle{ min \{ 2^{-n} e^{2^n \epsilon}, 1 \} }[/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]\displaystyle{ 2^{n - 2} }[/math] раз. Более того, анализ высшего порядка вышеупомянутого верхнего предела (раздел 4.2 в [12]), показывает, что ни один спин не может быть охлажден больше, чем в [math]\displaystyle{ 2^{n - 1} }[/math] раз; см. следствие 1 в [6].

Применение

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

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

Открытые вопросы

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

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

Экспериментальные результаты

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

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

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

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

См. также

• Сжатие данных с использованием словаря
• Квантовый алгоритм факторизации
• Квантовый алгоритм для решения задачи о четности
• Квантовое плотное кодирование
• Квантовое распределение ключей

Литература

1. Baugh,J., Moussa, O., Ryan,C.A., Nayak,A., Laflamme, R.: Experimental implementation of heat-bath algorithmic cooling using solid-state nuclear magnetic resonance. Nature 438,470-473 (2005)

2. Boykin, P.O., Mor, T., Roychowdhury, V., Vatan, F., Vrijen, R.: Algorithmic cooling and scalable NMR quantum computers. Proc. Natl. Acad. Sci.99, 3388-3393 (2002)

3. Brassard, G., Elias, Y., Fernandez, J.M., Gilboa, H., Jones, J.A., Mor, T., Weinstein, Y., Xiao, L.: Experimental heat-bath cooling of spins. Submitted to Proc. Natl. Acad. Sci. USA. See also quant-ph/0511156 (2005)

4. Chang, D.E., Vandersypen, L.M.K., Steffen, M.: NMR implementation of a building block for scalable quantum computation. Chem. Phys. Lett. 338, 337-344 (2001)

5. Cory, D.G., Fahmy, A.F., Havel, T.F.: Ensemble quantum computing by NMR spectroscopy. Proc. Natl. Acad. Sci. 94, 1634-1639(1997)

6. Elias, Y., Fernandez, J.M., Mor, T., Weinstein, Y.: Optimal algorithmic cooling of spins. Isr. J. Chem. 46, 371-391 (2006), also in: Ekl, S. et al. (eds.) Lecture Notes in Computer Science, Volume 4618, pp. 2-26. Springer, Berlin (2007), Unconventional Computation. Proceedings of the Sixth International Conference UC2007 Kingston, August 2007

7. Fernandez, J.M.: De computatione quantica. Dissertation, University of Montreal (2004)

8. Fernandez, J.M., Lloyd, S., Mor, T., Roychowdhury V.: Practicable algorithmic cooling of spins. Int. J. Quant. Inf. 2, 461-477 (2004)

9. Gershenfeld, N.A., Chuang, I.L.: Bulk spin-resonance quantum computation. Science 275,350-356 (1997)

10. Mor, T., Roychowdhury,V., Lloyd, S., Fernandez,J.M., Weinstein, Y.: Algorithmic cooling. US Patent 6,873,154 (2005)

11. Schulman, L.J., Mor, T., Weinstein, Y.: Physical limits of heat-bath algorithmic cooling. Phys. Rev. Lett. 94, 120501, pp. 1-4 (2005)

12. Schulman, L.J., Mor, T., Weinstein, Y.: Physical limits of heat-bath algorithmic cooling. SIAM J. Comput. 36, 1729-1747 (2007)

13. Schulman, L.J., Vazirani, U.: Molecular scale heat engines and scalable quantum computation. Proc. 31st ACM STOC, Symp. Theory of Computing,pp. 322-329 Atlanta, 01-04 May 1999

14. Sarensen, O.W.: Polarization transfer experiments in high-resolution NMR spectroscopy. Prog. Nuc. Mag. Res. Spect. 21, 503-569(1989)