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.

— Gil Kalai
źródło

I może być czegoś brakuje, ale nie jest pytanie 1 z wszystkich

p (i)

$p(i)$ równa się

1 / 2

$1/2$ banalne? Zaczynasz od równomiernego rozkładu na

{0, 1}^{n}

$\{0,1\}^n$ , który jest niezmienny w przypadku wstrzyknięć.

— Klaus Draeger

Czy następujące pożyteczne przekształcenie problemu? Przekształć dane wejściowe (wektor

p_{0}, p_{1}, \dots

$p_0,p_1,\dots$ ) w wektor o długości

2^{n}

$2^n$ reprezentujący rozkład prawdopodobieństwa na ciągach binarnych o długości

n

$n$ . Teraz każde obliczenie jest kwadratową macierzą stochastyczną działającą na (powiedzmy) po lewej stronie, aby uzyskać rozkład prawdopodobieństwa na ciągi wyjściowe o długości

n

$n$ . WLOG możemy przypuszczać, że wszystkie wpisy są binarne. Jedynym pytaniem jest, jaka jest klasa stochastycznych macierzy binarnych, które można wytworzyć przez ograniczoną liczbę mnożenia macierzy naszych macierzy podstawowych (bramek odwracalnych).

— usul

Przepraszam, powinienem być bardziej precyzyjny. Przez matrycę podstawową rozumiem tu nie bramę odwracalną, ale raczej pewien zestaw odwracalnych bram działających równolegle i nie wydaje mi się od razu oczywiste, jak takie matryce wyglądałyby przy danym zestawie bram.

— usul

Obie odpowiedzi zasługują na nagrodę, zobaczę, co da się zrobić

— Gil Kalai,

co rozumiesz przez „rozłączne zestawy” bitów?

— vzn 12.12.12

Odpowiedzi:

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

— MassimoLauria
źródło

Wielkie dzięki, Massimo! to wygląda bardzo trafnie.

— Gil Kalai

(Równie interesuje mnie przypadek nieodwracalny.)

— Gil Kalai,

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 dla której istnieje wielomian dla którego każdy zawiera kubitów wejściowych i co najwyżej świeżych ancillas, używa tylko bramek pojedynczych kubitów i kontrolowane bramy, a nie głębokość . $\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 . Wykorzystując ich wyniki do symulacji wybranych obwodów, oznacza to, że problem klasycznego próbkowania z rozkładu wyjściowego dowolnego $\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ści). $\sqrt 2$ $\mathsf{PH} \subseteq \Delta_3$

— Niel de Beaudrap
źródło

Drogi Niel, bardzo interesujące! Dzięki! Szczególnie interesują mnie dystrybucje. Czy możesz wyjaśnić, dlaczego „To oczywiście nie mówi ci ...”?

— Gil Kalai

Wynik stałości współczynnika niedopuszczalności utrzymuje się przez PostQNC⁰ = PostBQP = PP . Stosuje się tutaj postselekcję, aby „wymusić sukces” długiego ciągu teleportacji, symulować rozkład kwantowo-poli-głębokości poprzez rozkład kwantowo-stałej głębokości uwarunkowany zdarzeniem o ekstremalnie niskim, ale niezerowym prawdopodobieństwie. Jakikolwiek stały współczynnik aproksymacji byłby równie dobry dla obwodu o wielkiej głębokości. Ale to nie mówi ci, np. Górnej granicy, o ile amplituda, w kategoriach bezwzględnych (i asymptotycznych), jest skoncentrowana (lub może być rzutowana na) jakąkolwiek określoną podprzestrzeń.

— Niel de Beaudrap,