W jaki sposób aproksymacja bramek za pomocą bram uniwersalnych skaluje się z długością obliczeń?

Rozumiem, że istnieje konstruktywny dowód, że dowolne bramy można aproksymować skończonym uniwersalnym zestawem bram, którym jest Twierdzenie Solovaya – Kitaeva .
Jednak przybliżenie wprowadza błąd, który rozprzestrzenia się i kumuluje w długim obliczeniu. Prawdopodobnie byłoby to źle skalowane przy długości obliczeń? Być może można zastosować algorytm aproksymacyjny do całego obwodu jako całości, a nie do pojedynczej bramki. Ale w jaki sposób skaluje się to wraz z długością obliczeń (tj. W jaki sposób przybliżenie skaluje się z wymiarem bramek)? Jak przybliżenie bramki odnosi się do syntezy bramki? Ponieważ mogłem sobie wyobrazić, że wpływa to na końcową długość obliczeń?
Jeszcze bardziej niepokojące dla mnie: co się stanie, jeśli długość obliczeń nie będzie znana w momencie kompilacji sekwencji bramek?

— M. Sterna
źródło

$A$ $\left\lVert A\right\rVert$ $A$ $A$ $\epsilon$

O (\log^{c} \frac{1}{ϵ})

$\mathcal O\left(\log^c\frac 1\epsilon\right)$

c < 4

$c<4$

W pierwszej części:

przybliżenie wprowadza błąd, który rozprzestrzenia się i kumuluje w długim obliczeniu

Cóż, można to wykazać przez indukcję, że błędy kumulowane przez zastosowanie jednej macierzy do przybliżenia innej są subadditive (patrz np . Notatki z wykładu Andrew Childa ). To znaczy, dla macierzy jednostkowych i , . $U_i$ $V_i$ $\left\lVert U_i - V_i\right\rVert < \epsilon\,\forall\, i \in \left\lbrace1, 2, \ldots, t\right \rbrace\implies \left\lVert U_t\ldots U_2U_1 - V_t\ldots V_2V_1\right\rVert \leq t\epsilon$

Oznacza to, że pod względem implementacji, aby ogólny błąd nie został osiągnięty więcej niż , każda bramka musi być przybliżona do lub $\epsilon$ $\epsilon/t$

zastosowanie aproksymacji do obwodu jako całości

to to samo, co zastosowanie przybliżenia do każdej pojedynczej bramki, każda z indywidualnym błędem nie większym niż błąd całego obwodu podzielony przez liczbę bramek, które przybliżasz.

Jeśli chodzi o syntezę bramek, algorytm jest wykonywany przez przyjęcie produktów zestawu bramek celu utworzenia nowego zestawu bramek który tworzy sieć dla (dla dowolny ). Zaczynając od tożsamości, rekurencyjnie znajduje się nowy unitarny z nowego zestawu bram, aby uzyskać mocniejszą siatkę wokół docelowego unitarnego. Co dziwne, czas na wykonanie klasycznego algorytmu przez tę operację to także , czyli czas sub-wielomianowy. Jednak zgodnie z $\Gamma$ $\Gamma_0$ $\epsilon^2$ $\operatorname{SU}\left(d\right)$ $A \in \operatorname{SU}\left(d\right),\, \exists U\in\Gamma_0\, s.t. \left\lVert A-U\right\rVert\leq\epsilon^2$ $\mathcal O\left(\mathit{poly} \log 1/\epsilon\right)$ Harrow, Recht, Chuang , w wymiarach , ponieważ kula o promieniu wokół nazwa ma objętość , to skaluje się wykładniczo in dla nieokreślonej liczby wymiarów. $d$ $\epsilon$ $\operatorname{SU}\left(d\right)$ $\propto \epsilon^{d^2-1}$ $d^2$

Ma to wpływ na końcowy czas obliczeń. Ponieważ jednak skalowanie zarówno liczby bramek, jak i klasycznej złożoności obliczeniowej jest sub-wielomianowe, nie zmienia to klasy złożoności żadnego algorytmu, przynajmniej dla klas powszechnie uważanych.

Na bramy, ogólny (czasowych i bramka) złożony jest więc $t$ .

O (t p o l y \log \frac{t}{ϵ})

$\mathcal O\left(t\, \mathit{poly} \log \frac t\epsilon\right)$

W przypadku korzystania z modelu obwodu jednolitego bez pomiarów pośrednich liczba bramek, które należy wdrożyć, zawsze będzie znana przed obliczeniem. Można jednak założyć, że nie jest tak w przypadku pomiarów pośrednich, więc kiedy liczba bramek, które chcesz przybliżyć, jest nieznana, oznacza to, że jest nieznane. a jeśli nie wiesz, co to jest , oczywiście nie możesz przybliżyć każdej bramki do błędu . Jeśli znasz ograniczenie liczby bramek (powiedzmy, ), możesz zbliżyć każdą bramkę do aby uzyskać ogólny błąd $t$ $t$ $\epsilon/t$ $t_{\text{max}}$ $\epsilon/t_{\text{max}}$ $\leq\epsilon$ i złożoność chociaż jeśli nie ma górnej granicy liczby bram jest znany , wówczas każda brama byłaby zbliżona do niektórych (mniejszych) , dając ogólny błąd dla wynikowej liczby zaimplementowanych bramek (co jest nieznane na początku) , z ogólna złożoność

O (t p o l y \log \frac{t_{max}}{ϵ}),

$\mathcal O\left(t\, \mathit{poly} \log \frac {t_{\text{max}}}{\epsilon}\right),$

ϵ^{'}

$\epsilon'$

\leq t^{'} ϵ

$\leq t'\epsilon$

t^{'}

$t'$

O (t^{'} p o l y \log \frac{1}{ϵ^{'}}) .

$\mathcal O\left(t'\, \mathit{poly} \log \frac {1}{\epsilon'}\right).$

Oczywiście całkowity błąd tego jest nadal nieograniczony, więc jednym prostym ¹ sposobem na ograniczenie tego błędu byłoby zmniejszenie błędu za każdym razem o, powiedzmy, , tak aby bramka była zaimplementowano z błędem . Złożoność byłaby wtedy co daje ogólną (teraz wielomianową) złożoność chociaż ma to tę zaletę, że gwarantuje ograniczenie błędu. $2$ $n^{th}$ $\epsilon/2^n$

O (p o l y \log \frac{2^{n}}{ϵ^{'}}) = O (p o l y n \log \frac{1}{ϵ^{'}}),

$\mathcal O\left(\mathit{poly} \log \frac {2^n}{\epsilon'}\right) = \mathcal O\left(\mathit{poly}\, n\log \frac {1}{\epsilon'}\right),$

O (p o l y t \log \frac{1}{ϵ}),

$\mathcal O\left(\mathit{poly}\, t \log \frac {1}{\epsilon}\right),$

To nie jest zbyt złe, więc mam nadzieję, że (gdy liczba bramek jest nieznany) komputery klasyczne byłby w stanie utrzymać wymyślanie odpowiednich bramek co najmniej tak szybko jak procesor kwantowy będzie ich potrzebować. Jeśli nie obecnie, to mam nadzieję, że gdy procesory kwantowe staną się wystarczająco dobre, że stanie się to problemem!

^{1 Chociaż prawdopodobnie nie jest najbardziej wydajny}

— Mithrandir24601
źródło