Jak zaimplementowałbym kwantową wyrocznię w algorytmie Deutscha?

Próbuję symulować algorytm Deutscha (elementarny przypadek algorytmu Deutscha-Joszy) i nie jestem całkowicie pewien, w jaki sposób przystąpiłbym do implementacji kwantowej wyroczni niezbędnej do działania algorytmu, nie przekreślając celu algorytmu i „szukając” na czym polega wprowadzona funkcja, oceniając funkcję.

Tutaj są dwa pytania. Pierwszy z nich pyta, w jaki sposób możesz to zaimplementować w kodzie, a drugi pyta, o co chodzi, jeśli wiesz, jaką przepowiednię przekazujesz.

Realizacja

Prawdopodobnie najlepszym sposobem jest utworzenie funkcji, IsBlackBoxConstantktóra pobiera wyrocznię jako dane wejściowe, a następnie uruchamia program Deutsch Oracle w celu ustalenia, czy jest ona stała. Jeśli chcesz, możesz wybrać wyrocznię losowo. Oto, zaimplementowane w Q #:

operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
{
    body
    {
        mutable inputResult = Zero;
        mutable outputResult = Zero;

        // Allocate two qbits
        using (qbits = Qubit[2])
        {
            // Label qbits as inputs and outputs
            let input = qbits[0];
            let output = qbits[1];

            // Pre-processing
            X(input);
            X(output);
            H(input);
            H(output);

            // Send qbits into black box
            blackBox(input, output);

            // Post-processing
            H(input);
            H(output);

            // Measure both qbits
            set inputResult = M(input);
            set outputResult = M(output);

            // Clear qbits before release
            ResetAll(qbits);
        }

        // If input qbit is 1, then black box is constant; if 0, is variable
        return One == inputResult;
    }
}

Jaki jest sens?

Złożoność zapytania

Złożoność obliczeniowa to dziedzina zajmująca się klasyfikowaniem algorytmów według ilości zużywanych zasobów w funkcji wielkości wejściowej. Zasoby te obejmują czas (mierzony w krokach / instrukcjach), pamięć, a także coś, co nazywa się złożonością zapytań . Złożoność zapytania zależy od tego, ile razy algorytm musi wysłać zapytanie do funkcji wyroczni czarnej skrzynki.

$n$$2^{n-1}$

$2^{n-1}$

Aplikacje w prawdziwym świecie

Jeśli nie jesteś teoretykiem złożoności, możesz rozsądnie nie przejmować się złożonością zapytań i zamiast tego chcesz wiedzieć, dlaczego problem wyroczni Deutsch jest ważny w świecie „bez reguł”, w którym możesz zaglądać do czarnej skrzynki. Próba analizy problemu wyroczni jako problemu nierozstrzygniętego jest trudna i nie sądzę, aby ktokolwiek rozwiązał kwestię najlepszego klasycznego algorytmu dla problemu wyroczni Deutsch, gdy można analizować obwód wyroczni. Możesz pomyśleć - co można przeanalizować? Istnieją tylko cztery możliwe obwody! W rzeczywistości jest to o wiele bardziej skomplikowane.

Jeśli spojrzymy na najprostszą reprezentację jednobitowego Deutsch Oracle, konstrukcja bramy wygląda następująco:

$C_{1,0}$

$X_0C_{1,0}$

$\mathbb{I}_4$

$X_0$

Nie są to jednak jedyny sposób na wdrożenie wyroczni. Wszystkie te można przepisać przy użyciu setek, tysięcy, a nawet milionów bramek logicznych! Liczy się tylko skumulowany efekt tych bramek logicznych, równoważny powyższej prostej konstrukcji. Rozważ następującą alternatywną implementację Constant-1:

$H_0Z_0H_0$

Okazuje się, że dla każdego wkładu, jaki kiedykolwiek możesz podać:

$H_0Z_0H_0|\psi\rangle = X_0|\psi\rangle$

$H_0Z_0H_0$$X_0$

$H_0Z_0H_0 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = X_0$

Więc mamy:

$(H_0(Z_0(H_0|\psi\rangle))) = (((H_0Z_0)H_0)|\psi\rangle) = X_0|\psi\rangle$

$H_0Z_0H_0$$X_0$

Ważne ze względów historycznych i pedagogicznych

Przede wszystkim problem Deutsch Oracle jest ważny ze względów historycznych i pedagogicznych. Jest to pierwszy algorytm, którego uczą uczniowie, ponieważ jest najprostszy i wydaje się wykazywać przyspieszenie kwantowe, o ile nie zadaje się zbyt wielu pytań. Służy również jako dobry punkt wyjścia do nauki problemu okresowości Simona, a następnie algorytmu Shora.

Nie ma sposobu, aby zbudować wyrocznię w sposób, który nie pokonałby punktu algorytmu Deutscha - dlatego jest to algorytm oparty na wyroczni.

$x$$f(x)$$f(0)=f(1)$

$f(x)$$1 \leq x \leq N$$f(x)$$y$$f(x+y)=f(x)$$f(x)$

Chodzi o to, że algorytmy oparte na wyroczni dowodzą, że możesz uzyskać przyspieszenie, jeśli masz problem z tą strukturą (tj. Gdy chcesz tylko poznać określoną właściwość funkcji), ale nie mówi ci, czy taki problem istnieje.

Jeśli więc chcesz wdrożyć Deutsch, jakikolwiek sposób wykonania wyroczni jest w porządku - jest to algorytm „sprawdzania zasad” i nie zapewnia rzeczywistego przyspieszenia rzeczywistego problemu (przynajmniej takiego, o którym nie wiemy).

Na stronie IBM Q Experience znajdują się dwa przykłady dotyczące algorytmu . Pokazują przykład funkcji. Mam nadzieję, że może cię to zainspirować do twoich symulacji.

Nie mam przykładu przydatnego algorytmu Deutscha, ale tutaj i tutaj są dwa samouczki, które przeprowadzą cię przez implementację algorytmu Deutsch-Jozsa i wyroczni, których używa w Q #.

Pomysł na te dwa algorytmy jest taki sam: musisz dostarczyć wyrocznię do algorytmu jako operację zaimplementowaną gdzie indziej. W ten sposób algorytm nie wie, która wyrocznia została podana i nie ma sposobu, aby „spojrzeć” na wyrocznię inaczej niż przez jej wywołanie. Te samouczki mają również uprząż, która liczy, ile razy jest wywoływana wyrocznia, więc jeśli twoje rozwiązanie wywoła ją więcej niż raz, nie przejdzie testu.

Trzeba przyznać, że nadal ma to problem, który często mają algorytmy wyroczni: człowiek może spojrzeć na wykonanie testu i na przekazaną wyrocznię i wymyślić odpowiedź, zastanawiając się, która wyrocznia jest zaimplementowana. Można temu przeciwdziałać losowo wybierając wyrocznię, jak sugerował DaftWullie.

Myślę, że ta ahelwerodpowiedź dotyczy niektórych sposobów myślenia o złożoności algorytmów. Jednak - biorąc pod uwagę, że dosłownie nie mamy „wyroczni” w prawdziwym świecie, które chcielibyśmy zapytać, możesz zastanawiać się, dlaczego martwilibyśmy się złożonością zapytań lub ideą wyroczni. Spróbuję rzucić na to pewną perspektywę, a w szczególności opisać, w jaki sposób możesz spróbować wymyślić „wyrocznię Deutsch-Josza” w sposób, który nie wydaje ci się, że oszukujesz.

(Jak Norbert Schuchzaznaczono, w przypadku problemu Deutscha, który jest podstawowym przypadkiem Deutscha-Joszy, nie ma zbyt wiele miejsca na spostrzeżenia, ale spodziewam się, że twoje pytanie dotyczące wyroczni dotyczy również bardziej ogólnie. Właśnie o tym tutaj porozmawiam.)

Intuicja o wyroczniach

Koncepcja wyroczni jest sposobem na uproszczenie sposobu, w jaki mówimy o problemach obliczeniowych.

Pierwotnym zastosowaniem koncepcji wyroczni było rozważenie hipotetycznie, co moglibyśmy zrobić, gdybyśmy mogli rozwiązać trudne problemy, a nawet problemy niemożliwe, nie zobowiązując się do tego, w jaki sposób moglibyśmy to zrobić nawet w zasadzie. Ale obecnie w złożoności obliczeniowej - szczególnie w obliczeniach kwantowych, np.  W przypadku Deutscha-Joszy, Bernsteina-Vazirani i innych problemów wyroczni - sytuacja jest inna: wyrocznia opisuje funkcję, która jest podstawą problemu. Fakt, że jest to „wyrocznia”, jest sposobem na ustrukturyzowanie, w jaki sposób opisujemy funkcję, która jest w centrum problemu: nie dlatego, że nigdy nie możemy zastanawiać się, w jaki sposób obliczana jest funkcja, ale że informacje te po prostu nie są dostarczane jako część problemu i że nie zajmujemy się czasem ani inną złożonością związaną z tą funkcją.

Przyjmując takie podejście, możemy faktycznie uzyskać odpowiedzi związane z bardzo trudnymi pytaniami w obliczeniach. Na przykład, abyście wiedzieli, że nie wiemy, jak to udowodnić albo P  ≠  NP czy P  =  NP , ale które mogą pokazać, że istnieją wyrocznie takie, że możemy pokazać, że P ^A  ≠  NP ^A . To, co robi tutaj wyrocznia A , nie pomaga komputerowi (a dokładniej deterministycznej maszynie Turinga lub niedeterministycznej maszynie Turinga) w rozwiązaniu problemu - reprezentuje problem, który komputer musi rozwiązać. Fakt, że możemy pokazać, że w niektórych przypadkach P ≠  NP , nie oznacza, że P jest naprawdę różni się od NP : To po prostu oznacza, że tylko przy użyciu nondeterminism jest naprawdę znaczny zasób dla modelu obliczeń mieć - to pozwala skutecznie rozwiązać pewne problemy, i nie ma sposobu, ogólnie, aby skutecznie symulować niedeterminizm na deterministycznym komputerze. Więc jeśli chcesz, aby rozwiązać problem związane z zawartością A oblicza, bezwzględnie wymaga trochę informacji o strukturze dowolnej funkcji, które mogłyby skutecznie obliczyć A .

Jest to jedna z głównych rzeczy, które dotyczą wyroczni: pozwalają mówić o sposobach, w których modele obliczeniowe mogą lub nie mogą rozwiązywać problemów, gdy masz ograniczone informacje na temat problemu.

Używanie algorytmów Oracle do rozwiązywania problemów niezwiązanych z Oracle

Algorytm Deutsch – Josza lub algorytm Bernsteina – Vazirani nie są w zasadzie algorytmami, które wykonuje się dla nich samych. (Cóż, niezupełnie - patrz następna sekcja.) Stanowią sposoby rozwiązania problemu . Jakie problemy rozwiązują? Pozwalają odkryć pewne cechy interesującej Cię funkcji - niezależnie od tego, czy jest ona stała / zrównoważona, czy jaki wektor jest powiązany z jakąś funkcją liniową o wartościach skalarnych na wektorach.

Na jakich funkcjach je wykonujesz? - Wykonujesz je na dowolnej funkcji, dla której jesteś zainteresowany odpowiedzią.

Opis tych algorytmów opartych na wyroczniach nie ma znaczenia. Problemy z wyrocznią w zasadzie pozwalają ci wiedzieć, że dzięki idealnemu komputerowi kwantowemu możesz rozwiązać problem, nawet jeśli wiesz bardzo mało o tej funkcji , pod warunkiem, że faktycznie możesz skutecznie ocenić funkcję w praktyce. Aby faktycznie ocenić taką funkcję, oczywiście potrzebujesz trochę opisu, jak to zrobić, a więc masz więcej informacji niż w ustawieniu Oracle; ale to nie przeszkadza w użyciu tego samego algorytmu.

Gdy masz więcej informacji niż w wyroczni, dzieje się tak , że nagle są inne sposoby rozwiązania problemu. W szczególności może okazać się możliwe skuteczne rozwiązanie problemu klasycznie . (Jest to ta sama obserwacja, co w przypadku P ^A  ≠  NP ^A : dowodzi, że w NP występują problemy , które każdy skuteczny algorytm deterministyczny wymagałby co najmniej rzeczywistej informacji strukturalnej do rozwiązania - tak więc, gdy podasz opis o wydajnie obliczalnej funkcji zamiast „wyroczni”, możliwe, że problem się pojawiP. ) Oznacza to, że algorytm kwantowy może nie mieć takiej samej przewagi nad klasycznymi algorytmami przy rozwiązywaniu konkretnego problemu, który przedstawisz - i może być tak, że klasyczne podejście jest lepsze (szczególnie w przypadku urządzeń, które mamy obecnie).

W końcu to, że masz algorytm kwantowy do rozwiązania problemu, nie oznacza, że ​​jest to najlepszy sposób na rozwiązanie problemu. Jest to z pewnością prawda w przypadku algorytmu Deutsch – Josza: nawet w ustawieniach Oracle użycie losowości jest prawie tak samo dobre, i jest o wiele lepsze, biorąc pod uwagę, że nie mamy jeszcze dużych niezawodnych komputerów kwantowych! Ale potem znowu...

„Wdrażanie” wyroczni

Cel implementacji algorytmu Deutsch – Josza jest taki sam jak implementacja „ Witaj, świecie! ” - nie po to, aby rozwiązać palący nierozwiązany problem, ale poćwiczyć używanie narzędzia, które, jak się spodziewasz, będzie przydatne do robienia innych rzeczy.

Aby ćwiczyć kodowanie, powinieneś czuć się całkowicie zrelaksowany i wygodny z pomysłem wdrożenia wyroczni oraz z pomysłem komputera oceniającego wyrocznię. Zasadniczo jest to punkt tego, co chcesz zrobić. Nawet jeśli używasz klasycznego emulatora, w którym klasyczny komputer faktycznie ocenia wszystkie gałęzie superpozycji i tak wyraźnie znajduje odpowiedź na problem, aby udawać, że jest to komputer kwantowy działający w nieco bardziej okrągły sposób, więc niech tak będzie - ćwiczysz, jak korzystać z narzędzia, które może być przydatne do innych rzeczy, a które pewnego dnia nie będzie działać na klasycznym komputerze.

Jak więc powinieneś wdrożyć swoją wyrocznię?

(i) Jeśli naprawdę jesteś przekonany, że dopiero zaczynasz ćwiczyć, nie musisz udawać, że robisz coś magicznego. Wymyśl jakikolwiek sposób na wdrożenie funkcji wyroczni, nawet jeśli zwykły obserwator jest rażąco oczywisty, czy wynik jest stały, czy zrównoważony. Po prostu próbujesz ćwiczyć realizowanie algorytmu - nie martw się, że ktoś oskarży cię o oszustwo, że udajesz, że leczysz raka, ale tak naprawdę bawisz się klockami Lego. Nigdy nie zostały udając leczyć raka, a są gry z Lego przez świadomego wyboru. Przyjmij to i po prostu zrób to.

$f(x) = g(x,r)$$r$$g(x,r)$$x$$r$i gdzie nie jest oczywiste, jak rozwiązać to klasycznie, nie jest trywialne.

• $g(x,r) = x \cdot r$$x,r \in \{0,1\}^n$$g(x,r)$$f(x)$$f(x)$$r \ne 0$

• Można sobie wyobrazić, że powyższą konstrukcję można by nieco rozwinąć / zaciemnić, aby uzyskać konstrukcję, która gwarantuje ocenę funkcji stałej lub funkcji zrównoważonej, i gdzie która z tych dwóch wystąpi nie jest oczywista ani nawet trudna - ale ja mogę ” Pomyśl o tym, jak w tej chwili.

Pamiętaj, że tak naprawdę jest to bardzo trudne - ale jeśli potrafisz to zrobić, może być bardzo opłacalne: Bravyi, Gossett i Koening zrobili coś takiego w przypadku problemu Bernsteina-Vazirani i pozwoliło im to aby pokazać niewielki, ale bezwarunkowy rozdział złożoności kwantowej od klasycznej, co było jedną z bardziej interesujących rzeczy w złożoności kwantowej w ciągu ostatnich kilku lat.

TL; DR

• Nie przejmuj się faktem, że „oceniasz” wyrocznię.

• Jeśli się pocisz, martw się, że faktyczny opis funkcji może ułatwić rozwiązanie tego samego problemu bez komputera kwantowego.

• Jeśli twoją motywacją jest tylko ćwiczenie z programowania kwantowego, nie przejmuj się tym. Oszczędzaj martwienia się o bardziej wartościowe problemy, takie jak globalne ocieplenie. W międzyczasie ciesz się grą z Legos, gdy budujesz coś więcej.