Número de portões necessários para aproximar unidades arbitrárias

Se bem entendi, devem existir operações unitárias que possam ser aproximadas a uma distância apenas por um número exponencial de portas quânticas e não menos.$\epsilon$

No entanto, pelo teorema de Solovay-Kitaev, qualquer operação unitária arbitrária em qubits, com fixo, pode ser aproximada a uma distância de usando portas universais poli (log (1 / )).$n$$n$$\epsilon$$\epsilon$

Essas duas afirmações não parecem contraditórias? o que estou perdendo?

A escala completa será $O(4^n\text{poly}\left(\log\frac{1}{\epsilon}\right))$ , para que você realmente obtenha uma escala exponencial no número de qubits.

Observe que o teorema de Solovay-Kitaev vale para os unitários no qu $d$ it (seção 5 em DN05 ), então podemos definir $d=2^n$ para $n$ qubit unitário. Seguindo a mesma análise, obtemos

• comprimento de porta sequências $l_{\epsilon} = O(\ln^{\ln 5/\ln(3/2)} (1/\epsilon))$ ,
• tempo complexidade $t_{\epsilon} = O(\ln^{\ln 3/\ln(3/2)}(1/\epsilon))$ .

Agora a questão é o parâmetro de precisão $\epsilon$ . Como $SU(d)$ é o coletor de dimensões $(d^2-1)$ , de modo a aproximar cada porta em $SU(d)$ dentro de $\epsilon_0$ , geramos sequências $O(1/\epsilon_0^{d^2-1})$ .

Portanto, para qualquer conjunto universal específico de portas $\mathcal{G}$ o comprimento das seqüências de portas