Пороговая теорема

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

Объяснение

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

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

Пороговая теорема для квантовых вычислений ^[6]^: 481: Квантовая схема на n кубитах и содержащая p(n) вентили может быть смоделирована с вероятностью ошибки не более ε, используя $O(\log ^{c}(p(n)/\varepsilon )p(n))$ вентили (для некоторой константы c ) на оборудовании, компоненты которого выходят из строя с вероятностью не более p , при условии, что p ниже некоторого постоянного порога , $p<p_{\rm {th}}$ и с учетом разумных предположений о шуме в базовом оборудовании.

Пороговые теоремы для классических вычислений имеют ту же форму, что и выше, за исключением классических схем вместо квантовых. Стратегия доказательства для квантовых вычислений аналогична стратегии классических вычислений: для любой конкретной модели ошибок (например, отказа каждого вентиля с независимой вероятностью 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 .
^ Jump up to: ^а ^б Нилл, Э. (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 века?» .
Скотт Ааронсон . «Лекция 14 PHYS771: Скептицизм квантовых вычислений» : «Вся суть пороговой теоремы заключается в том, что вы исправляете ошибки быстрее, чем они создаются. В этом весь смысл и вся нетривиальность, которую показывает теорема. Вот проблему, которую он решает».

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

[Neumann56-1] Нойман, Дж. фон (1956-12-31), «Вероятностная логика и синтез надежных организмов из ненадежных компонентов» , «Исследование автоматов». (AM-34) , Принстон: Princeton University Press, стр. 43–98, doi : 10.1515/9781400882618-003 , ISBN 978-1-4008-8261-8 , получено 10 октября 2020 г.

[AB96-2] Ааронов, Дорит; Бен-Ор, Майкл (1 января 2008 г.). «Отказоустойчивые квантовые вычисления с постоянной частотой ошибок» . SIAM Journal по вычислительной технике . 38 (4): 1207–1282. arXiv : Quant-ph/9906129 . дои : 10.1137/S0097539799359385 . ISSN 0097-5397 . S2CID 8969800 .

[KLZ97-3] Jump up to: ^а ^б Нилл, Э. (16 января 1998 г.). «Устойчивые квантовые вычисления» . Наука . 279 (5349): 342–345. arXiv : Quant-ph/9702058 . Бибкод : 1998Sci...279..342K . дои : 10.1126/science.279.5349.342 .

[Kitaev97-4] Китаев, А.Ю. (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 .

[Shor96-5] Шор, П.В. (1996). «Отказоустойчивые квантовые вычисления» . Материалы 37-й конференции по основам информатики . Берлингтон, Вирджиния, США: IEEE Comput. Соц. Нажимать. стр. 56–65. дои : 10.1109/SFCS.1996.548464 . ISBN 978-0-8186-7594-2 . S2CID 7508572 .

[MikeNIke-6] Нильсен, Майкл А .; Чуанг, Исаак Л. (июнь 2012 г.). Квантовые вычисления и квантовая информация (изд. к 10-летию). Кембридж: Издательство Кембриджского университета . ISBN 9780511992773 . OCLC 700706156 .

[7] Ааронсон, Скотт ; Гранаде, Крис (осень 2006 г.). «Лекция 14: Скептицизм квантовых вычислений» . PHYS771: Квантовые вычисления со времен Демокрита . Штетл оптимизирован . Проверено 27 декабря 2018 г.

[8] Фаулер, Остин Г.; Стивенс, Эшли М.; Грошковски, Питер (11 ноября 2009 г.). «Высокопороговые универсальные квантовые вычисления на поверхностном коде». Физический обзор А. 80 (5): 052312. arXiv : 0803.0272 . Бибкод : 2009PhRvA..80e2312F . дои : 10.1103/physreva.80.052312 . ISSN 1050-2947 . S2CID 119228385 .

[10] Кэмпбелл, Эрл Т.; Терхал, Барбара М.; Вуйо, Кристоф (13 сентября 2017 г.). «Пути к отказоустойчивым универсальным квантовым вычислениям». Природа . 549 (7671): 172–179. arXiv : 1612.07330 . Бибкод : 2017Natur.549..172C . дои : 10.1038/nature23460 . ISSN 0028-0836 . ПМИД 28905902 . S2CID 4446310 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[а]

[9]