Пороговая теорема
В квантовых вычислениях ( пороговая теорема или квантовая теорема отказоустойчивости ) утверждает, что квантовый компьютер с частотой физических ошибок ниже определенного порога может, посредством применения схем квантового исправления ошибок , подавлять частоту логических ошибок до сколь угодно низкого уровня. Это показывает, что квантовые компьютеры можно сделать отказоустойчивыми , как аналог пороговой теоремы фон Неймана для классических вычислений. [1] Этот результат был доказан (для различных моделей ошибок) группами Дорит Ахаранов и Михаэля Бен-Ора; [2] Эмануэль Книлл , Раймон Лафламм и Войцех Журек ; [3] и Алексей Китаев [4] независимо. [3] Эти результаты основаны на статье Питера Шора . [5] что доказало более слабую версию пороговой теоремы.
Объяснение [ править ]
Ключевой вопрос, который решает пороговая теорема, заключается в том, могут ли квантовые компьютеры на практике выполнять длительные вычисления, не поддаваясь шуму. Поскольку квантовый компьютер не сможет идеально выполнять операции с вентилями , неизбежна небольшая постоянная ошибка; гипотетически это может означать, что квантовые компьютеры с несовершенными вентилями могут применять только постоянное количество вентилей, прежде чем вычисления будут уничтожены шумом.
Удивительно, но теорема о квантовом пороге показывает, что если ошибка выполнения каждого вентиля является достаточно маленькой константой, можно выполнять сколь угодно длинные квантовые вычисления со сколь угодно хорошей точностью, лишь с небольшими дополнительными накладными расходами, связанными с количеством вентилей. Формальная формулировка пороговой теоремы зависит от типов рассматриваемых кодов коррекции ошибок и модели ошибок. Квантовые вычисления и квантовая информация Майкла Нильсена и Исаака Чуанга дают общую основу для такой теоремы:
Пороговая теорема для квантовых вычислений [6] : 481 : Квантовая схема на n кубитах и содержащая p(n) вентили может быть смоделирована с вероятностью ошибки не более ε, используя
Пороговые теоремы для классических вычислений имеют ту же форму, что и выше, за исключением классических схем вместо квантовых. Стратегия доказательства для квантовых вычислений аналогична стратегии классических вычислений: для любой конкретной модели ошибок (например, отказа каждого вентиля с независимой вероятностью p ) используйте коды, исправляющие ошибки , чтобы построить лучшие вентили из существующих вентилей. Хотя эти «лучшие вентили» больше и поэтому более склонны к ошибкам внутри них, их свойства исправления ошибок означают, что у них меньшая вероятность отказа, чем у исходного вентиля (при условии, что p — достаточно малая константа). Затем можно использовать эти лучшие вентили для рекурсивного создания еще лучших вентилей, пока не будут получены вентили с желаемой вероятностью отказа, которые можно будет использовать для желаемой квантовой схемы. По словам теоретика квантовой информации Скотта Ааронсона :
«Все содержание пороговой теоремы заключается в том, что вы исправляете ошибки быстрее, чем они возникают. В этом весь смысл и вся нетривиальность, которую показывает теорема. Вот проблема, которую она решает». [7]
Пороговое значение на практике [ править ]
По текущим оценкам, порог поверхностного кода составляет порядка 1%. [8] хотя оценки варьируются в широких пределах, и их трудно вычислить из-за экспоненциальной сложности моделирования больших квантовых систем. [ нужна ссылка ] [а] При вероятности ошибки деполяризации 0,1% для поверхностного кода потребуется примерно 1000–10 000 физических кубитов на кубит логических данных. [9] хотя большее количество типов патологических ошибок может радикально изменить эту цифру. [ нужны дальнейшие объяснения ]
См. также [ править ]
Примечания [ править ]
- ^ Широко распространено мнение, что классическим компьютерам экспоненциально сложно моделировать квантовые системы. Эта проблема известна как квантовая проблема многих тел . Однако квантовые компьютеры могут моделировать многие (хотя и не все) гамильтонианы за полиномиальное время с ограниченными ошибками , что является одним из основных преимуществ квантовых вычислений. применимо к химическому моделированию, открытию лекарств, производству энергии, моделированию климата и производству удобрений (например, FeMoco Это также ). Из-за этого квантовые компьютеры могут лучше классических компьютеров помочь в разработке будущих квантовых компьютеров.
Ссылки [ править ]
- ^ Нойман, Дж. фон (1956-12-31), «Вероятностная логика и синтез надежных организмов из ненадежных компонентов» , «Исследование автоматов». (AM-34) , Принстон: Princeton University Press, стр. 43–98, doi : 10.1515/9781400882618-003 , ISBN 978-1-4008-8261-8 , получено 10 октября 2020 г.
- ^ Ааронов, Дорит; Бен-Ор, Майкл (1 января 2008 г.). «Отказоустойчивые квантовые вычисления с постоянной частотой ошибок» . SIAM Journal по вычислительной технике . 38 (4): 1207–1282. arXiv : Quant-ph/9906129 . дои : 10.1137/S0097539799359385 . ISSN 0097-5397 . S2CID 8969800 .
- ↑ Перейти обратно: Перейти обратно: а б Нилл, Э. (16 января 1998 г.). «Устойчивые квантовые вычисления» . Наука . 279 (5349): 342–345. arXiv : Quant-ph/9702058 . Бибкод : 1998Sci...279..342K . дои : 10.1126/science.279.5349.342 .
- ^ Китаев, А.Ю. (01.01.2003). «Отказоустойчивые квантовые вычисления с помощью анионов» . Анналы физики . 303 (1): 2–30. arXiv : Quant-ph/9707021 . Бибкод : 2003АнФиз.303....2К . дои : 10.1016/S0003-4916(02)00018-0 . ISSN 0003-4916 . S2CID 119087885 .
- ^ Шор, П.В. (1996). «Отказоустойчивые квантовые вычисления» . Материалы 37-й конференции по основам информатики . Берлингтон, Вирджиния, США: IEEE Comput. Соц. Нажимать. стр. 56–65. дои : 10.1109/SFCS.1996.548464 . ISBN 978-0-8186-7594-2 . S2CID 7508572 .
- ^ Нильсен, Майкл А .; Чуанг, Исаак Л. (июнь 2012 г.). Квантовые вычисления и квантовая информация (изд. к 10-летию). Кембридж: Издательство Кембриджского университета . ISBN 9780511992773 . OCLC 700706156 .
- ^ Ааронсон, Скотт ; Гранаде, Крис (осень 2006 г.). «Лекция 14: Скептицизм квантовых вычислений» . PHYS771: Квантовые вычисления со времен Демокрита . Штетл оптимизирован . Проверено 27 декабря 2018 г.
- ^ Фаулер, Остин Г.; Стивенс, Эшли М.; Грошковски, Питер (11 ноября 2009 г.). «Высокопороговые универсальные квантовые вычисления на поверхностном коде». Физический обзор А. 80 (5): 052312. arXiv : 0803.0272 . Бибкод : 2009PhRvA..80e2312F . дои : 10.1103/physreva.80.052312 . ISSN 1050-2947 . S2CID 119228385 .
- ^ Кэмпбелл, Эрл Т.; Терхал, Барбара М.; Вуйо, Кристоф (13 сентября 2017 г.). «Пути к отказоустойчивым универсальным квантовым вычислениям». Природа . 549 (7671): 172–179. arXiv : 1612.07330 . Бибкод : 2017Natur.549..172C . дои : 10.1038/nature23460 . ISSN 0028-0836 . ПМИД 28905902 . S2CID 4446310 .
Внешние ссылки [ править ]
- Гил Калай . «Вечный двигатель XXI века?» .
- Скотт Ааронсон . «PHYS771 Лекция 14: Скептицизм квантовых вычислений» : «Вся суть пороговой теоремы заключается в том, что вы исправляете ошибки быстрее, чем они создаются. В этом весь смысл и вся нетривиальность, которую показывает теорема. Вот проблему, которую он решает».
