Operacje kwantowe grupy Clifforda i klasyczne obliczenia

Grupa Clifford operatorów kwantowej są generowane przez operacje kwantowej:

• Controlled-Z ,
• Hadamard i
• Faza ( ).$= |0\rangle\langle0| + i |1\rangle\langle1|$

Obwód złożony tylko z tych bram może być skutecznie symulowany na klasycznym komputerze. Jednak, jeśli dobrze rozumiem, nie wszystkie klasyczne algorytmy mogą być skutecznie wdrożone przy użyciu operacji grupowych Clifford, przynajmniej o ile nam wiadomo.

Czy istnieje konstrukcja do wdrożenia, nawet nieefektywnie lub w przybliżeniu, klasycznego algorytmu wykorzystującego operacje grupy Clifford? Na przykład, jak wdrożyć bramę Toffoli za pomocą bram grupy Clifford, jeśli to możliwe?

Jak wskazano w komentarzu powyżej, gdyby możliwe było spójne wdrożenie bramki Toffoli za pomocą bramek grupy Clifford, grupa Clifford byłaby uniwersalna do obliczeń kwantowych. W części 5 tego dokumentu zauważono, że coś jeszcze silniejszego jest prawdą: nieoficjalnie, jeśli istnieje klasa obwodów kwantowych, które można skutecznie symulować klasycznie i która jest uniwersalna dla obliczeń klasycznych , to BQP = BPP. Zatem spodziewalibyśmy się, że symulowalne klasy obwodów kwantowych nie będą uniwersalne dla klasycznych obliczeń.

Same obwody grupy Clifford są szczególnie słabe i odpowiadają klasie złożoności Parity-L, jak pokazano tutaj .