Jednokierunkowa weryfikacja kwantowa

Teoria obliczania stanu skupienia jest już dobrze ugruntowana, pokazując, że dowolny obwód BQP może być modyfikowany, więc używa tylko pojedynczych bramek kwantowych, ewentualnie sterowanych klasycznie, pod warunkiem wystarczającej podaży stanu zwanego „stanem skupienia” - który jest prostym w produkcji stanem stabilizatora.

Moje pytanie brzmi: czy podobne pojęcie jest znane z weryfikacji kwantowej - tj. Czy można zastąpić obwody QMA klasycznie sterowanymi bramkami 1-kubitowymi, ewentualnie używając jakiegoś „stanu specjalnego”? Przynajmniej na początku nie jestem pewien, dlaczego stan klastra może nawet działać w tym przypadku.

quantum-computing Lior Eldar
źródło

Jeśli dobrze rozumiem, czy problem, który w QMA Merlin daje ci kwantowy dowód, który musisz w jakiś sposób włączyć do modelu? Innymi słowy, jeśli byłaby to QCMA zamiast QMA, w której Merlin wręcza ci klasyczny ciąg, moglibyśmy po prostu użyć znanych wyników dla BQP, prawda?

Robin Kothari,

Tak, to jest poprawne. Dziękujemy za dokonanie tego rozróżnienia.

Lior Eldar

Na początek można zadać to samo pytanie dla BQP: Czy możemy wykonać jakiekolwiek obliczenia kwantowe, biorąc pod uwagę moc do wykonywania pomiarów 1-kubitowych i biorąc pod uwagę niezaufane stany skupień (lub inny odpowiedni stan)?

Norbert Schuch,

Odpowiedzi:

Możliwe jest ograniczenie weryfikatora QMA do pomiarów pojedynczych kubitów oraz klasycznego przetwarzania wstępnego i końcowego (z losowością) przy zachowaniu kompletności QMA.

Aby zobaczyć dlaczego, weź dowolną klasę lokalnych QMA-Hamiltonów na kubitach. Dodając stałą rzędu i przeskalowując za pomocą współczynnika , hamiltonian można doprowadzić do postaci gdzie , , i $k$ $\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$

H = \sum_{i} w_{i} h_{i},

$H=\sum_i w_i h_i\ ,$

w_{i} > 0

$w_i>0$

\sum_{i} w_{i} = 1

$\sum_i w_i=1$

, w którym

jest produktem Paulis. Szacowanie najmniejszej wartości własnej

do dokładności

jest nadal trudne QMA.

h_{i} = \frac{1}{2} (I d \pm P_{i})

$h_i = \tfrac12(\mathrm{Id}\pm P_i)$

P_{i}

$P_i$

H

$H$

1 / p o l y (n)

$1/\mathrm{poly}(n)$

Możemy teraz zbudować obwód, który wykorzystuje tylko pomiary pojedynczego kubita, które przy danym stanie , przyjmuje z prawdopodobieństwem (który konstrukcyjnie znajduje się pomiędzy i ). W tym celu najpierw losowo wybierz jedno z zgodnie z rozkładem . Następnie zmierzyć każdy z Paulis w , i podjąć parzystości z rezultatów, które jest obecnie związany $|\psi\rangle$ $1-\langle\psi|H|\psi\rangle$ $0$ $1$ $i$ $w_i$ $P_i$ $\pi$ $\langle\psi|h_i|\psi\rangle$ poprzez Układ generuje teraz, a wyjście jest zatem rozprowadzany zgodnie.

⟨ ψ | h_{i} | ψ ⟩ = \frac{1}{2} (1 \pm (- 1)^{π}) \in {0, 1} .

$\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .$

1 - ⟨ ψ | h_{i} | ψ ⟩

$1-\langle\psi|h_i|\psi\rangle$

⟨ ψ | H | ψ ⟩

$\langle\psi|H|\psi\rangle$

$|\psi\rangle$ $\ge a$ $\le b$ $a-b>1/\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$ luka. Wreszcie, ta wersja QMA może być wzmacniana przy użyciu zwykłych technik amplifikacji dla QMA, co ostatecznie dowodzi, że jest ona kompletna dla QMA niezależnie od odstępu (w tym samym zakresie co QMA).

Norbert Schuch
źródło

H

$H$

H^{'}

$H'$

ϵ = 1 / p o l y (n)

$\epsilon=1/\mathrm{poly}(n)$

H = x (H^{'} + y)

$H=x(H'+y)$

x = 1 / p o l y (n)

$x=1/\mathrm{poly}(n)$

y = p o l y (n)

$y=\mathrm{poly}(n)$

H

$H$

x ϵ = 1 / p o l y (n)

$x\epsilon=1/\mathrm{poly}(n)$

h_{i}

$h_i$

h^{'}

$h'$

4^{k}

$4^k$

4^{k} = p o l y (n)

$4^k=\mathrm{poly}(n)$

k = O (\log (n))

$k=O(\log(n))$

P_{i}

$P_i$

t r [P_{i} h^{'}] / 2^{k} \leq ‖ h^{'} ‖_{\infty}

$\mathrm{tr}[P_ih']/2^k\le \|h'\|_\infty$

Moją interpretacją pytania jest to, że zadajesz pytanie, czy możemy założyć, że obwód weryfikatora dla protokołu QMA wykorzystuje tylko pomiary pojedynczej kubity? (Idea polega na tym, że przysłowia wysyła zarówno dowód kwantowy, jak i stan klastra kwantowego potrzebne do wdrożenia oryginalnego obwodu weryfikacyjnego przez „jednokierunkowe obliczenia kwantowe”).

Problem polega oczywiście na tym, że przysłowia może wcale nie wysłać prawidłowego stanu klastra. Dlatego weryfikator musiałby przetestować otrzymany stan, aby upewnić się, że rzeczywiście jest to stan klastra. Weryfikator dokonuje tego, wykonując pomiary pojedynczych kubitów i sprawdzając korelacje spełniające niezbędne kontrole stabilizatora. Ponieważ takie testowanie jest destrukcyjne dla stanu, musiałaby istnieć procedura, w której weryfikator otrzyma wiele kopii stanu, sprawdzi większość z nich i użyje losowej do obliczeń. Czy wystarczy wielomianowo wiele kopii?

Nie sądzę, że jest to znane twierdzenie. Nie widzę oczywistego kontrprzykładu (z chwilą namysłu), więc może to być wiarygodne. Wydaje się, że sprawdzona technologia sprawdzania stanów testowych powinna wystarczyć. Na przykład zobacz artykuł Matthew McKague'a arXiv: 1010.1989 [quant-ph]. Jeśli otrzymasz dowód, prześlij dokument do QIP (termin 5 października)!

Anonimowy
źródło

Być może nie rozumiem tego pytania. Jeśli pytasz, czy możesz zaimplementować obwód weryfikatora dla problemu w QMA za pomocą obliczeń opartych na pomiarach, w których Merlin dostarcza warstwę wejściową, a Arthur dostarcza wszystkie dalsze kubity w stanie zasobu i splata oba zestawy kubitów przed rozpoczęciem pomiarów, wtedy odpowiedź brzmi trywialnie tak. Wynika to bezpośrednio z faktu, że dowolny obwód kwantowy może być zaimplementowany jako obliczenie oparte na pomiarach, niezależnie od tego, czy zależy Ci na wejściu klasycznym czy kwantowym.

Zauważysz, że w większości artykułów na temat obliczeń miejsca wprowadzania obliczeń są ogólnie identyfikowane oddzielnie od innych miejsc i właśnie dlatego (tj. Konkretnie w przypadku przypadku danych kwantowych).

Joe Fitzsimons
źródło

Właściwie nie jestem pewien w tej kwestii. W artykułach z obliczeń opartych na pomiarach, na które patrzyłem, transformacja przebiega z dowolnego obwodu BQP z klasycznym wejściem do jednokierunkowego obwodu obliczeniowego rozpoczynającego się od stanu skupienia. Oznacza to, że NIE jest to opisywane jako transformacja przenosząca dowolny arbitralny obwód jednostkowy U do obwodu pomiarowego U_1, bez względu na wejście. Chociaż pytanie o złożoność, które zadałem, zostało rozwiązane po odpowiedzi Norberta, nadal chciałbym zrozumieć ten punkt.

Lior Eldar,

@LiorEldar: Zatem powinieneś spojrzeć na oryginalny papier Raussendorf i Briegel lub papier Raussendorf, Browne i Briegel. Wyraźnie konstruują obwody pojedynczo, pokazując, że każdy wzorzec pomiarowy implementuje daną bramkę na warstwie wejściowej, która może być w dowolnym stanie. Zdecydowanie można zaimplementować dowolne obwody na dowolnych wejściach.

Joe Fitzsimons,

Lior rzeczywiście był tutaj, w Aachen, kiedy o tym rozmawialiśmy, i jeden sposób na zrozumienie pytania opiera się na tym pomyśle: czy Merlin mógłby dostarczyć dowód wbudowany w (niezaufany) stan skupienia, a Arthur używa swoich pomiarów w jednym kubicie, aby zweryfikować klaster lub zweryfikować dowód za pomocą MBQC? (Być może można by użyć podobnych pomysłów jak w ślepej kompilacji, gdzie stosowana jest korekcja błędów?) Niestety, nie potrzeba tego miłego pomysłu, aby udowodnić twardość QMA. ;-( Uważam jednak, że nadal jest interesujące pytanie, czy to zadziała, a ty byłbyś ekspertem, aby to pokazać :-)

Norbert Schuch,

@Lior: Jeśli chcesz użyć MBQC do weryfikacji danych wejściowych, oprócz pomiarów jednokubitowych potrzebujesz oczywiście również 2-kubitowych bramek (ponieważ musisz splątać dane wejściowe ze stanem klastra).

Norbert Schuch,

@Joe: BTW, to samo pytanie dla BQP (czy możemy uruchomić BQP za pomocą pomiarów 1-kubitowych przy niezaufanym stanie skupienia) jest oczywiście nadal otwarte i wydaje mi się, że pomysły zastosowane w ślepym obliczeniu mogą być dobrym pomysłem .

Norbert Schuch,