Кажется, что под квантовыми вычислениями часто понимают метод вычисления квантовых цепей, где на регистр кубитов воздействует схема квантовых вентилей и измеряется на выходе (и, возможно, на некоторых промежуточных этапах). Квантовый отжиг, по крайней мере, кажется совершенно другим методом для вычислений с квантовыми ресурсами ¹ , так как он не включает квантовые вентили.

Какие существуют различные модели квантовых вычислений? Что отличает их?

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

---

<sub>1. Все, что по своей природе не является классическим, например, запутанность и согласованность.
2. Процесс, который преобразует входные данные (например, кубиты) в выходные (результаты вычислений).</sub>

Адиабатическая модель

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

Адиабатические вычисления обычно принимают следующую форму.

1. Начните с некоторого набора кубитов, все в каком-то простом состоянии, таком как $\lvert + \rangle$ . Назовите начальное глобальное состояние $\lvert \psi_0 \rangle$ .
2. Подчините эти кубиты гамильтониану взаимодействия для которого | ψ 0 ⟩ является уникальным основное состояние (состояние с наименьшей энергией). Например, учитывая | ψ 0 ⟩ = | + ⟩ ⊗ n , мы можем выбрать H 0 = - ∑ k σ ( x ) k .$H_0$$\lvert \psi_0 \rangle$$\lvert \psi_0 \rangle = \lvert + \rangle^{\otimes n}$$H_0 = - \sum_{k} \sigma^{(x)}_k$
3. Выберите конечный гамильтониан , который имеет уникальное основное состояние, которое кодирует ответ на интересующую вас проблему. Например, если вы хотите решить проблему удовлетворения ограничения, вы можете определить гамильтониан H 1 = ∑ c h c где сумма берется по ограничениям c классической задачи, и где каждый h c является оператором, который налагает штраф энергии (положительный вклад энергии) в любое стандартное базовое состояние, представляющее классическое назначение, которое не удовлетворяет ограничению c ,$H_1$$H_1 = \sum_{c} h_c$$c$$h_c$$c$
4. $T \geqslant 0$$H(t)$$H(0) = H_0$$H(T) = H_1$$H(t) = \tfrac{t}{T} H_1 + (1 - \tfrac{t}{T})H_0$
5. В моменты времени от до позвольте системе эволюционировать под непрерывно меняющимся гамильтонианом и измерьте кубиты на выходе, чтобы получить результат .$t = 0$$t = T$$H(t)$$y \in \{0,1\}^n$

Основой адиабатической модели является адиабатическая теорема , из которой существует несколько версий. Версия Амбайниса и Регева [  arXiv: quant-ph / 0411152  ] (более строгий пример) подразумевает, что если всегда существует «энергетическая щель», по крайней мере, между основным состоянием и его первое возбужденное состояние для всех , а оператор-нормы первой и второй производных достаточно малы (то естьH ( t ) 0 ⩽ t ⩽ T H H ( t $\lambda > 0$$H(t)$$0 \leqslant t \leqslant T$$H$$H(t)$не меняется слишком быстро или резко), тогда вы можете сделать так, чтобы получить желаемый результат настолько большим, насколько вам нравится, просто выполняя вычисления достаточно медленно. Кроме того, вы можете уменьшить вероятность ошибки на любой постоянный фактор, просто замедляя все вычисления полиномиально связанным фактором.

Несмотря на то, что представление очень отличается от модели унитарной схемы, было показано, что эта модель за полиномиальное время эквивалентна модели унитарной цепи [  arXiv: quant-ph / 0405098  ]. Преимущество адиабатического алгоритма состоит в том, что он обеспечивает другой подход к построению квантовых алгоритмов, который более поддается задачам оптимизации. Одним из недостатков является то, что неясно, как защитить его от шума или сказать, как его производительность ухудшается при несовершенном контроле. Другая проблема заключается в том, что даже без каких-либо недостатков в системе определить, как медленно запустить алгоритм, чтобы получить надежный ответ, - трудная проблема: она зависит от разрыва энергии, и вообще не так просто определить, какая энергия разрыв для статического гамильтонианаH ( т $H$не говоря уже о нестационарных .$H(t)$

Тем не менее, это модель, представляющая как теоретический, так и практический интерес, и отличающаяся тем, что она наиболее отличается от модели унитарной схемы, по существу, от любой существующей.

Измерение на основе квантовых вычислений (MBQC)

Это способ выполнения квантовых вычислений, используя промежуточные измерения как способ управления вычислением, а не просто извлечения ответов. Это частный случай «квантовых цепей с промежуточными измерениями», и поэтому он не более мощный. Однако, когда он был представлен, он опроверг интуицию многих людей о роли унитарных преобразований в квантовых вычислениях. В этой модели есть следующие ограничения:

1. Каждый подготавливает или получает очень большое запутанное состояние - состояние, которое можно описать (или подготовить) с помощью некоторого набора кубитов, изначально подготовленных в состоянии , а затем некоторой последовательности операций с контролируемым Z , выполняемый на парах кубитов в соответствии с отношениями ребер графа (обычно это прямоугольная сетка или гексагональная решетка).C Z = d i a g ( + 1 , + 1 , + 1 , - 1 $\lvert + \rangle$$\mathrm{CZ} = \mathrm{diag}(+1,+1,+1,-1)$
2. Выполните последовательность измерений на этих кубитах - некоторые, возможно, в стандартном базисе, но большинство не в стандартном базисе, а вместо этого измеряют наблюдаемые, такие как для разных углов . Каждое измерение дает результат или (часто обозначаемый «0» или «1» соответственно), и выбор угла может просто зависеть от результатов предыдущих измерений (способом, вычисленным классическим система контроля).θ + 1 - $M_{\mathrm{XY}}(\theta) = \cos(\theta) X - \sin(\theta) Y$$\theta$$+1$$-1$
3. Ответ на вычисление может быть вычислен из классических результатов измерений.$\pm 1$

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

Эту модель вычислений обычно считают полезной, прежде всего, как способ моделирования унитарных цепей. Поскольку его часто рассматривают как средство для имитации более подходящей и более простой модели вычислений, он больше не считается теоретически очень интересным для большинства людей. Тем не мение:

• Это важно среди прочего как мотивирующая концепция класса IQP , которая является одним из способов продемонстрировать, что квантовый компьютер сложно моделировать, и Blind Quantum Computing, которая является одним из способов попытаться решить проблемы в безопасных вычислениях с использованием квантовых ресурсов. ,

• Нет причин, по которым вычисления на основе измерений должны быть по существу ограничены моделированием унитарных квантовых цепей: мне кажется (и горстке других теоретиков в меньшинстве), что MQBC мог бы предоставить способ описания интересных вычислительных примитивов. Хотя MBQC является просто частным случаем цепей с промежуточными измерениями, и поэтому его можно моделировать с помощью унитарных цепей только с полиномиальными издержками, это не означает, что унитарные схемы обязательно будут очень плодотворным способом описания всего, что можно сделать в принципе. в вычислениях, основанных на измерениях (так же, как в классических вычислениях существуют императивные и функциональные языки программирования, которые немного неудобны друг с другом).

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

Модель унитарной цепи

Это лучшая известная модель квантовых вычислений. В этой модели есть следующие ограничения:

1. набор кубитов, инициализированных чистым состоянием, которое мы обозначим ;$\lvert 0 \rangle$
2. последовательность унитарных преобразований, которые выполняются над ними, которые могут зависеть от классической цепочки битов ;$x\in \{0,1\}^n$
3. одно или несколько измерений в стандартном базисе выполняются в самом конце вычисления, давая классическую выходную строку . (Мы не требуем k = n : например, для проблем ДА / НЕТ, часто берется k = 1 независимо от размера n .)$y \in \{0,1\}^k$$k = n$$k = 1$$n$

Мелкие детали могут меняться (например, набор унитарных можно выполнить, разрешает ли один препарат в других чистых состояниях , такие как , | + ⟩ , | - ⟩ ; должно ли измерение быть в стандартном базисе , или также может быть в некоторой другой основе), но они не имеют никакого существенного различия.$\lvert 1 \rangle$$\lvert +\rangle$$\lvert -\rangle$

Квантовое блуждание с дискретным временем

«Квантовое блуждание в дискретном времени» - это квантовое изменение случайного блуждания, в котором есть «ходок» (или несколько «ходоков»), который выполняет небольшие шаги в графе (например, цепочка узлов или прямоугольная сетка). ). Разница в том, что когда случайный бродяга делает шаг в произвольно определенном направлении, квантовый бродяга делает шаг в направлении, определяемом квантовым регистром «монеты», который на каждом шаге «переворачивается» унитарным преобразованием, а не изменяется путем повторной выборки случайной величины. См. [  ArXiv: Quant-Ph / 0012090  ] для более ранней ссылки.

Для простоты я опишу квантовое блуждание на цикле размером ; хотя необходимо изменить некоторые детали, чтобы рассмотреть квантовые блуждания на более общих графах. В этой модели вычислений обычно делают следующее.$2^n$

1. Подготовьте регистр «позиции» для кубитов в некотором состоянии, таком как | 00 ⋯ 0 ⟩ , и «монета» регистр (со стандартными базисными состояниями , которые мы обозначим через | + 1 ⟩ и | - 1 ⟩ ) в некотором начальном состоянии , которое может быть суперпозицией двух стандартных базисных состояний.$n$$\lvert 00\cdots 0\rangle$$\lvert +1 \rangle$$\lvert -1 \rangle$
2. Выполните когерентное управляемо-унитарное преобразование, которое добавляет 1 к значению регистра положения (по модулю ), если монета находится в состоянии | + 1 ⟩ , и вычитает 1 к значению регистра позиции ( по модулю 2 п ) , если монета находится в состоянии | - 1 ⟩ .$2^n$$\lvert +1 \rangle$$2^n$$\lvert -1 \rangle$
3. Выполните фиксированное унитарное преобразование в регистр монет. Это играет роль "броска монеты", чтобы определить направление следующего шага. Затем мы вернемся к шагу 2.$C$

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

Эта модель также часто описывается с точки зрения поиска или определения местоположения «помеченных» элементов на графике, и в этом случае выполняется другой шаг (для вычисления того, отмечен ли узел, на котором находится ходок, и затем для измерения результата этого вычисления ), прежде чем вернуться к шагу 2. Другие варианты такого рода являются разумными.

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

Эта модель вычислений, строго говоря, является частным случаем модели унитарных цепей, но мотивирована очень специфической физической интуицией, которая привела к некоторому алгоритмическому пониманию (см., Например, [  arXiv: 1302.3143  ]) для ускорений за полиномиальное время в ограниченной ошибке. квантовые алгоритмы. Эта модель также является близким родственником квантового блуждания с непрерывным временем как модели вычислений.

Квантовые схемы с промежуточными измерениями

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

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

Квантовый отжиг

Квантовый отжиг - это модель квантовых вычислений, которая, грубо говоря, обобщает адиабатическую модель вычислений. В результате работы D-WAVE по этому вопросу она привлекла популярное и коммерческое внимание.

Точно то, из чего состоит квантовый отжиг , не так четко определено, как другие модели вычислений, в основном потому, что оно представляет больший интерес для квантовых технологов, чем для ученых-компьютерщиков. Вообще говоря, мы можем сказать, что обычно его рассматривают люди с побуждениями инженеров, а не с побуждениями математиков, поэтому у субъекта, по-видимому, много интуиций и практических правил, но мало «формальных» результатов. На самом деле, в ответе на мой вопрос о квантовом отжиге , мы Andrew O говорим, что « квантовый отжиг не может быть определен без учета алгоритмов и аппаратного обеспечения.«Тем не менее,« квантовый отжиг », по-видимому, достаточно четко определен, чтобы его можно было описать как способ подхода к решению проблем с квантовыми технологиями с помощью конкретных методов - и поэтому, несмотря Andrew Oна оценку, я думаю, что он воплощает некоторую неявно определенную модель вычисление. Я попытаюсь описать эту модель здесь.

Интуиция позади модели

$$\begin{aligned} H_{\rm{classical}} &= \sum_{i,j} J_{ij} s_i s_j \\ H_{\rm{quantum}} &= A(t) \sum_{i,j} J_{ij} \sigma_i^z \sigma_j^z - B(t) \sum_i \sigma_i^x \end{aligned}$$ $s_i \in \{0,1\}$

• $\Delta E = E_1 - E_0$$\{s_i\}_{i=1}^n$
• $\Delta E > 0$

$T > 0$будет стабильное распределение («тепловое состояние») присваиваний, которое является равномерным распределением при «бесконечной» температуре и которое все больше и больше влияет на глобальные минимальные энергетические состояния при понижении температуры. Если вам потребуется достаточно много времени, чтобы понизить температуру от бесконечной до почти нулевой, в принципе вы должны быть уверены, что найдете глобальный оптимум для задачи минимизации энергии. Таким образом, моделируемый отжиг является подходом к решению задач оптимизации.

$t = 0$

$$A(t=0) = 0, \qquad B(t=0) = 1$$ $\def\ket#1{\lvert#1\rangle}\ket{\psi_0} \propto \ket{00\cdots00} + \ket{00\cdots01} + \cdots + \ket{11\cdots11}$$A(t)$$B(t)$ $$A(t_f) = 1, \qquad B(t_f) = 0.$$

$A(t)$$B(t)$$0$$1$$A(t)$$B(t)$$A(t)$$B(t)$D-Wave рассмотрел преимущества приостановки графика отжига и «отжига в обратном направлении» .

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

Сравнение с классическим моделируемым отжигом

Несмотря на терминологию, не сразу ясно, что есть много общего у квантового отжига с классическим отжигом. Основные различия между квантовым отжигом и классическим моделируемым отжигом заключаются в том, что:

• При квантовом отжиге состояние в некотором смысле является в идеале чистым состоянием, а не смешанным состоянием (что соответствует распределению вероятностей при классическом отжиге);

• При квантовом отжиге эволюция обусловлена ​​явным изменением гамильтониана, а не внешнего параметра.

$$\tilde H_{\rm{classical}} = A(t) \sum_{i,j} J_{ij} s_i s_j - B(t) \sum_{i,j} \textit{const.}$$ $A(t) = t\big/(t_F - t)$$B(t) = t_F - t$$t_F > 0$$A(0) = 0$$A(t) \to +\infty$$t \to t_F$ $$p(x \to y) = \max\Bigl\{ 1,\; \exp\bigl(-\gamma \Delta E_{x\to y}\bigr) \Bigr\}$$ $\gamma$$E_{x \to y}$$t=0$$t \to t_F$$t$$t \to t_F$вероятность любого увеличения энергии исчезает (потому что любое возможное увеличение является дорогостоящим).

$t \to t_F$, Распространенная идиома в описании квантового отжига - говорить о «туннелировании» через энергетические барьеры - это, безусловно, относится к тому, как люди рассматривают квантовые прогулки: рассмотрим, например, работу Farhi et al. о квантовых ускорениях в непрерывном времени для оценки цепей NAND и более фундаментальной работе Вонга по квантовым блужданиям по туннелированию линий через потенциальные барьеры . Канцлером [ arXiv: 1606.06800 ] была проделана некоторая работа по рассмотрению квантового отжига в терминах квантовых блужданий, хотя, как представляется, есть место для более формального и полного описания.

На чисто эксплуатационном уровне кажется, что квантовый отжиг дает преимущество в производительности по сравнению с классическим отжигом (см., Например, эти слайды о разнице в характеристиках между квантовым и классическим отжигом , из группы Тройера в ETH, около 2014 г.).

Квантовый отжиг как явление, в отличие от вычислительной модели

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

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

Некоторые люди иногда описывают шум как нечто существенное для процесса квантового отжига. Например, Boixo et al. [ arXiv: 1304.4595 ] напишите

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

Возможно, было бы правильным описать его как неизбежную особенность систем, в которых будет выполняться отжиг (просто потому, что шум является неизбежной особенностью системы, в которой вы будете выполнять квантовую обработку информации любого рода): как Andrew Oпишет « на самом деле нет Ванны действительно помогают квантовому отжигу ». Возможно, что диссипативный процесс может помочь квантовому отжигу, помогая системе построить население в состояниях с более низкой энергией (как предложено в работе Amin et al. , [ ArXiv: cond-mat / 0609332 ]), но, по-видимому, это, по сути, классический эффект, который по своей природе требует тихой низкотемпературной среды, а не «присутствия шума».

Суть

Можно сказать - в частности, теми, кто его изучает - что квантовый отжиг - это эффект, а не модель вычислений. Тогда «квантовый отжиг» лучше всего понимать как «машину, которая реализует эффект квантового отжига», а не машину, которая пытается воплотить модель вычислений, известную как « квантовый отжиг ». Однако то же самое можно сказать и об адиабатических квантовых вычислениях, которые, по моему мнению, правильно, описаны как модель вычислений сами по себе.

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