Opérations quantiques du groupe Clifford et calcul classique

Le groupe Clifford d'opérateurs quantiques est généré par les opérations quantiques:

• Contrôlé-Z ,
• Hadamard et
• Phase ( ).$= |0\rangle\langle0| + i |1\rangle\langle1|$

Un circuit composé uniquement de ces portes peut être simulé efficacement sur un ordinateur classique. Cependant, si je comprends bien, tous les algorithmes classiques ne peuvent pas être mis en œuvre efficacement en utilisant les opérations du groupe Clifford, du moins pour autant que nous le sachions.

Existe-t-il une construction pour implémenter, même de manière inefficace ou approximative, un algorithme classique utilisant les opérations du groupe Clifford? Par exemple, comment implémentez-vous une porte Toffoli en utilisant des portes de groupe Clifford, si c'est possible?

Comme indiqué dans un commentaire ci-dessus, s'il était possible d'implémenter de manière cohérente une porte de Toffoli en utilisant des portes de groupe Clifford, alors le groupe Clifford serait universel pour le calcul quantique. Il a été noté dans la section 5 de cet article que quelque chose de plus fort est vrai: de manière informelle, s'il existe une classe de circuits quantiques qui peut être simulée efficacement de manière classique, et qui est universelle pour le calcul classique , alors BQP = BPP. Ainsi, nous nous attendrions à ce que les classes simulables de circuits quantiques ne soient pas universelles pour le calcul classique.

Les circuits du groupe Clifford eux-mêmes sont particulièrement faibles et correspondent à la classe de complexité Parity-L, comme cela a été montré ici .