Modele obliczeń ściśle między klasycznym a kwantowym pod względem złożoności zapytań

18

Powszechnie wiadomo, że komputery kwantowe są silniejsze niż ich klasyczne odpowiedniki pod względem złożoności zapytań .

Czy istnieją inne modele (naturalne lub sztuczne), które są ściśle kwantowe i klasyczne pod względem złożoności zapytań?

Separacja może być włączona

  • specyficzne problemy: model X oblicza funkcję ze znacznie większą liczbą zapytań niż kwantowe, ale mniej zapytań niż dolna granica klasycznego, lubf
  • inne problemy: model X oblicza funkcję przy znacznie większej liczbie zapytań niż kwant, ale oblicza funkcję f 2 przy mniejszej liczbie zapytań niż klasyczna.f1f2

W obu przypadkach chcemy, aby każda funkcja miała Q 2 ( f ) ≤ X ( f ) ≤ R 2 ( f ), aby uniknąć przykładów trudnych do porównania z kwantowymi (np. Złożoność certyfikatu zapytań niedeterministycznych). Tutaj P 2 ( f ) (i R 2 ( f ) ), jest obustronnie 1 / 3 -error kwantowe (i klasyczną randomizowane) złożoność zapytania i nierówności są w stałych czynników.fQ2(f)≤X(f)≤R2(f)Q2(f)R2(f)1/3

cc.complexity-theory quantum-computing query-complexity Artem Kaznatcheev
źródło

Odpowiedzi:

8

Jednym z łatwych sposobów wymyślenia takiego modelu jest najpierw stworzenie ograniczonego modelu obliczeń kwantowych, który nadal może zrobić coś nieklasycznego, a następnie po prostu nadanie mu klasycznego obliczenia za darmo.

Przykładem tej strategii jest jeden czysty model kubitowy (wraz z maszyną BPP). Kilka odniesień: Na mocy jednego bitu informacji kwantowej , obliczenia z jednostkami i jednym czystym Qubitem i oszacowaniem wielomianów Jonesa jest kompletnym problemem dla jednego czystego kubita .

Innym przykładem może być obwód kwantowy (lub głębokość polilogu) z dostępem do klasycznego komputera. Da to coś podobnego .bP.P.bQN.do

Robin Kothari
źródło
To z pewnością działa na złożoność obliczeniową, ale czy działa na złożoność zapytań? Nie widzę od razu żadnego problemu, dla którego jeden czysty model qubit + BPP zapewnia lepszą złożoność zapytań niż klasyczna maszyna. Ogólnie rzecz biorąc, technika ta może się nie powieść, ponieważ klasyczne obliczenia grupy Clifforda lub bramki meczowej zwiększają je do uniwersalnego obliczenia kwantowego.
Joe Fitzsimons,
@JoeFitzsimons: Nie mogę wymyślić żadnego problemu z góry mojej głowy, ale myślę, że Dan Shepherd pokazuje w wyrobie separację wyroczni między BPP a jedynym czystym modelem kubitowym. Twój drugi punkt jest oczywiście ważny.
Robin Kothari,
Ale z pewnością separacja wyroczni niekoniecznie oznacza separację złożoności zapytań.
Joe Fitzsimons,
Zgadzam się z @JoeFitzsimons, chociaż model DQC1 jest interesujący, nie widziałem dla niego separacji złożoności zapytań. Naturalne problemy, takie jak szacowanie śladu lub wariant wielomianu Jonesa autorstwa Shora, wydają się trudne do przedstawienia w modelu zapytania.
Artem Kaznatcheev
7

X(fa)≤re(fa)R2)(fa)

Joe Fitzsimons
źródło
2
P.⊕L.P.L.
2

Być może bardziej wyraźnym przykładem tego rodzaju modeli obliczeniowych jest DQC1 wyjaśniony przez @RobinKothari w jego odpowiedzi. Zobacz odniesienia w jego odpowiedzi na dobre wprowadzenie do modelu.

Niedawno w magazynie Nature pojawił się fajny artykuł na temat Quantum Discord. Niezgoda kwantowa to teoretyczna miara nieklasycznych korelacji, uogólniająca splątanie. Oto link . Zobaczysz tam, że istnieją przykłady obliczeń, w których splątanie nie odgrywa fundamentalnej roli, tj. Inne nieklasyczne korelacje to te, które dbają o przyspieszenie obliczeń. Dzieje się tak w DQC1 do obliczania śladu macierzy (patrz artykuł Datty, Shaji i Cavesa ). Interesujące w tym artykule jest to, że otwiera pytanie dotyczące „algorytmów opartych na dyskach kwantowych”, tj. Algorytmów, w których nie potrzebujesz splątania dla przyspieszenia kwantowego. Jest to coś pomiędzy pełnym obliczeniem kwantowym a klasycznym.

Innym modelem, który może należeć do tej kategorii (między pełnym kwantowym a klasycznym) jest Liniowy Model Optyczny autorstwa Arkhipova i Aaronsona. Zobacz to pytanie, aby uzyskać ładne wyjaśnienie.

Nie wiem, gdzie te modele pasują pod względem złożoności zapytań, ale może to być dobry punkt wyjścia.

Marcos Villagra
źródło