Отказоустойчивые квантовые вычисления

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

Порог квантового шума

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

Отказоустойчивость подразумевает обеспечение надежности вычислений с использованием ненадежных компонентов. Если у нас задана модель шума, можем ли мы надежно выполнять вычисления в его присутствии? Например, можно параллельно выполнять множество копий классических вычислений, периодически используя мажоритарные вентили для выявления и исправления ошибок. Фон Нейман в 1956 г. показал, что если каждый из вентилей выходит из строя независимо с вероятностью p, поменяв значение выходного бита 0 $ 1, то такая схема отказоустойчивости все еще позволяет производить произвольно надежные вычисления при условии, что p находится ниже некоторого постоянного порога (значение которого зависит от конкретики модели) [10].

Элементарные вентили квантового компьютера гораздо более чувствительны к шумам, чем классические транзисторы, поскольку в зависимости от реализации они имеют дело со спинами одиночных электронов, поляризациями фотонов и не менее хрупкими субатомными частицами. Может оказаться, что не удастся создать системы с коэффициентом шума менее 10~2, или, возможно, 10~3 на вентиль. Кроме того, феномен запутывания делает квантовые системы хрупкими по своей природе. Например, в состоянии кота Шредингера – равномерной суперпозиции живого и мертвого кота, которая часто записывается в идеальном виде как 1/p2(j0ni + j1ni) – взаимодействие всего с одним квантовым битом («кубитом») способно вызвать разрушение, или декогеренцию, всей системы. Поэтому методы обеспечения отказоустойчивости будут иметь важное значение для реализации потенциала квантовых компьютеров. Практические методы отказоустойчивости потребуются для контроля над высоким уровнем шума – и должны обеспечивать его с минимальными накладными расходами, поскольку кубиты стоят дорого.

Отказоустойчивые квантовые вычисления, рисунок 1 Ошибки инвертирования разряда (X-ошибки) меняют значения 0 и 1. В кубите значения |0> и |1> могут быть представлены горизонтальной и вертикальной поляризацией фотона, соответственно. Ошибки инвертирования фазы (Z-ошибки) меняют на ±45° поляризованные состояния |+> и |->

Квантовые системы являются непрерывными, а не дискретными, поэтому существует множество возможных моделей шума. Тем не менее, основные особенности квантового шума в контексте отказоустойчивости можно описать простой дискретной моделью, схожей с использовавшейся фон Нейманом. Основное отличие заключается в том, что помимо X-ошибок инвертирования разряда, которые меняют 0 на 1 и наоборот, возможны также Z-ошибки инвертирования фазы, которые меняют значения j+i = 1/p2(j0i + j1i) и |-> = 1/л/2(|0) - 1i) (Fig. 1). Шумный вентиль моделируется как идеальный вентиль с последующим независимым введением ошибок X, Z, или Y (сочетающей X- и Z-ошибку) с соответствующими вероятностями pX, pZ, pY. Одной из популярных моделей является независимый деполяризационный шум (pX = pZ = pY = p/3); деполяризованный кубит полностью рандомизирован.

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

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

Важнейшим результатом в концепции отказоустойчивости является наличие порога шума для определенных моделей шума и вычислительных моделей.

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

Квантовая схема с N вентилями может априори допускать только O(1/N) ошибок на один вентиль, поскольку всего один отказ может привести к рандомизации всей выдачи. В 1996 году Шор показал, как можно справиться с O(1/poly(log N)) ошибками на один вентиль, закодировав каждый кубит в poly(log N)-размерный квантовый код коррекции ошибок, а затем реализуя каждый вентиль желаемой схемы непосредственно на закодированных кубитах, чередуя вычисления и шаги исправления ошибок (это напоминает схему фон Неймана) [ ]. Результат Шора состоит из двух основных технических частей:

1. Серьезным результатом было открытие кодов квантовой коррекции ошибок (QECC). Примечательно, что несмотря на то, что квантовые ошибки могут быть непрерывными, кодов, которые исправляют дискретные ошибки, оказывается достаточно. (Измерение синдрома блока кода превращается в дискретное событие об ошибке). Первым квантовым кодом, обнаруженным Шором, был 9-кубитный код, состоящий из конкатенации трехкубитного кода j 0 i-> |000), j1 i-> |111) для защиты от ошибок инвертирования разряда, тогда как его дуальный код j+ i-> | + ++i ;) i-> | ) обеспечивал защиту от ошибок инвертирования фазы. С тех пор было обнаружено много других QECC. Такие коды, как 9-кубитный код, способный исправлять ошибки разряда и фазы по отдельности, известны как коды Калдербанка-Шора-Стина (Calderbank-Shor-Steane, CSS) и имеют квантовые кодовые слова, которые одновременно являются суперпозициями кодовых слов классических кодов в базах j0/1i and j + /—).

2. Коды QECC позволяют использовать квантовую память или общаться по шумному каналу. Для вычисления, однако, должна быть возможность расчета на основе кодирования последовательности состояний в отсутствие первичного декодирования. Операция считается отказоустойчивой, если она не может привести к коррелированным ошибкам внутри блока кода. При наличии n-битного мажоритарного кода все классические вентили могут быть применены перпендикулярно: закодированный вентиль можно реализовать посредством применения незакодированного вентиля к битам i каждого блока кода, 1 < i < n. Эта операция является отказоустойчивой, так как один отказ влияет не более чем на один бит в каждом блоке и, таким образом, отказы не могут распространяться слишком быстро. Для квантовых кодов CSS вентиль с контролируемым отрицанием CNOT: ja;b i!j 7a;a (B bi может применяться перпендикулярно аналогичным образом. Однако сам по себе вентиль CNOT не является универсальным, поэтому Шор также предложил отказоустойчивую реализацию вентиля Тоффоли ja; b; c i!j 7a; b; c ф (a Л b)i. Как для коррекции ошибок при использовании неисправных вентилей, так и для начального этапа подготовки требуются дополнительные процедуры. Кодирование j 0i представляет сильно запутанное состояние и трудно для подготовки (в отличие от 0n для классического мажоритарного кода).

Однако Шор не доказал существование константного допустимого уровня шума, или порога шума. Несколько групп исследователей – Ахаронов/Бен-Ор, Китаев, Книлл/Лафламм/Зурек – пришли к идее использовать меньшие по размеру коды и многократно выполнять конкатенацию процедуры поверх себя самой. Интуитивно представляется, что при наличии кода с расстоянием 3 (т. е. кода, который исправляет любую одну ошибку) можно ожидать, что «эффективный» коэффициент логических ошибок закодированного вентиля не будет превышать cp2 для некоторой константы c, потому что одну ошибку можно исправить, а две – нет. Тогда эффективный коэффициент ошибок для дважды кодированного вентиля должен составлять не более c(cp2)2; а поскольку эффективный коэффициент ошибок убывает дважды экспоненциально относительно числа уровней конкатенации, то накладные расходы при достижении коэффициента ошибок 1/N составляют только poly(logN). Порог для улучшения – cp2 < p, p < 1/c. Однако эта грубая прикидка не является жесткой, поскольку эффективный коэффициент ошибок плохо определен, и логические ошибки не обязательно должны соответствовать той же модели, что и физические ошибки (например, они не будут независимыми).

Ахаронов с Бен-Ором и Китаев в 1997 году независимо друг от друга предложили строгие доказательства существования положительного константного порога шума [1, 5].

В целом с тех пор был достигнут прогресс по двум направлениям задачи об отказоустойчивости:

1. Во-первых, была продолжена работа по расширению набора моделей шума и вычислительных моделей, для которых известно существование порога отказоустойчивости. Например, коррелированный или даже враждебный шум, ошибки утечки (когда кубит выходит из подпространства j0i; j1i) и немарковский шум (в этом случае окружение обладает памятью) – все это оказалось допустимым в теории, даже при наличии только локальных вентилей.

2. Доказательства существования порогов устанавливают, что построение рабочего квантового компьютера в принципе возможно. Физикам необходимо только разработать квантовые системы с достаточно низким константным уровнем шума. Но для реализации потенциала квантового компьютера потребуются практические схемы отказоустойчивости. Схемы должны будут выдерживать высокий уровень шума (а не просто константный) и добиваться этой цели с низкими накладными расходами (а не просто полилогарифмическими). Однако грубые оценки допустимого уровня шума согласно исходным доказательствам существования не являются многообещающими – необходим уровень ниже 10~6 на вентиль. Если истинный порог составляет всего 10~6, то построить квантовый компьютер будет практически невозможно. Поэтому, во-вторых, была проведена значительная работа по оптимизации схем отказоустойчивости – главным образом с целью повышения допустимого уровня шума. Такие оптимизации обычно оцениваются с помощью симуляций и эвристических аналитических моделей. Однако недавно Алиферис, Готтесман и Прескилл разработали метод доказательства достаточно хороших нижних границ порога, до 2 х 10~4, на основе подсчета «злокачественных» множеств локализаций ошибок [3].

В своей революционной работе Книлл [6] построил новую схему отказоустойчивости, основанную на очень эффективных кодах с расстоянием 2. Его коды не исправляют ошибки; в схеме активно используется поствыбор в случае отсутствия обнаруженных ошибок – т. е. при обнаружении ошибки объемлющая подпрограмма перезапускается. Клнилл оценил порог на уровне выше 3% на каждый вентиль, что на порядок больше предыдущих оценок. Рейхардт доказал нижнюю границу порога 10~3 для аналогичной схемы [ ], отчасти поддерживая высокую оценку Книлла. Однако зависимость от поствыбора приводит к огромным накладным расходам при высокой частоте ошибок, что значительно снижает практичность. (Классическая схема отказоустойчивости, основанная на обнаружении ошибок, может не быть эффективной, но квантовая телепортация допускает, по крайней мере, теоретическую эффективность схемы Книлла). По-видимому, существует компромисс между допустимым уровнем шума и накладными расходами, необходимыми для его достижения. Существует несколько взаимодополняющих подходов к обеспечению квантовой отказоустойчивости. Для достижения максимальной эффективности целесообразно использовать любую известную структуру шума, прежде чем переходить к общим процедурам отказоустойчивости. Специализированные методы включают тщательное квантовое проектирование, методы ядерного магнитного резонанса (ЯМР), такие как динамическая развязка и композитные последовательности импульсов, а также подпространства, свободные от декогерентности. Для очень малых квантовых компьютеров такие методы могут обеспечить достаточную защиту от шума. Не исключено, что будет спроектировано или открыто надежное по своей сути квантово-вычислительное устройство, подобное транзистору для классических вычислений, и это является целью топологических квантовых вычислений [4].

Применение

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

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

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

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

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

С теоретической точки зрения представляет интерес лучший вариант асимптотических накладных расходов при моделировании схемы FTC в сравнении с C. Накладные расходы могут измеряться с точки зрения размера N и глубины/времени T. При каскадном кодировании размер и глубина FTC равны O(NpolylogN) и O(TpolylogN), соответственно. Однако глубина классических схем C может составлять только O(T). Неизвестно, можно ли улучшить накладные расходы с точки зрения квантовой глубины.

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

Схемы обеспечения отказоустойчивости были смоделированы для крупных квантовых систем с целью получения оценок значений порогов. К примеру, обширные симуляции, включая геометрические ограничения локальности, провели Тэкер и др. [9].

Коррекция ошибок при помощи очень маленьких кодов была экспериментально проверена в лаборатории.

Ссылка на код

Эндрю Кросс написал и распространяет код, дающий оценки методом Монте-Карло и строгие нижние границы для порогов отказоустойчивости: http://web.mit.edu/awcross/www/qasm-tools/. Эмануэль Книлл опубликовал код Mathematica для оценки порогов отказоустойчивости для некоторых схем, основанных на поствыборе: http://arxiv.org/e-print/quant-ph/0404104.

См. также

• Квантовая коррекция ошибок

Литература

1. Aharonov, D., Ben-Or, M.: Fault-tolerant quantum computation with constant error rate. In: Proc. 29th ACM Symp. on Theory of Computing (STOC), pp. 176-188, (1997).quant-ph/9906129

2. Aharonov, D., Kitaev, A.Y., Preskill, J.: Fault-tolerant quantum computation with long-range correlated noise. Phys. Rev. Lett. 96,050504 (2006). quant-ph/0510231

3. Aliferis, P., Gottesman, D., Preskill, J.: Quantum accuracy threshold for concatenated distance-3 codes. Quant. Inf. Comput. 6, 97-165 (2006).quant-ph/0504218

4. Freedman, M.H., Kitaev, A.Y., Larsen, M.J., Wang, Z.: Topological quantum computation. Bull. AMS 40(1), 31-38 (2002)

5. Kitaev, A.Y.: Quantum computations: algorithms and error correction. Russ. Math. Surv. 52,1191-1249 (1997)

6. Knill, E.: Quantum computing with realistically noisy devices. Nature 434,39-44 (2005)

7. Reichardt, B.W.: Error-detection-based quantum fault tolerance against discrete Pauli noise. Ph.D. thesis, University of California, Berkeley (2006). quant-ph/0612004

8. Shor, P.W.: Fault-tolerant quantum computation. In: Proc. 37th Symp. on Foundations of Computer Science (FOCS) (1996). quant-ph/9605011

9. Thaker, D.D., Metodi, T.S., Cross, A.W., Chuang, I.L., Chong, F.T.: Quantum memory hierarchies: Efficient designs to match available parallelism in quantum computing. In: Proc. 33rd. Int. Symp. on Computer Architecture (ISCA), pp. 378-390 (2006) quant-ph/0604070

10. von Neumann, J.: Probabilistic logic and the synthesis of reliable organisms from unreliable components. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp.43-98. Princeton University Press, Princeton (1956)