Um circuito quântico pode usar qualquer operador unitário. Sua matriz é exponencial no número de bits de entrada. Na prática, como isso pode ser possível (além de operadores que são produtos tensores), ou seja, como você pode construir uma matriz de tamanho exponencial?
A chave é que você realmente não constrói uma matriz. Sim, se você deseja simular uma computação quântica em um computador clássico, um método é construir a matriz unitária correspondente, e é por isso que (a menos que haja uma estrutura especial) é impossível executar com eficiência uma simulação clássica da computação quântica.
As operações quânticas básicas que usamos são pensadas dessa maneira - você realmente só faz algo com um ou dois qubits por vez e o torna exponencial adicionando identidades ("não faça nada") a todos os outros qubits. A combinação de um pequeno número destes atuando em diferentes conjuntos de qubits pode criar algumas matrizes unitárias que não são produtos tensores.
Agora, enquanto um computador quântico pode, em princípio, implementar qualquer operador unitário, a universalidade nesse sentido não diz nada sobre quanto tempo a construção leva. A grande, esmagadora, a maioria deles não ter tempo exponencial de implementar. A computação quântica está especificamente interessada em descobrir a zona Goldilocks, o pequeno número de instâncias que podem ser implementadas em tempo polinomial e fornecer uma computação interessante que não pode ser computada em tempo polinomial em um computador clássico.
Note que não há nada especificamente quântico nisso.
A dimensão dessas matrizes também aumenta claramente exponencialmente com o número de bits, mas isso não é um problema, pois não tem nenhuma conexão com o quão difícil é realmente implementar a operação correspondente, pelas razões expostas na outra resposta .