Operações quânticas do grupo Clifford e computação clássica

12

O grupo Clifford de operadores quânticos é gerado pelas operações quânticas:

  • Z controlado ,
  • Hadamard , e
  • Fase ( ).=|00|+i|11|

Um circuito composto apenas por esses portões pode ser simulado com eficiência em um computador clássico. No entanto, se eu entendi corretamente, nem todos os algoritmos clássicos podem ser implementados com eficiência usando as operações do grupo Clifford, pelo menos até onde sabemos.

Existe uma construção para implementar, mesmo de maneira ineficiente ou aproximada, um algoritmo clássico usando operações do grupo Clifford? Por exemplo, como você implementa um portão de Toffoli usando os portões do grupo Clifford, se é possível?

Antonio Valério Miceli-Barone
fonte
2
O portão quântico de Toffoli é universal para computação quântica, enquanto os portões do grupo Clifford não são universais.
Mohammad Al-Turkistany
2
No meu entendimento, o portão de Toffoli por si só não é universal para a computação quântica eficiente, uma vez que leva estados de base computacional para outros estados de base computacional.
Antonio Valerio Miceli-Barone
2
Grupo Toffoli + Clifford é universal para computação quântica eficiente, se eu entendi corretamente
Antonio Valerio Miceli-Barone

Respostas:

22

Como apontado em um comentário acima, se fosse possível implementar coerentemente um portão de Toffoli usando os portões do grupo Clifford, então o grupo Clifford seria universal para o cálculo quântico. Observou-se na Seção 5 deste artigo que algo ainda mais forte é verdadeiro: informalmente, se existe uma classe de circuitos quânticos que podem ser simulados de maneira eficiente e clássica, e que é universal para a computação clássica , então BQP = BPP. Assim, esperaríamos que classes simuláveis ​​de circuitos quânticos não fossem universais para o cálculo clássico.

Os circuitos do grupo Clifford são particularmente fracos e correspondem à classe de complexidade Parity-L, como foi mostrado aqui .

Ashley Montanaro
fonte
Obrigado pelas referências. Agora que você mencionou, pareço lembrar que Nielsen & Chuang descrevem uma construção do grupo Toffoli + Clifford que é universal para computação quântica (não posso acessar o livro no momento).
Antonio Valerio Miceli-Barone
4
De fato, apenas ter portões de Toffoli e Hadamard é suficiente (veja o artigo quant-ph / 0301040, por exemplo).
Ashley Montanaro
Por favor, considere entrar em: quantumcomputing.stackexchange.com .
Rob