Teorema de Gottesman-Knill

En computació quàntica, el teorema de Gottesman – Knill és un resultat teòric de Daniel Gottesman i Emanuel Knill que estableix que els circuits estabilitzadors – circuits que només consisteixen en portes del normalitzador del grup qubit de Pauli, també anomenat grup de Clifford – es poden simular perfectament en temps polinomial en un ordinador probabilístic clàssic. El grup Clifford es pot generar únicament utilitzant les portes controlades NOT, Hadamard i fase (CNOT, H i S); i, per tant, els circuits estabilitzadors es poden construir utilitzant només aquestes portes.

El motiu de l'acceleració dels ordinadors quàntics en comparació amb els clàssics encara no s'entén del tot. El teorema de Gottesman-Knill demostra que tots els algorismes quàntics l'acceleració dels quals es basa en l'entrellat que es pot aconseguir amb les portes CNOT i Hadamard no aconsegueixen cap avantatge computacional relatiu als ordinadors clàssics, a causa de la simulabilitat clàssica d'aquests algorismes (i dels tipus particulars d'entrellaçat). estats que poden produir).

Des de la declaració inicial del teorema, s'han identificat construccions més eficients per simular aquests circuits estabilitzadors (Clifford) amb una implementació.

El teorema de Gottesman – Knill es va publicar en un article d'un sol autor de Gottesman, en el qual atribueix a Knill el resultat, mitjançant comunicació privada.

Declaració formal

Teorema: un circuit quàntic que utilitza només els elements següents es pot simular de manera eficient en un ordinador clàssic:

1. Preparació de qubits en estats de base computacional.
2. Portes Clifford (generades per la porta Hadamard, la porta NO controlada i la porta de fase S).
3. Mesures en la base computacional.

El teorema de Gottesman – Knill mostra que fins i tot alguns estats molt entrellaçats es poden simular de manera eficient en un ordinador clàssic. Diversos tipus importants d'algoritmes quàntics utilitzen només portes de Clifford, inclosos els algorismes estàndard per a la destil·lació d'entrellaçament i la correcció d'errors quàntics. Des d'un punt de vista pràctic, els circuits estabilitzadors en n qubits es poden simular en temps O(n log n) utilitzant el formalisme d'estat gràfic.