М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 143
Текст из файла (страница 143)
Задача 10.2 (граница Варшамова — Гильберта). Докажите границу Вар- шамова-Гильберта для СЯЯ кодов, т. е. покажите, что существует СЯЯ [и, й[- код, способный исправить 4 ошибок, для которого — > 1 — 2Н (10.122) Можете также попробовать доказать гранину Варшамова — Гильберта для про- извольного симплектического кода, т. е. доказать, что существует симплекти- ческий [п.1с]-код, способный исправить | ошибок, для которого 7с 2 1об(3)$2$ (10.123) Задача 10.3 (кодирование симплектического кода). Пусть образующие кода имеют стандартную форму и закодированные операторы Я и Х также построены в стандартной форме.
Постройте цепь, преобразующую проверочную матрицу и х 2п, соответствующую списку всех образующих кода с закодированными операторами Я, вида (10.124) в стандартную форму (10.125) Задача 10.4 (кодирование с помощью телепортации). Пусть нужно за- кодировать симплектическим кодом кубит в неизвестном состоянии [ф). По- стройте схему для этого следующим образом. (1) Объясните, как построить устойчивым к ошибкам способом частично закодированное состояние [0)[Оь) + [1)[1ь) (10.126) 0 0 0 0 0 0 0 0 0 1 А~ Аэ 0 0 0 0 0 0 в о с Ю 1 Е Ат~ 0 1 10.6.
Квантовые вычисления, устойчивые к ошибкам 606 записав его как стабилизированное состояние, с тем, чтобы его можно было приготовить путем измерения образующих стабилизатора. (2) Покажите, как можно выполнить устойчивое к ошибкам измерение в базисе Велла над состоянием ~ф) и незакодированным кубитом из состояния (10.126). (3) С помощью операторов Паули исправьте полученный после измерения закодированный кубит, так чтобы его состояние стало ~ф), как в обычной квантовой схеме для телепортации.
Вычислите вероятность ошибки в такой схеме. Покажите, как нужно изменить схему, чтобы она выполняла устойчивое к ошибкам декодирование. Задача 10.5. Пусть С(Я) — симплектический (и, 1)-код, способный исправить ошибку в одном кубите. Объясните, как может быть реализован устойчивый к ошибкам элемент С1чОТ, действующий на два логических кубита, закодированных этим кодом, с использованием только устойчивых к ошибкам процедур приготовления стабилизированных состояний, измерения элементов стабилизатора, а также образующих нормали заторы, применяемых побитово. Краткое содержание главы ° Квантовый код, исправляющий ошибки. Квантовый (и, к, й)-код кодирует /с кубитов и кубитами с расстоянием Н.
° Условие квантового исправления ошибок. Пусть С вЂ” квантовый код, исправляющий ошибки, а Р— проектор на пространство кода С. Код может исправлять множество ошибок (Е;) тогда и только тогда, когда РЕ'ЕР=о; Р (10.127) для некоторой эрмитовой матрицы а. ° Симплектические коды. Пусть Я вЂ” стабилизатор симплектического кода С(Я), а (Еу) — набор оШибок из группы Паули, такой, что Е Еь ф Ф(Я) — Я для всех у и в.
Тогда (Е ) — исправляемый набор ошибок для кода С(Я). ° Устойчивое к ошибкам квантовое вычисление. Универсальный набор логических операпшй над вакодироваииьими состояниями может быть выполнен так, что эффективная вероятность ошибки в закодированном состоянии равна 0(рз), где р — вероятность ошибки в каждом элементе. 606 Глава 10. Исправление квантовых ошибок ° Пороговая теорема. Если шум в каждом квантовом элементе меньше некоторого порогового значения и удовлетворяет физически разумным предположениям, то можно надежно выполнять произвольно длинное квантовое вычисление. Для достижения надежности вычисления требуется только небольшое увеличение размера схемы. История и дополнительная литература Существует множество замечательных работ по классической теории информации, в которых рассматриваются коды, исправляющие ошибки. Особенно мы рекомендуем работу Маквильямс и Слоуна [296].
Авторы этой работы начинают с элементарных основ, а затем переходят к сложным вопросам, охватывая огромный объем материала. Более современное введение, также очень хорошее, дано в работе Уэлша [414]. Квшповое исправление ошибок было независимо открыто Шором [355), который построил девятикубитовый код, описанный в разд.
10.2, и Стином [371], использовавшим другой подход — изучение интерференционных свойств многочастичных запутанных состояний. Условия квантового исправления ошибок были независимо доказаны Беннетом, Дивинченцо, Смолиным и Вутерсом [42), а также Ниллом и Лафламом [216). Основой послужила более ранняя работа Экерта и Макчиавелло [142]. Пятикубитовый код был предложен Беннетом, Дивинченцо, Смолиным и Вутерсом [42) и независимо Лафламом, Микелем, Пазом и Зуреком [257].
Кальдербанк и Шор [104), а также Стин [372), используя идеи классического исправления ошибок, построили СЯЯ коды (коды Кальдербанка-Шоре-Стина). Кальдербанк и Шор также сформулировали и доказали границу ВаршамоваГильберта для СЯЯ кодов. Готтесман ]165] ввел формализм стабилизаторов, использовал его для построения симплектических кодов и изучил некоторые их свойства.
Независимо Кальдербанк, Раино, Шор и Слоун [102) предложиля эквивалентный подход к квантовому исправлению ошибок, основанный на классической теории кодов. Им удалось классифицировать почти все квантовые коды [103], а также доказать границу Варшамова-Гильберта для произвольного симплектического кода, которая была введена Экертом и Макиавелло [142]. Теорема Готтесмана-Нилла впервые по-видимому была сформулирована Готтесманом в работе [166], где он приписывает этот результат Ниллу, вместе с доказательством, на основе формализма стабилизаторов, который ввел Готтесман. Готтесман очень успешно применял формализм стабилизаторов для решения большого числа задач. В работе [166] приводится пример и даются ссылки на литературу.
Наше рассмотрение формализма стабилизаторов основано главным образом на работе [166], где можно найти большинство описанных здесь результатов, включая утверждение о том, что элемент Адамара, фазовый элемент и ОХОТ являются образующими нормэлизатора Ф(С„). 10.6. Квантовые вычисления, устойчивые к ошибкам 607 Известно много построений конкретных классов квантовых кодов; мы отметим здесь только некоторые из них.
Райне, Хардин, Шор и Слоун [339] построили интересный класс кодов, не являющихся симплектическими. Многие рассматривали квантовые коды для систем, отличных от кубитов. Следует особо отметить работы Готтесмана [167] и Райнса [335], которые построили недвоичные коды и рассмотрели устойчивые к ошибкам вычисления для них. Ааронова и Бен-Ор [2] построили недвоичные коды с использованием интересного метода, основанного на полиномах над конечными полями, и также рассмотрели устойчивые к ошибкам вычисления для таких кодов. Еще одна тема, которой мы не касались — приближенное квантовое исправление ошибок.
Как показали Леунг, Нильсен, Чанг и Ямамото [258], такое исправление ошибок может привести к улучшению квантовых кодов. Большой и интересный класс квантовых кодов, исправляющих ошибки (не описанный в этой главе) — так называемые бесшумные квантовые коды, или подпростракства без потери когерентности. Этой теме посвящено большое количество работ: для начала можно порекомендовать работы Занарди и Расетти [436, 431], Лидара, Чанга и Уайли [238], Бэкона, Кемпа, Лидара и Уайли [59, 236], Нилла, Лафлама и Виолы [219].
Известно множество неравенств для квантовых кодов, исправляющих ошибки. Часть из них получена из аналогичных классических неравенств. Экерт и Макчиавелло [142] указали на возможность доказательства квантового аналога границы Хэмминга. Эта конструкция и роль вырожденных квантовых кодов были последовательно объяснена Готтесманом [165]. Шор и Лафлам [361] доказали квантовый аналог классических тождеств Маквилльямса. Более общий подход к этим вопросам описан в работах [17], [13], [333, 336, 334].
Теория устойчивого к ошибкам вычисления для классических компьютеров разработана фон Нейманом [404] и обсуждается в монографии Винограда и Коуэна [412]. Шор [356] ввел понятие устойчивости к ошибкам для квантового вычисления и привел устойчивые к ошибкам схемы для всех основных этапов вычисления (приготовление состояний, квантовая логика, исправление ошибок и измерения). Китаев [213, 214] независимо разработал много аналогичных идей, включая устойчивые к ошибкам конструкции для многих основных квантовых логических элементов.
Сирак, Пеллипдари и Цоллер [101], а также Зурек и Лафлан [434] тоже сделали несколько шагов к устойчивым к ошибкам вычислениям. Дивинченцо и Шор показали, как можно выполнить устойчивое к ошибкам измерение синдрома для любого симплектического кода [132]. Готтесман [168], обобщив устойчивые к ошибкам конструкции, показал, как можно выполнять устойчивое к ошибкам вычисление для любого симплектического кода. С общим обзором этой работы и другими материалами, включая конструкцию для решения задачи 10.5, можно познакомиться в [166].
Устойчивые к ошибкам схемы для элементов Тоффоли и я/8 основаны на идеях, разработанных Готесманом и Чангом [161], а также Жу и Чангом [435]. Схема для устойчивого к ошибкам элемента Тоффоли из упражнения 10.68 разработана Шором [356]. Стив [374] создал много оригинальных конструкций для процедур, устойчивых к ошибкам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
