Problem Simona

Nie należy mylić z problemami Simona w fizyce matematycznej.

W teorii złożoności obliczeniowej i obliczeniach kwantowych problem Simona jest problemem obliczeniowym , który, jak udowodniono, jest rozwiązywany wykładniczo szybciej na komputerze kwantowym niż na komputerze klasycznym (czyli tradycyjnym). Algorytm kwantowy rozwiązujący problem Simona, zwykle nazywany algorytmem Simona , posłużył jako inspiracja dla algorytmu Shora . Oba problemy są szczególnymi przypadkami problemu abelowej ukrytej podgrupy , o którym obecnie wiadomo, że ma wydajne algorytmy kwantowe.

Problem jest osadzony w modelu złożoności drzewa decyzyjnego lub złożoności zapytań i został wymyślony przez Daniela Simona w 1994 roku. Simon przedstawił algorytm kwantowy , który rozwiązuje problem Simona wykładniczo szybciej i z wykładniczo mniejszą liczbą zapytań niż najlepszy klasyczny algorytm probabilistyczny (lub deterministyczny). W szczególności algorytm Simona wykorzystuje liniową liczbę zapytań, a każdy klasyczny algorytm probabilistyczny musi wykorzystywać wykładniczą liczbę zapytań.

Ten problem daje wyrocznię separację między klasami złożoności BPP (klasyczna złożoność zapytania z ograniczonym błędem) i BQP (złożoność zapytania kwantowego z ograniczonym błędem). Jest to ta sama separacja, którą algorytm Bernsteina – Vaziraniego , i różni się od separacji zapewnianej przez algorytm Deutscha – Jozsy , który oddziela P i EQP . W przeciwieństwie do algorytmu Bernsteina – Vaziraniego , separacja algorytmu Simona jest wykładnicza .

Ponieważ ten problem zakłada istnienie wysoce ustrukturyzowanej wyroczni „czarnej skrzynki”, aby osiągnąć jego przyspieszenie, problem ten ma niewielką wartość praktyczną. Jednak bez takiej wyroczni nie można łatwo udowodnić przyspieszeń wykładniczych, ponieważ udowodniłoby to, że P różni się od PSPACE .

Opis problemu

Biorąc pod uwagę funkcję (zaimplementowaną przez czarną skrzynkę lub wyrocznię) $n}}$${\ Displaystyle f: \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \}$$nieznanych$${\ displaystyle x, y \ w \ {0,1 \} ^ {n}}$ obietnicą, dla ,

$)}$ wtedy i tylko wtedy, gdy ${\ Displaystyle x \ oplus y \ w \ {0 ^ {n },s\}}$ ,

gdzie $oznacza$ XOR. Celem jest zidentyfikowanie $,$${\ displaystyle f (x)}$ jak najmniej zapytań do . Zauważ to

${\ Displaystyle a \ oplus b = 0 ^ {n}}$ wtedy i tylko wtedy, gdy ${\ Displaystyle a = b}$

Ponadto, dla niektórych i ${\ Displaystyle$$s}$ w ${\ Displaystyle x \ oplus y = s}$ , ${\ Displaystyle y}$ wyjątkowy (nie równy ${\ Displaystyle y} x}$ ) wtedy i tylko wtedy, gdy ${\ Displaystyle s \ neq 0 ^ {n}}$ . Oznacza to, że $\ displaystyle f}$ dwa do jednego, gdy ${\ Displaystyle s \ neq 0 ^ {n}}$ i fa { jeden do jednego , gdy ${\ displaystyle s = 0 ^ {n}}$ . $= s {\ Displaystyle x \ oplus y = s$ również tak, że implikuje ${\ Displaystyle y = s \ oplus x}$ , co oznacza, że

$${\ Displaystyle f (x) = f (y) = f (x \ oplus {s})}$$

co pokazuje, jak $jest$ .

Powiązanym sformułowaniem problemu decyzyjnego problemu Simona jest rozróżnienie, kiedy ${\ displaystyle s$ jest jeden do jednego), a kiedy $} \ neq 0 ^ {n}}$$0 ^ {$ ( jest $.$ do jednego)

Przykład

Na przykład, jeśli ${\ displaystyle n = 3}$ , to następująca funkcja jest przykładem funkcji, która spełnia wymaganą i właśnie wymienioną właściwość: n = 3 {\ displaystyle n = 3}

${\ displaystyle x}$	${\ Displaystyle f (x)}$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

W tym przypadku ${\ displaystyle s = 110}$ (czyli rozwiązanie). Można łatwo zweryfikować, że każde wyjście $dwukrotnie$ , a dwa łańcuchy wejściowe odpowiadające dowolnemu danemu wyjściu mają bitowy XOR równy ${\ displaystyle s = 110}$ .

$wyjściowy$ przykład ciągi wejściowe i $\$$displaystyle 100}$ są odwzorowywane (przez $na$ sam ciąg . ${\ Displaystyle {\ Displaystyle f (010) = 000}}$ i ${\ Displaystyle {\ Displaystyle f (100) = 000}}$ . Jeśli zastosujemy XOR do 010 i 100 otrzymamy 110, czyli ${\ Displaystyle {\ Displaystyle 010 \ oplus 100 = 110 = s}.}$

${\ displaystyle s = 110}$ można również zweryfikować za pomocą ciągów wejściowych 001 i 111, które są odwzorowane (przez f) na ten sam ciąg wyjściowy 010. Jeśli zastosujemy XOR do 001 i 111, otrzymamy 110, to znaczy ${\ Displaystyle 001 \ oplus 111 = 110 = s}$ . $rozwiązaliśmy$ samo rozwiązanie, wcześniej.

W tym przykładzie funkcja f jest rzeczywiście funkcją dwa do jednego, gdzie ${\ Displaystyle {\ Displaystyle s \ neq 0 ^ {n}}}$ .

Problematyczna twardość

Intuicyjnie jest to bardzo trudny problem do rozwiązania w „klasyczny” sposób, nawet jeśli zastosuje się losowość i zaakceptuje małe prawdopodobieństwo błędu. Intuicja stojąca $\displaystyle f(x)=f(y)}$ dość prosta: jeśli chcesz rozwiązać problem , musisz znaleźć dwa różne dane wejściowe, $dla$ których $)$$y$ . Funkcja niekoniecznie ma jakąkolwiek strukturę ${\ displaystyle f}$ które pomogłyby nam znaleźć dwa takie dane wejściowe: dokładniej, możemy dowiedzieć się czegoś o $tylko$ wtedy, gdy dla dwóch różnych danych wejściowych otrzymamy ten sam wynik. W każdym razie musielibyśmy zgadnąć $, zanim$ na ${ \displaystyle f}$ daje taki sam wynik, jak w przypadku problemu z urodzinami . Ponieważ klasycznie znaleźć s $wejściowych ,$ sprawdzenia Simona polega na znalezieniu s przy użyciu mniejszej liczby niż ta klasyczna metoda

Algorytm Simona

Obwód kwantowy reprezentujący/implementujący algorytm Simona

Algorytm jako całość wykorzystuje ten podprogram w następujących dwóch krokach:

1. Uruchom podprogram kwantowy oczekiwaną $,$ aby uzyskać listę liniowo łańcuchów ${\ Displaystyle y_ {1}, ..., y_ {n-1}}$ .
2. Każdy spełnia $displaystyle$$y_ {k} \ cdot s = 0} y k {\ displaystyle y_ {k}} , więc możemy$ układ równań, który tworzy, aby uzyskać $\ displaystyle s}$ .

Podprogram kwantowy

Obwód kwantowy (patrz rysunek) jest implementacją kwantowej części algorytmu Simona. Podprogram kwantowy algorytmu wykorzystuje transformatę Hadamarda

$${\ Displaystyle H ^ {\ otimes n} | k \ rangle = {\ Frac {1} {\ sqrt {2 ^ {n}}}} \ suma _ {j = 0} ^ {2 ^ {n} -1}(-1)^{k\cdot j}|j\rangle }$$

gdzie ${\ Displaystyle k \ cdot j = k_ {1} j_ {1} \ oplus \ ldots \ oplus k_ {n} j_ {n}}$ , gdzie ${\ Displaystyle \ oplus}$ oznacza XOR .

Po pierwsze, algorytm rozpoczyna się od dwóch rejestrów, zainicjowanych jako ${\ Displaystyle | 0 \ rangle ^ {\ otimes n} | 0 \ rangle ^ {\ otimes n}}$ . Następnie stosujemy transformatę Hadamarda do pierwszego rejestru, który daje stan

${\ Displaystyle {\ Frac {1} {\ sqrt {2 ^ {n}}}} \ suma _ {k = 0} ^ {2 ^ {n} -1} | k \ rangle | 0 \ rangle ^{\czasami n}}$

$Zapytaj$ wyrocznię, uzyskać

${\ Displaystyle {\ Frac {1} {\ sqrt {2 ^ {n}}}} \ suma _ {k = 0} ^ {2 ^ {n} -1} | k \ rang | f (k)\zakres }$ .

Zastosuj kolejną transformatę Hadamarda do pierwszego rejestru. To stworzy państwo

${\ Displaystyle {\ Frac {1} {\ sqrt {2 ^ {n}}}} \ suma _ {k = 0} ^ {2 ^ {n} -1} \ lewo [{\ frac {1}{\sqrt {2^{n}}}}\suma _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \ prawo]|f(k)\rangle =\suma _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\ suma _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right]}$

Na koniec mierzymy pierwszy rejestr (algorytm działa również wtedy, gdy drugi rejestr jest mierzony przed pierwszym, ale jest to niepotrzebne). Prawdopodobieństwo pomiaru stanu ${\ Displaystyle | j \ rangle}$ jest

$${\ Displaystyle \ lewo | \ lewo | {\ Frac {1} {2 ^ {n}}} \ suma _ {k = 0} ^ {2 ^ {n} -1} (-1) ^ {j \ cdot k}|f(k)\rangle \right|\right|^{2}}$$

Wynika to z faktu, że obliczenie wielkości tego wektora i podniesienie go do kwadratu sumuje wszystkie prawdopodobieństwa wszystkich możliwych pomiarów drugiego rejestru, który musi mieć pierwszy rejestr jako ${\ Displaystyle | j \ rangle}$ . Nasz pomiar ma dwa przypadki:

1. ${\ displaystyle s = 0 ^ {n}}$ i ${\ displaystyle f}$ jest jeden do jednego.
2. ${\ Displaystyle s \ neq 0 ^ {n}}$ i ${\ Displaystyle f}$ to dwa do jednego.

W pierwszym przypadku od

$${\ Displaystyle \ lewo | \ lewo | {\ Frac {1} {2 ^ {n}}} \ suma _ {k = 0} ^ {2 ^ {n} -1} (-1) ^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}}$$

ponieważ w tym przypadku $} ^ {n}}$$\$ } n $displaystyle$ , co oznacza, że ​​sumowanie odbywa się po każdym wektorze bazowym. istnieją dwa ciągi $i$ takie że $)$${\ Displaystyle f (x_ {1}) = f (x_ {2}) = z}$ , gdzie ${\ Displaystyle Z \ in \ operatorname {zakres} (f )}$ . Tak możemy napisać

$${\ Displaystyle \ lewo | \ lewo | {\ Frac {1} {2 ^ {n}}} \ suma _ {k = 0} ^ {2 ^ {n} -1} (-1) ^ {j \ cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {zakres} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\ prawda|^{2}}$$

Ponadto, ponieważ wiemy, że ${\ Displaystyle x_ {1} \ oplus x_ {2} = s}$ , wiemy, że ${\ Displaystyle x_ {2} = x_ { 1}\oplus s}$ i tak dalej

$${\ Displaystyle {\ rozpocząć {wyrównane} \ lewo | \ lewo | {\ Frac {1} {2 ^ {n}}} \ suma _ {z \, \ w \, \ operatorname {zakres} (f)} ( (-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\ left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {zakres} (f)}((-1)^{j\cdot x_{1} }+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac { 1}{2^{n}}}\sum _{z\,\in \,\mathrm {zakres} (f)}((-1)^{j\cdot x_{1}}+(-1) ^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^ {n}}}\suma _{z\,\in \,\mathrm {zakres} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\ cdot s})|z\rangle \right|\right|^{2}\end{wyrównane}}}$$

To wyrażenie jest teraz łatwe do oszacowania. Przypomnijmy, że mierzymy ${\ displaystyle j}$ . Kiedy jot $j \ cdot s = 1}$$a$ , to wyrażenie to zostanie ocenione jako ${\ Displaystyle 0}$ kiedy , to wyrażenie to być ${\ Displaystyle 2 ^ {- n + 1}}$ .

Tak więc, zarówno gdy ${\ Displaystyle s = 0 ^ {n}},$ jak i kiedy ${\ Displaystyle s \ neq 0 ^ {n}}$ , nasz zmierzony ${\ displaystyle j}$ spełnia ${ \displaystyle j\cdot s=0}$ .

Klasyczna obróbka końcowa

$aż$ uzyskamy liniowo $listę$ każdy $\ Displaystyle y_ {k}}$ spełnia ${\ Displaystyle y_ {k} \ cdot s = 0}$ . W ten sposób możemy skutecznie rozwiązać ten układ równań klasycznie, aby znaleźć ${\ displaystyle s}$ .

Prawdopodobieństwo, że ${\ Displaystyle y_ {1}, y_ {2}, \ kropki, y_ {n-1}}$ są liniowo niezależne, wynosi co najmniej

$${\ Displaystyle \ prod _ {k = 1} ^ {\ infty} \ lewo (1- {\ Frac {1} {2 ^ {k}}} \right)=0,288788\kropki }$$

$')}$ rozwiążemy układ równań i stworzymy rozwiązanie , możemy sprawdzić, czy ${$$f (0 ^ {n}) = f ($ . $,$ to wiemy ponieważ ${\ Displaystyle f (0 ^ {n}) = f (0 ^ {n} \ oplus s) = f (s)}$ . Jeśli jest tak, że ${\ Displaystyle f (0 ^ {n}) \ neq f (s')}$ , oznacza to, że ${\ Displaystyle s = 0 ^ {n}}$ i ${n}) \ neq f (s')}$$ponieważ$ jest jeden do jednego.

Możemy powtarzać algorytm Simona stałą liczbę razy, aby arbitralnie zwiększyć prawdopodobieństwo sukcesu, zachowując jednocześnie tę samą złożoność czasową.

Jawne przykłady algorytmu Simona dla kilku kubitów

${\ displaystyle n = 1}$

Rozważ najprostszą instancję algorytmu, gdzie ${\ displaystyle n = 1}$ . W tym przypadku ewolucja stanu wejściowego przez bramkę Hadamarda i wyrocznię daje stan (aż do renormalizacji):

${\ Displaystyle | 0 \ rangę | f (0) \ rangę + | 1 \ rangę | f (1) \ rangę.}$

Jeśli $}$$,$ znaczy , pomiar drugiego rejestru zawsze ${\ Displaystyle | f (0) \ rangle}$ i zawsze powoduje załamanie pierwszego rejestru do stanu (aż do renormalizacji):

${\ displaystyle | 0 \ ranga + | 1 \ ranga.}$

Zatem zastosowanie Hadamarda i zmierzenie pierwszego rejestru zawsze daje wynik ${\ Displaystyle | 0 \ rangle}$ . Z drugiej strony, jeśli $to$$|$ do jednego, to znaczy , ${\ Displaystyle | 0 \ rangle}$ rejestru po drugim Hadamarda może dać oba i ${\ Displaystyle | 1 \ rangle}$ z równym prawdopodobieństwem.

Odzyskujemy $wyników$ pomiarów, sprawdzając, czy zawsze mierzyliśmy ${\ Displaystyle | 0 \ rangle}$ , w takim przypadku ${\ Displaystyle s = 1}$ lub zmierzyliśmy oba ${\ Displaystyle | 0 \ rangle}$ i ${\ displaystyle | 1 \ rangle}$ z równym prawdopodobieństwem, w takim przypadku wnioskujemy, że ${\ displaystyle s = 0}$ . Ten schemat się nie powiedzie, jeśli ${\ displaystyle s = 0}$ , ale mimo to zawsze znaleźliśmy wynik ${\ Displaystyle | 0 \ rangle}$ , ale prawdopodobieństwo tego zdarzenia wynosi ${\ Displaystyle 2 ^ {- N}}$$z$ liczbą pomiarów, a zatem może być wykładniczo małe zwiększając statystyki.

${\ displaystyle n = 2}$

Rozważmy teraz przypadek z ${\ displaystyle n = 2}$ . Wynikiem początkowej części algorytmu jest stan (do renormalizacji):,

$${\ Displaystyle | 00 \ rangle | f (00) \ rangle + | 01 \ rangle | f (01) \ rangle + | 10 \ rangle | f (10) \ rangle + | 11 \ rangle | f (11) \ rangle .}$$

Jeśli ${\ Displaystyle s = (00)}$ , co oznacza, $iniekcyjne$ , to znalezienie ${\ Displaystyle | f (x) \ rangle}$ w drugim rejestrze zawsze zwija pierwszy rejestr do ${\ Displaystyle | x \ rangle}$ , dla wszystkich ${\ Displaystyle x \ in \ {0,1 \} ^ {2}}$ . Innymi $Hadamarda$ i mierząc pierwszy rejestr, cztery wyniki w ten sposób

Załóżmy z drugiej strony ${\ Displaystyle s \ neq (00)}$ , na przykład ${\ Displaystyle s = (01)}$ . Następnie pomiar ${\ Displaystyle | f (00) \ rangle}$ w drugim rejestrze zwija pierwszy rejestr do stanu ${\ Displaystyle | 00 \ rangle +|10 \ rangle}$ . A bardziej ogólnie, mierzenie ${\ Displaystyle | f (xy) \ rangle}$ daje ${\ Displaystyle | x, y \ rangle + | x, y \ oplus 1 \ rangle = | x \ rangle (| 0 \ rangle + | 1 \ rangle)} w pierwszym$ rejestrze . Zastosowanie bramek Hadamada i pomiar na pierwszym rejestrze może więc dać wynik ${\ displaystyle 00}$ i ${\ displaystyle 10}$ z równymi prawdopodobieństwami.

$\ Displaystyle 00}$ innych przypadków: jeśli , $01$ możliwe wyniki to $i$ { $01}$ , podczas gdy jeśli $(11)}$$11}$ możliwe wyniki to i $displaystyle$ , zgodne z ${\ displaystyle j \ cdot s = 0}$ reguła omówiona w przypadku ogólnym.

Aby odzyskać $musimy$ więc tylko rozróżnić te cztery przypadki, zbierając wystarczającą liczbę statystyk, aby zapewnić, że prawdopodobieństwo pomylenia jednego rozkładu prawdopodobieństwa wyniku z innym jest wystarczająco małe.

Złożoność

Algorytm Simona wymaga $czarnej skrzynki, podczas gdy$ klasyczny wymagałby co najmniej $\ Omega (2 ^ {n/2}) }$ zapytania. Wiadomo również, że algorytm Simona jest optymalny w tym sensie, że $zapytań$ rozwiązania tego problemu wymaga .

Zobacz też

• Algorytm Deutscha-Jozsy