Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В квантовых вычислениях ( квантовая ) теорема о пороге (или теорема о квантовой отказоустойчивости ) утверждает, что квантовый компьютер с частотой физических ошибок ниже определенного порога может посредством применения схем квантовой коррекции ошибок подавить частоту логических ошибок до произвольно низкого уровня. уровни. Это показывает, что квантовые компьютеры можно сделать отказоустойчивыми , как аналог пороговой теоремы фон Неймана для классических вычислений. [1] Этот результат был доказан (для различных моделей ошибок) группами Ахаранова и Бен-Ор; [2] Knill, Laflamme иЖурек ; [3] и Китаева [4] независимо друг от друга. [3] Эти результаты построены от бумаги из Шор , [5] , который доказал ослабленную версию пороговой теоремы.

Объяснение [ править ]

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

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

Пороговая теорема для квантовых вычислений [6] : 481 : Квантовая схема на n кубитах и ​​содержащая p (n) вентили может быть смоделирована с вероятностью ошибки не более ε, используя

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

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

«Все содержание теоремы о пороге состоит в том, что вы исправляете ошибки быстрее, чем они создаются. В этом весь смысл и все нетривиальные вещи, которые показывает теорема. Это проблема, которую она решает». [7]

Пороговое значение на практике [ править ]

Текущие оценки устанавливают порог для поверхностного кода порядка 1% [8], хотя оценки сильно различаются и их трудно вычислить из-за экспоненциальной сложности моделирования больших квантовых систем. [ необходима цитата ] [a] При вероятности деполяризации 0,1% поверхностный код потребует приблизительно 1 000–10 000 физических кубитов на логический кубит данных [9], хотя большее количество типов патологических ошибок может существенно изменить эту цифру. [ требуется дальнейшее объяснение ]

См. Также [ править ]

Заметки [ править ]

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

Ссылки [ править ]

  1. ^ Нойман, Дж. Фон (1956-12-31), "Вероятностная логика и синтез надежных организмов из ненадежных компонентов" , Исследования автоматов. (AM-34) , Princeton: Princeton University Press, стр. 43–98, ISBN. 978-1-4008-8261-8, получено 10.10.2020
  2. ^ Ааронов, Дорит; Бен-Ор, Майкл (01.01.2008). «Отказоустойчивые квантовые вычисления с постоянной частотой ошибок» . SIAM Journal on Computing . 38 (4): 1207–1282. arXiv : квант-ph / 9906129 . DOI : 10,1137 / S0097539799359385 . ISSN 0097-5397 . 
  3. ^ a b Knill, E. (1998-01-16). «Устойчивые квантовые вычисления» . Наука . 279 (5349): 342–345. arXiv : квант-ph / 9702058 . DOI : 10.1126 / science.279.5349.342 .
  4. ↑ Китаев, А.Ю. (01.01.2003). «Отказоустойчивые квантовые вычисления по анонам» . Летопись физики . 303 (1): 2–30. arXiv : квант-ph / 9707021 . DOI : 10.1016 / S0003-4916 (02) 00018-0 . ISSN 0003-4916 . 
  5. Перейти ↑ Shor, PW (1996). «Отказоустойчивые квантовые вычисления» . Материалы 37-й конференции по основам информатики . Берлингтон, Вирджиния, США: IEEE Comput. Soc. Пресс: 56–65. DOI : 10.1109 / SFCS.1996.548464 . ISBN 978-0-8186-7594-2.
  6. ^ Нильсен, Майкл А .; Чуанг, Исаак Л. (июнь 2012 г.). Квантовые вычисления и квантовая информация (10-летие изд.). Кембридж: Издательство Кембриджского университета . ISBN 9780511992773. OCLC  700706156 .
  7. ^ Ааронсон, Скотт ; Гранад, Крис (осень 2006 г.). «Лекция 14: Скептицизм квантовых вычислений» . PHYS771: квантовые вычисления со времен Демокрита . Штетл Оптимизированный . Проверено 27 декабря 2018 .
  8. ^ Фаулер, Остин G .; Стивенс, Эшли М .; Грошковский, Питер (11.11.2009). «Высокопороговые универсальные квантовые вычисления на поверхностном коде». Physical Review . 80 (5): 052312. arXiv : 0803.0272 . Bibcode : 2009PhRvA..80e2312F . DOI : 10.1103 / physreva.80.052312 . ISSN 1050-2947 . 
  9. ^ Кэмпбелл, Эрл Т .; Terhal, Barbara M .; Вуйо, Кристоф (13 сентября 2017). «Пути к отказоустойчивым универсальным квантовым вычислениям». Природа . 549 (7671): 172–179. arXiv : 1612.07330 . Bibcode : 2017Natur.549..172C . DOI : 10.1038 / nature23460 . ISSN 0028-0836 . PMID 28905902 .  

Внешние ссылки [ править ]

  • Гил Калаи . "Вечный двигатель 21 века?" .
  • Скотт Ааронсон . «PHYS771 Лекция 14: Скептицизм квантовых вычислений» : «Все содержание пороговой теоремы состоит в том, что вы исправляете ошибки быстрее, чем они создаются. В этом вся суть и вся нетривиальная вещь, которую показывает теорема. Это проблема, которую он решает ».