4431
правка
Алгоритмическое охлаждение: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 106: | Строка 106: | ||
Мор и Вайнштейн обобщили этот анализ и обнаружили, что n - 1 вычислительных спинов и один сбрасывающий спин могут быть охлаждены (приблизительно) до смещений в соответствии с рядом Фибоначчи: {... 34, 21, 13, 8, 5, 3, 2, 1, 1}. Вычислительный спин, наиболее удаленный от сбрасывающего спина, может быть охлажден до соответствующего числа Фибоначчи <math>F_n</math>. Это приближение справедливо до тех пор, пока наибольший член, кратный <math>\epsilon</math>, все еще намного меньше 1. Затем Шульман предложил «алгоритм сопряжения партнеров» (PPA) и доказал оптимальность PPA среди всех ''классических и квантовых'' алгоритмов. Эти два алгоритма, Фибоначчи-охлаждение и PPA, стали основной для двух совместных работ [11, 12], где также были получены верхние и нижние границы для алгоритмического охлаждения. Алгоритм сопряжения партнеров. определяется следующим образом. Повторяйте эти два шага, пока охлаждение не будет достаточно близким к пределу: (а) RESET – применяется к сбрасывающему спину в системе, содержащей n - 1 вычислительных спинов и один (представляющий наименьший значащий бит) сбрасывающий. (b) SORT – перестановка, сортирующая <math>2^n</math> диагональных элементов матрицы плотности по убыванию, так что спин с наибольшим значащим битом становится самым холодным. В работе [12] доказаны две важные теоремы: | Мор и Вайнштейн обобщили этот анализ и обнаружили, что n - 1 вычислительных спинов и один сбрасывающий спин могут быть охлаждены (приблизительно) до смещений в соответствии с рядом Фибоначчи: {... 34, 21, 13, 8, 5, 3, 2, 1, 1}. Вычислительный спин, наиболее удаленный от сбрасывающего спина, может быть охлажден до соответствующего числа Фибоначчи <math>F_n</math>. Это приближение справедливо до тех пор, пока наибольший член, кратный <math>\epsilon</math>, все еще намного меньше 1. Затем Шульман предложил «алгоритм сопряжения партнеров» (PPA) и доказал оптимальность PPA среди всех ''классических и квантовых'' алгоритмов. Эти два алгоритма, Фибоначчи-охлаждение и PPA, стали основной для двух совместных работ [11, 12], где также были получены верхние и нижние границы для алгоритмического охлаждения. Алгоритм сопряжения партнеров. определяется следующим образом. Повторяйте эти два шага, пока охлаждение не будет достаточно близким к пределу: (а) RESET – применяется к сбрасывающему спину в системе, содержащей n - 1 вычислительных спинов и один (представляющий наименьший значащий бит) сбрасывающий. (b) SORT – перестановка, сортирующая <math>2^n</math> диагональных элементов матрицы плотности по убыванию, так что спин с наибольшим значащим битом становится самым холодным. В работе [12] доказаны две важные теоремы: | ||
Теорема 1 (нижняя граница). Когда <math>\epsilon^2 \gg 1</math> (а именно, для достаточно длинных молекул), теорема 3 из [12] гарантирует, что может быть извлечено <math>n - log(1/ \epsilon)</math> холодных кубитов. Этот случай актуален для масштабируемых квантовых вычислений на базе ЯМР. | '''Теорема 1 (нижняя граница)'''. Когда <math>\epsilon^2 \gg 1</math> (а именно, для достаточно длинных молекул), теорема 3 из [12] гарантирует, что может быть извлечено <math>n - log(1/ \epsilon)</math> холодных кубитов. Этот случай актуален для масштабируемых квантовых вычислений на базе ЯМР. | ||
Теорема 2 (верхняя граница). В разделе 4.2 работы [12] доказывается следующая теорема: Ни один алгоритмический метод охлаждения не может увеличить вероятность любого базисного состояния выше <math>min \{ 2^{-n} e^{2^n \epsilon}, 1 \}</math>, если начальная конфигурация представляет собой полностью смешанное состояние (то же самое верно, если начальное состояние представляет собой тепловое состояние). | '''Теорема 2 (верхняя граница)'''. В разделе 4.2 работы [12] доказывается следующая теорема: Ни один алгоритмический метод охлаждения не может увеличить вероятность любого базисного состояния выше <math>min \{ 2^{-n} e^{2^n \epsilon}, 1 \}</math>, если начальная конфигурация представляет собой полностью смешанное состояние (то же самое верно, если начальное состояние представляет собой тепловое состояние). | ||
Впоследствии Элиас, Фернандес, Мор и Вайнштейн [6] более тщательно проанализировали случай n < 15 (при комнатной температуре), когда самый холодный спин (на всех стадиях) все еще имеет поляризационное смещение намного меньше 1. Этот случай наиболее актуален для применения в ЯМР-спектроскопии. Они обобщили принцип Фибоначчи-охлаждения на алгоритмы, дающие | Впоследствии Элиас, Фернандес, Мор и Вайнштейн [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]. | ||
== Применение == | == Применение == | ||
