В квантовых вычислениях теорема Готтесмана –Книлла — это теоретический результат Дэниела Готтесмана и Эмануэля Книлла, который утверждает, что схемы стабилизаторов, схемы, которые состоят только из вентилей из нормализатора группы Паули кубита , также называемой группой Клиффорда , могут быть идеально смоделированы за полиномиальное время на вероятностном классическом компьютере. Группа Клиффорда может быть сгенерирована исключительно с использованием CNOT, Адамара и фазового вентиля S ; [1] и, следовательно, схемы стабилизаторов могут быть построены с использованием только этих вентилей.
Причина ускорения квантовых компьютеров пока не до конца понятна [ требуется цитата ] . Теорема доказывает, что для всех квантовых алгоритмов с ускорением, которое опирается на запутанность, которая может быть достигнута с помощью CNOT и вентиля Адамара для создания запутанных состояний, этот тип запутанности сам по себе не дает никаких вычислительных преимуществ.
Существует более эффективное моделирование схем стабилизатора, чем конструкция оригинальной публикации [1] с реализацией. [2]
Теорема Готтесмана–Книлла была опубликована в статье одного автора Готтесмана, в которой он приписывает результат Книллу через частное общение. [3]
Теорема: Квантовую схему, использующую только следующие элементы, можно эффективно смоделировать на классическом компьютере:
Теорема Готтесмана–Книлла показывает, что даже некоторые сильно запутанные состояния могут быть эффективно смоделированы. Несколько важных типов квантовых алгоритмов используют только вентили Клиффорда, наиболее важными из которых являются стандартные алгоритмы для дистилляции запутанности и для квантовой коррекции ошибок . С практической точки зрения схемы стабилизаторов были смоделированы за время O ( n log n ) с использованием формализма состояний графа .