Begrenzte Tiefenwahrscheinlichkeitsverteilungen

Zwei verwandte Fragen zum Bounded-Depth-Computing:

1) Angenommen, Sie beginnen mit n Bits, und um mit Bit i zu beginnen, können Sie mit einer gewissen Wahrscheinlichkeit p (i) unabhängig 0 oder 1 sein. (Wenn es das Problem einfacher macht, können wir annehmen, dass alle p (i) s 0,1 oder 1/2 sind.oder sogar, dass alle 1/2 sind.)

Jetzt machen Sie eine begrenzte Anzahl von Berechnungsrunden. In jeder Runde werden disjunkte Bitsätze mit reversiblen klassischen Toren versehen. (Fixieren Sie Ihr Lieblingsset an universellen klassischen Wendetoren.)

Am Ende erhalten Sie eine Wahrscheinlichkeitsverteilung auf Strings mit n Bits. Gibt es Ergebnisse zur Einschränkung solcher Distributionen?

Ich suche etwas analog zu Hastad Switching Lemme, Boppana Ergebnis, dass der Gesamteinfluss klein ist oder LMN-Theorem.

2) Dieselbe Frage wie 1), jedoch mit Quantenkreisen mit begrenzter Tiefe.

Es gibt einige relativ neue Arbeiten von Emanuele Viola et al., Die sich mit der Komplexität von Stichprobenverteilungen befassen. Sie konzentrieren sich auf eingeschränkte Berechnungsmodelle wie Entscheidungsbäume mit begrenzter Tiefe oder Schaltkreise mit begrenzter Tiefe.

Leider diskutieren sie keine reversiblen Tore. Im Gegenteil, es kommt häufig zu Verlusten bei der Ausgabelänge. Dennoch können diese Papiere ein guter Ausgangspunkt sein.

Bounded-Depth-Schaltkreise können keine guten Codes abtasten

Die Komplexität von Distributionen

Kurze Antwort.

Für Quantenschaltungen gibt es mindestens ein nicht einschränkendes Ergebnis: Es ist unwahrscheinlich, dass Quantenschaltungen mit beliebiger begrenzter Tiefe mit einem kleinen multiplikativen Fehler in der Wahrscheinlichkeit des Ergebnisses simuliert werden können, selbst für Polynome -depth klassischen Schaltungen.

Dies ist natürlich nicht sagen , was resctrictions Schaltungen tatsächlich haben; Insbesondere, wenn Sie an Entscheidungsproblemen mit begrenzten Fehlern und nicht an Wahrscheinlichkeitsverteilungen interessiert sind. Dies bedeutet jedoch, dass eine Analyse in Bezug auf Entscheidungsbäume, wie bei Håstad's Switching Lemma , für die klassische Simulation dieser Schaltungen wahrscheinlich nicht in Frage kommt.$\mathsf{QNC^0}$

Einzelheiten

Wir können die Definition von Polylog-Tiefen-Quantenschaltungen betrachten, wie sie von Fenner et al. (2005) :

Definition. ist die Klasse von Quantenschaltungsfamilien { C n } n ⩾ 0, für die ein Polynom p existiert, für das jedes C n n Eingangs-Qubits enthält und höchstens p ( n ) frische Ancillas, die nur Single-Qubit-Gatter verwenden und nichtgesteuerte Tore und hat die Tiefe O ( log k ( n ) ) .$\mathsf{QNC^k}$$\{C_n\}_{n\geqslant0}$$p$$C_n$$n$$p(n)$$O(\log^k(n))$

Die Single-Qubit-Gatter müssen aus einer festen endlichen Menge stammen, obwohl dies ausreicht, um eine feste Einheit auf einer konstanten Anzahl von Qubits mit einer festen Genauigkeit zu simulieren. Wir erlauben auch, dass eine beliebige Teilmenge der Qubits am Ende der Schaltung verwendet wird, um die Ausgabe der Schaltungsfamilie darzustellen (z. B. ein einzelnes Qubit für Boolesche Funktionen).

Bremner, Jozsa und Sheppard (2010) zur Kenntnis (siehe Abschnitt 4) , dass eine Anpassung der Gate-Teleportation Technik aufgrund Terhal und DiVincenzo (2004) , post-Auswahl auf einige der Qubits in einer - Schaltung macht es möglich, Probleme in P o s t B Q P = P P zu entscheiden . Unter Verwendung deren Ergebnisse auf postselected Schaltungen simuliert, bedeutet dies , dass das Problem der klassischen Probennahme aus der Ausgangsverteilung eines beliebigen Q N C 0 Schaltung mit booleschen Ausgang mit multiplikativen Fehler höchstens $\mathsf{QNC^0}$$\mathsf{PostBQP = PP}$$\mathsf{QNC^0}$ in der Abtastwahrscheinlichkeit ist mit zufälligen Polynomtiefenschaltungen unmöglich, es sei denn, die Polynomhierarchie kollabiert teilweise (speziellPH⊆Δ3).$\sqrt 2$$\mathsf{PH} \subseteq \Delta_3$