Jak stosuje się algorytm Grovera do bazy danych?

Pytanie

Chcę użyć algorytmu Grovera do przeszukania nieposortowanej bazy danych dla elementu . Teraz pojawia się pytanie, jak zainicjować indeks i wartość bazy danych za pomocą kubitów?$x$

Przykład

• Powiedzmy, że mam kubity. W ten sposób można zmapować klasycznych wartości.$4$$2 ^ 4 = 16$
• Moja nieposortowana baza danych zawiera następujące elementy: .$d$$d [\text{Value}] = [3,2,0,1]$
• Chcę wyszukać $x = 2_d = 10_b = |10\rangle$ .
• Moje podejście: indeksuj bazę danych $d$ pomocą $d [(\text{Index, Value})] = [(0,3), (1,2), (2,0), (3,1)]$ . Rejestruje $0$ i $1$ dla indeksu oraz rejestruje $2$ i $3$ dla wartości. Następnie zastosuj algorytm Grovera tylko do rejestrów $2$ i $3 (\text{Value})$ . Czy można to zrealizować? Czy istnieje inne podejście?

Co już zaimplementowałem ( na GitHub )

„Algorytm Grovera z 2-, 3-, 4-Qubitami”, ale to, co robi, jest proste: bity są inicjalizowane za pomocą $|0\rangle$ , wyrocznia zaznaczy moje rozwiązanie $x$ (co jest tylko liczbą $2_d = 10_b$ ), część Grovera zwiększy prawdopodobieństwo wybranego elementu $x$ i zmniejszy wszystkie inne prawdopodobieństwa, a następnie kubity zostaną odczytane poprzez odwzorowanie na klasyczne bity. Pozwalamy temu procesowi działać kilka razy z rzędu, a tym samym uzyskać rozkład prawdopodobieństwa, w którym największe prawdopodobieństwo ma poszukiwany element $x$ .

Wyjście jest zawsze takie samo, jak zaznaczone w wyroczni. Jak mogę wygenerować więcej informacji z danych wyjściowych, których nie znam w momencie, gdy budowałem wyrocznię?

Pracowałem również nad tym problemem. Jako początkujący i klasyczny programista (tzn. Nie mówię o mechanice kwantowej) trudno jest zrozumieć pojęcia bez pełnych przykładów. Pracowałem z próbką wyszukiwania bazy danych Microsoft Q # . Po prostu szuka określonego indeksu / klucza w bazie danych, co nie jest bardzo przydatne. Rozszerzyłem tę próbkę, aby wyszukać listę wartości w bazie danych i zwrócić odpowiedni klucz.

Podobnie jak w twoim przykładzie, istnieje jeden dwububitowy „rejestr kluczy” dla indeksów i osobny dwububitowy rejestr wartości. Istnieje również piąty „zaznaczony kubit”, który pochodzi z próbki Microsoftu, aby wskazać, kiedy pożądana wartość zostanie znaleziona. Klucze i wartości są powiązane przez splątanie. Najlepszym tego przykładem jest obwód. Kliknij tutaj, aby zobaczyć aktualny obwód Quirka .

Zauważ, że ten obwód zawiera tylko wyrocznię. Nie implementuje całego algorytmu Grovera.

• Dwa górne kubity są rejestrem kluczy, następne dwa są rejestrem wartości, a dolny kubit jest zaznaczonym kubitem.
• Pierwsza sekcja umieszcza rejestr kluczy w jednolitej superpozycji przy użyciu bram Haramarda, zgodnie z wymaganiami algorytmu Grovera.
• W drugiej sekcji klucze są powiązane z wartościami przez splątanie. Każdy klucz jest splątany z odpowiednią wartością w rejestrze wartości przez zastosowanie (anty-) kontrolowanych bramek X. Tak więc, gdy rejestr kluczy wynosi 0, wówczas rejestr wartości zostanie ustawiony na 3. Gdy klucz to 1, wartość zostanie ustawiona na 2 i tak dalej.
• Trzecią częścią obwodu jest wyrocznia poszukiwawcza. Rejestr wartości jest zaplątany w zaznaczony kubit. W tym przykładzie pożądaną wartością jest 2. Gdy rejestr wartości zawiera 2, zaznaczony kubit zostanie ustawiony na 1.
• Algorytm Grovera sprawdza rejestr kluczy i zaznaczony kubit. Wyrocznia wyszukiwania patrzy na rejestr wartości i ustawia zaznaczony kubit. Spowoduje to wzmocnienie klawisza 1, gdy wartość wynosi 2.

Warto zauważyć, że klucze i wartości nie są przechowywane w kubitach, ale raczej w obwodzie / programie. Można powiedzieć, że tak naprawdę nie jest to baza danych. To bardziej jak instrukcja switch / case, ale taka, która może działać na superpozycji wartości.

Aby uzyskać więcej informacji, ostrzeżenia i kod Q #, zobacz moje repozytorium GitHub .

EDYCJA: Coś, co rozumiem lepiej od czasu odpowiedzi ... musisz cofnąć / cofnąć obwód w ramach każdej iteracji. W kodzie Q # wywołanie Adjoint StatePreparationOracle () w ramach operacji ReflectStart () obsługuje to, więc nie musiałem tego robić jawnie. Nie wiem, czy Qiskit ma podobną funkcję. Jeśli poprawnie wykonałem tłumaczenie, oto kompletny obwód dla powyższego przykładu.

$n=4$

Myślę, że lepiej myśleć o algorytmie wyszukiwania kwantowego jako o optymalizacji funkcji, zamiast przeszukiwania listy / bazy danych. Oto artykuł, nad którym pracowałem, w którym wykorzystuje się wyszukiwanie kwantowe do rozwiązania kombinatorycznego problemu maksymalizacji, jeśli chcesz pogłębić swoje zrozumienie algorytmu.

Musisz również przekonwertować wyrocznię, aby przechowała także bazę danych, w wyniku czego ogólna Oracle (Phase Inversion) będzie miała dwa sub-wyrocznie, patrz rysunek.

Pierwszym pod-wyrocznią, którą należy przygotować, jest obwód pamięci, w przeciwieństwie do pamięci QRAM, która przechowuje dane kwantowe (stan) w swoim ciele, ten obwód pamięci (macierzy) jest przygotowany do przechowywania tylko klasycznych informacji w swojej ramce. Przykład takiego rodzaju obwodu, który przechowuje tablicę plików binarnych [010, 110, 100, 011] jest wyświetlany poniżej: Więcej informacji można znaleźć w tym dokumencie .