Квантовые операции группы Клиффорда и классические вычисления

Группа Клиффорда квантовых операторов порождается квантовых операций:

• Контролируемый-Z ,
• Адамар и
• Фаза ( ).$= |0\rangle\langle0| + i |1\rangle\langle1|$

Схема, состоящая только из этих ворот, может быть эффективно смоделирована на классическом компьютере. Однако, если я правильно понимаю, не все классические алгоритмы могут быть эффективно реализованы с помощью групповых операций Клиффорда, по крайней мере, насколько нам известно.

Существует ли конструкция для реализации, даже неэффективно или приблизительно, классического алгоритма, использующего групповые операции Клиффорда? Например, как вы реализуете ворота Тоффоли, используя групповые ворота Клиффорда, если это возможно?

Как указывалось в комментарии выше, если бы было возможно когерентно реализовать ворота Тоффоли с использованием групповых вентилей Клиффорда, тогда группа Клиффорда была бы универсальной для квантовых вычислений. В разделе 5 этой статьи было отмечено , что верно нечто еще более сильное: если говорить неформально, если существует класс квантовых цепей, которые можно эффективно моделировать классически и который универсален для классических вычислений, то BQP = BPP. Таким образом, мы ожидаем, что моделируемые классы квантовых цепей не будут универсальными для классических вычислений.

Сами групповые схемы Клиффорда особенно слабы и соответствуют классу сложности Parity-L, как было показано здесь .