Jak potężne są obliczenia „kwantowe”, jeśli zawiesisz jednolitość?

Krótkie pytanie

Jaka jest moc obliczeniowa obwodów „kwantowych”, jeśli pozwolimy na niejednorodne (ale wciąż odwracalne) bramki i wymagamy, aby dane wyjściowe dawały prawidłową odpowiedź z pewnością?

To pytanie w pewnym sensie dotyczy tego, co dzieje się z klasą kiedy pozwalasz obwodom na korzystanie z więcej niż tylko jednolitych bram. (Wciąż jesteśmy zmuszeni ograniczyć się do odwracalnych bramek powyżej C, jeśli chcemy mieć dobrze zdefiniowany model obliczeń.)$\mathsf{EQP}$$\mathbb C$

(To pytanie zostało zmienione w świetle pewnych nieporozumień z mojej strony dotyczących znanych wyników dotyczących takich obwodów w przypadku jednolitym.)

O „dokładnym” obliczeniu kwantowym

Dla tego pytania definiuję jako klasę problemów, które można dokładnie rozwiązać przez jednorodną rodzinę obwodów kwantowych, w której współczynniki każdej jednostki są obliczalne przez wielomianowe maszyny Turinga ograniczone czasowo (z ciągu wejściowego 1 n ) dla każdego rozmiaru wejściowego n oraz że układ obwodu jako sieci kierowanej może być również wytwarzany w czasie wielomianowym. Przez „dokładnie” rozwiązany, mam na myśli, że pomiar bitu wyjściowego daje | 0 ⟩ z pewnością dla instancji nie, i | 1 ⟩ z pewnością dla przypadkach tak.$\mathsf{EQP}$$1^n$$n$$|0\rangle$$|1\rangle$

Ostrzeżenia:

• Nawet ograniczając się do bram jednostkowych, to pojęcie różni się od opisu opisanego przez Bernsteina i Vazirani przy użyciu kwantowych maszyn Turinga. Powyższa definicja pozwala rodzinie obwodów { C n } zasadniczo mieć nieskończony zestaw bramek - każdy pojedynczy obwód C n używa oczywiście tylko skończonego podzbioru - ponieważ bramki są w rzeczywistości obliczane z danych wejściowych. (Kwantowa maszyna Turinga może symulować dowolny zestaw skończonych bram, ale może symulować tylko zestawy skończonych bram, ponieważ ma tylko skończoną liczbę przejść).$\mathsf{EQP}$$\{ C_n \}$$C_n$

• Ten model obliczeń trywializuje wszelkie problemy w , ponieważ jednostka unitarna może zawierać pojedynczą bramkę, która koduje na stałe rozwiązanie dowolnego problemu w P (jego współczynniki są przecież określane przez obliczenia wielogodzinne). Tak więc specyficzna złożoność problemów w czasie lub przestrzeni niekoniecznie jest interesująca dla takich obwodów.$\mathsf P$$\mathsf P$

Do tych zastrzeżeń możemy dodać spostrzeżenie, że praktyczne implementacje komputerów kwantowych i tak będą generować hałas. Ten model obliczenia jest interesujące przede wszystkim ze względów teoretycznych , dotyczy tak tworzenia jednolitych przekształceń zamiast jednego możliwego obliczeń, a także dokładnego wersji . W szczególności, mimo powyższych zastrzeżeń, mamy P ⊆ E Q P ⊆ B Q P .$\mathsf{BQP}$$\mathsf{P} \subseteq \mathsf{EQP} \subseteq \mathsf{BQP}$

Powodem definiowania w drodze robię to tak, że dyskretnych LOG mogą być wprowadzane do E Q P . W [  Mosca + Zalka 2003  ] istnieje algorytm wielomianowy do budowy obwodu jednostkowego, który dokładnie rozwiązuje przypadki DISCRETE-LOG poprzez tworzenie dokładnych wersji QFT w zależności od modułu wejściowego. Wierzę, że możemy następnie wprowadzić DISCRETE-LOG do E Q P , jak zdefiniowano powyżej, poprzez osadzenie elementów konstrukcji obwodu w sposób, w jaki obliczane są współczynniki bramki. (Tak więc wynik DISCRETE-LOG ∈ E Q P zasadniczo trzyma się fiat, ale opiera się na konstrukcji Mosca + Zalka.)$\mathsf{EQP}$$\mathsf{EQP}$$\mathsf{EQP}$$\in \mathsf{EQP}$

Zawieszenie jednolitości

Niech będzie klasą obliczeniową, którą otrzymamy, jeśli zawiesimy ograniczenie, że bramki są jednolite, i pozwolimy, by obejmowały one ponad odwracalne transformacje. Czy możemy umieścić tę klasę (lub nawet ją scharakteryzować) w kategoriach innych tradycyjnych niedeterministycznych klas C ?$\mathsf{EQP_{\mathrm{GL}}}$$\mathbf C$

Jednym z moich powodów do pytania: czy jest klasą problemów, które można skutecznie rozwiązać z ograniczonym błędem , przez jednolite rodziny obwodów „niejednolitych” - gdzie instancje TAK dają wynik | 1 ⟩ z prawdopodobieństwem co najmniej 2/3, a nie z prawdopodobieństwem wystąpienia co najwyżej 1/3 (po normalizacji wektor stanu) - następnie [Aaronson 2005] wskazuje, że B P P G L = P P . To znaczy: zawieszenie jednolitości jest w tym przypadku równoważne zezwalaniem na nieograniczony błąd.$\mathsf{BQP}_{\mathrm{GL}}$$|1\rangle$$\mathsf{BQP}_{\mathrm{GL}} = \mathsf{PP}$

Czy podobny wynik lub jakikolwiek wyraźny wynik uzyskuje się dla ?$\mathsf{EQP_{\mathrm{GL}}}$

Krótka odpowiedź. Okazuje się, że zawieszenie wymogu przekształceń jednostkowych i wymaganie, aby każda operacja była odwracalna, powoduje powstanie dokładnych klas definiowanych przez odstęp. Specyficzne klasy są wykorzystywane, i 'nowy' podklasy L P W P P , które to siedzenia między S P P i C = P . Klasy te mają dość techniczne definicje, które zostały krótko opisane poniżej; chociaż te definicje można teraz zasadniczo zastąpić definicjami w kategoriach niejednolitych algorytmów „podobnych do kwantowych”.$\mathsf{LWPP}$$\mathsf{LPWPP}$$\mathsf{SPP}$$\mathsf{C_=P}$

Klasa liczenia zawiera GRAPH ISOMORPHISM. Zawiera także całą klasę U P , więc nie spodziewalibyśmy się, że dokładne jednostkowe algorytmy kwantowe będą tak potężne jak klasy niejednorodne (jak moglibyśmy w przeciwnym razie pokazać N P ⊆ B Q P ).$\mathsf{SPP}$$\mathsf{UP}$$\mathsf{NP \subseteq BQP}$

Dłuższa odpowiedź.

• W moim pytaniu zaproponowałem przedefiniowanie aby uwzględnić problemy rozwiązywane przez rodziny jednorodnych obwodów, które używają bramek, które są wydajnie obliczalne, ale niekoniecznie pochodzą z skończonego zestawu bramek. Nie jestem już tak pewien, czy dobrym pomysłem jest przedefiniowanie E Q P w ten sposób, chociaż uważam, że takie rodziny obwodów są warte nauki. Zamiast tego możemy nazwać tę klasę czymś w rodzaju U n i t a r y P $\mathsf{EQP}$ $\mathsf{EQP}$$\mathsf{UnitaryP_{\mathbb C}}$

  Możliwe jest, aby wykazać, że , które do niedawna najlepszy znany związany z E Q P . Klasa L W P P mniej więcej odpowiada problemom, dla których istnieje algorytm randomizowany, w którym instancje NIE dają wynik 1 z prawdopodobieństwem dokładnie 0,5, a instancje TAK dają wynik 1 z pewnym prawdopodobieństwem, które mogą być skutecznie i dokładnie obliczone w formie racjonalnej, która jest większa niż (ale być może wykładniczo bliska) 0,5. Definicja techniczna L W $\mathsf{UnitaryP_{\mathbb C} \subseteq LWPP}$$\mathsf{EQP}$$\mathsf{LWPP}$ jest przedstawiany w kategoriach niedeterministycznych maszyn Turinga, ale już nie jest pouczający.$\mathsf{LWPP}$

  Jeśli zdefiniujemy jako ekwiwalent odwracalnej bramki dla U n i t a r y P C , tak że jest to zestaw problemów, które są dokładnie rozwiązywalne przez rodziny obwodów odwracalnych o efektywnie obliczalnych współczynnikach bramki, wówczas G L P C = l W P P .$\mathsf{GLP}_{\mathbb C}$$\mathsf{UnitaryP_{\mathbb C}}$$\mathsf{GLP_{\mathbb C} = LWPP}$

• Jeśli to ograniczenie do zestawów ograniczonych bramy, możliwe jest wykazanie, że jednostkowe rodziny układu można symulować w podgrupie , który może nazywamy L P W P P . (Stosując powyższy opis L W P P , odpowiada to algorytmom losowym, w których prawdopodobieństwo uzyskania wyniku 1 dla instancji YES wynosi dokładnie m t ( x ) / 2 p ( | x | ) , dla niektórych wielomianów p , niektóre liczba całkowita $\mathsf{LWPP}$$\mathsf{LPWPP}$$\mathsf{LWPP}$$m^{t(x)} / 2^{p(|x|)}$$p$$m$, i kilka wydajnie obliczalnych wielomianów .)$t$

  Jeśli określenie być równoważne odwracalna, brama E Q, P , jak to jest zwykle definiowany, możemy zobaczyć, że E P P G L ⊆ L P W P P .$\mathsf{EQP_{\mathrm{GL}}}$$\mathsf{EQP}$$\mathsf{EQP_{\mathrm{GL}} \subseteq LPWPP}$

Korekta dotycząca DYSKRETNEGO DZIENNIKA.

Powyższe wyniki opierają się na standardowych technikach reprezentowania współczynników algebraicznych w sposób niezależny od danych wejściowych (ale który może zależeć od wielkości danych wejściowych). W opisie pierwotnego pytania twierdziłem, że [ Mosca + Zalka 2003 ] pokazują, że DZIENNIK DYSKRETNY można dokładnie rozwiązać za pomocą zestawu bramek o efektywnie obliczalnych współczynnikach. Prawda wydaje się bardziej skomplikowana. Jeśli dba się o dokładną rozwiązywalność, uważam dokładne przedstawienie współczynników za ważne: ale Mosca i Zalka nie zapewniają sposobu na zrobienie tego w sposób zależny od wkładu. Nie jest więc oczywiste, że LOG DYSKRETNY faktycznie znajduje się w lub w nowej klasie U n i t a r y $\mathsf{EQP}$ .$\mathsf{UnitaryP_{\mathbb C}}$

Odniesienie.

• de Beaudrap, O dokładnym liczeniu i złożoności quasi-kwantowej , [ arXiv: 1509.07789 ].