Ograniczone rozkłady prawdopodobieństwa głębokości

Dwa powiązane pytania dotyczące obliczeń na ograniczonej głębokości:

1) Załóżmy, że zaczynasz od n bitów i na początku bitu i może wynosić 0 lub 1 z pewnym prawdopodobieństwem p (i), niezależnie. (Jeśli upraszcza to problem, możemy założyć, że wszystkie p (i) s wynoszą 0,1 lub 1/2.a nawet że wszystkie mają 1/2.)

Teraz wykonujesz ograniczoną liczbę rund obliczeniowych. W każdej rundzie stosujesz odwracalne klasyczne bramki na rozłącznych zestawach bitów. (Napraw swój ulubiony zestaw uniwersalnych klasycznych bram dwustronnych.)

Na koniec otrzymujesz rozkład prawdopodobieństwa dla ciągów na n bitach. Czy istnieją wyniki dotyczące ograniczenia takich dystrybucji?

Szukam czegoś analogicznego do lematu przełączającego Hastada, wynik Boppany, że całkowity wpływ jest niewielki lub twierdzenie LMN.

2) To samo pytanie co 1), ale z obwodami kwantowymi o ograniczonej głębokości.

Istnieje kilka stosunkowo niedawnych prac Emanuele Viola i in., Które dotyczą złożoności rozkładów próbkowania. Koncentrują się na ograniczonym modelu obliczeń, takim jak drzewa decyzyjne z ograniczoną głębokością lub obwody z ograniczoną głębokością.

Niestety nie omawiają odwracalnych bram. Przeciwnie, często dochodzi do utraty długości wyjściowej. Niemniej jednak dokumenty te mogą być dobrym punktem wyjścia.

Obwody o ograniczonej głębokości nie mogą próbkować dobrych kodów

Złożoność dystrybucji

Krótka odpowiedź.

Dla układów kwantowych, istnieje co najmniej jeden non wynik -limitation: dowolne układy kwantowe ograniczony-głębokości są mało prawdopodobne, aby być simulatable z małym multiplikatywnego błędu prawdopodobieństwa wyniku, nawet dla wielomianu -depth klasycznych obwodów.

To oczywiście nie mówi ci, jakie ograniczenia rzeczywiście będą miały obwody ; szczególnie jeśli interesują Cię problemy decyzyjne z ograniczonym błędem, a nie rozkłady prawdopodobieństwa. Oznacza to jednak, że analiza pod kątem drzew decyzyjnych, podobnie jak w przypadku Switching Lemma Håstad , prawdopodobnie nie będzie dostępna w przypadku klasycznej symulacji tych obwodów.$\mathsf{QNC^0}$

Detale

Możemy rozważyć definicję obwodów kwantowych o głębokości polilogu podaną przez Fennera i in. (2005) :

Definicja. jest klasą rodzin obwodów kwantowych { C n } n ⩾ 0, dla której istnieje wielomian p, dla którego każdy C n zawiera n kubitów wejściowych i co najwyżej p ( n ) świeżych ancillas, używa tylko bramek pojedynczych kubitów i kontrolowane bramy, a nie głębokość O ( log k ( n ) ) .$\mathsf{QNC^k}$$\{C_n\}_{n\geqslant0}$$p$$C_n$$n$$p(n)$$O(\log^k(n))$

Bramy pojedynczych kubitów muszą pochodzić z ustalonego zbioru skończonego, ale wystarcza to do symulacji dowolnego ustalonego elementu na stałej liczbie kubitów z dowolną ustaloną dokładnością. Umożliwiamy również użycie dowolnego podzbioru kubitów na końcu obwodu do reprezentowania wyjścia rodziny obwodów (np. Pojedynczego kubita dla funkcji boolowskich).

Bremner, Jozsa i Sheppard (2010) zauważają (zob. Sekcja 4), że wykorzystując adaptację techniki teleportacji bramkowej ze względu na Terhala i DiVincenzo (2004) , dokonano selekcji wstępnej niektórych kubitów w obwodzie umożliwia to podjęcie decyzji problemy p o s t B P P = P P . Wykorzystując ich wyniki do symulacji wybranych obwodów, oznacza to, że problem klasycznego próbkowania z rozkładu wyjściowego dowolnego Q N C $\mathsf{QNC^0}$$\mathsf{PostBQP = PP}$$\mathsf{QNC^0}$ obwodu z wyjściem logicznym, z błędem multiplikatywnym co najwyżej w prawdopodobieństwa próbkowania, jest niemożliwe przypadkowe wielomianowych obwodów głębokości chyba że wielomian hierarchia częściowo rozpada (w szczególnościpH⊆Æ3).$\sqrt 2$$\mathsf{PH} \subseteq \Delta_3$