Operasi kuantum grup Clifford dan perhitungan klasik

The Clifford kelompok dari operator kuantum yang dihasilkan oleh operasi kuantum:

• Terkendali-Z ,
• Hadamard , dan
• Tahap ( ).$= |0\rangle\langle0| + i |1\rangle\langle1|$

Sirkuit yang hanya terdiri dari gerbang-gerbang ini dapat disimulasikan secara efisien pada komputer klasik. Namun, jika saya mengerti dengan benar, tidak semua algoritma klasik dapat diimplementasikan secara efisien menggunakan operasi grup Clifford, setidaknya sejauh yang kita tahu.

Apakah ada konstruksi untuk mengimplementasikan, bahkan tidak efisien atau kira-kira, algoritma klasik menggunakan operasi grup Clifford? Misalnya, bagaimana Anda menerapkan gerbang Toffoli menggunakan gerbang grup Clifford, jika memungkinkan?

Seperti yang ditunjukkan dalam komentar di atas, jika mungkin untuk mengimplementasikan gerbang Toffoli secara koheren menggunakan gerbang grup Clifford, maka grup Clifford akan bersifat universal untuk perhitungan kuantum. Telah dicatat dalam Bagian 5 dari makalah ini bahwa sesuatu yang lebih kuat adalah benar: berbicara secara informal, jika ada kelas sirkuit kuantum yang dapat disimulasikan secara efisien secara klasik, dan yang universal untuk perhitungan klasik , maka BQP = BPP. Dengan demikian kita harapkan kelas simulable dari sirkuit kuantum tidak universal untuk komputasi klasik.

Sirkuit grup Clifford sendiri sangat lemah, dan sesuai dengan kelas kompleksitas Parity-L, seperti yang ditunjukkan di sini .