Теорема Готтесмана–Нилла
В квантовых вычислениях теорема Готтесмана -Нилла представляет собой теоретический результат Дэниела Готтесмана и Эмануэля Нилла , который утверждает, что схемы стабилизатора, схемы, которые состоят только из элементов нормализатора группы кубита Паули , также называемой группой Клиффорда , могут быть идеально смоделированы в квантовых вычислениях. полиномиальное время на вероятностном классическом компьютере. Группу Клиффорда можно создать исключительно с помощью CNOT, Адамара и фазового вентиля S ; [ 1 ] и поэтому схемы стабилизатора могут быть построены с использованием только этих вентилей.
Причина ускорения квантовых компьютеров еще не до конца понятна [ нужна ссылка ] . Теорема доказывает, что для всех квантовых алгоритмов с ускорением, основанным на запутанности, которое может быть достигнуто с помощью CNOT и вентиля Адамара для создания запутанных состояний, сама по себе такая запутанность не дает никакого вычислительного преимущества.
Существует более эффективное моделирование схем стабилизатора, чем конструкция оригинальной публикации. [ 1 ] с реализацией. [ 2 ]
Теорема Готтесмана-Нилла была опубликована Готтесманом в единственной авторской статье, в которой он приписывает результат Книлу в частном сообщении. [ 3 ]
Официальное заявление
[ редактировать ]Теорема: Квантовую схему, использующую только следующие элементы, можно эффективно смоделировать на классическом компьютере:
- Подготовка кубитов в состояниях вычислительного базиса,
- Ворота Клиффорда ( вентили Адамара , управляемые вентили НЕ , фазовые вентили S ) и
- Измерения в вычислительной основе.
Теорема Готтесмана-Нилла показывает, что даже некоторые сильно запутанные состояния можно эффективно моделировать. Некоторые важные типы квантовых алгоритмов используют только вентили Клиффорда, и наиболее важно это стандартные алгоритмы перегонки запутанности и квантовой коррекции ошибок . С практической точки зрения схемы стабилизатора были смоделированы за O ( n log n ) время с использованием формализма состояний графа .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Ааронсон, Скотт ; Готтесман, Дэниел (2004). «Улучшенное моделирование схем стабилизатора». Физический обзор А. 70 (5): 052328. arXiv : quant-ph/0406196 . Бибкод : 2004PhRvA..70e2328A . дои : 10.1103/physreva.70.052328 . S2CID 5289248 .
- ^ Ааронсон, Скотт ; Готтесман, Дэниел . «ТЭЦ: CNOT-Адамар-Фаза» . Скоттааронсон . Проверено 19 сентября 2017 г.
- ^ Готтесман, Дэниел (1998). «Гейзенберговское представление квантовых компьютеров». arXiv : Quant-ph/9807006 .
- Дэниел Готтесман (1998). «Гейзенберговское представление квантовых компьютеров». arXiv : Quant-ph/9807006 .
- С. Андерс и Х. Дж. Бригель (2006). «Быстрое моделирование схем стабилизатора с использованием представления графического состояния». Физический обзор А. 73 (2): 022334. arXiv : quant-ph/0504117v2 . Бибкод : 2006PhRvA..73b2334A . дои : 10.1103/PhysRevA.73.022334 . S2CID 12763101 .
- Нильсен, Майкл А .; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3 . OCLC 844974180 .
