Algorytm wyszukiwania Grovera to algorytm, który może przeprowadzić wyszukiwanie w kolejności pierwiastka kwadratowego z rozmiaru wejściowego. Jest to możliwe do udowodnienia przyspieszenie w porównaniu z najlepszym klasycznym algorytmem, który wymaga czasu rzędu N na wykonanie wyszukiwania.
Ten blog autorstwa Scotta Aaronsona jest bardzo przydatnym i prostym wyjaśnieniem algorytmu Shora . Zastanawiam się, czy istnieje takie wytłumaczenie drugiego najbardziej znanego algorytmu kwantowego: algorytmu Grovera do przeszukiwania nieuporządkowanej bazy danych o wielkości w O ( √O ( n...
(Przepraszam za nieco amatorskie pytanie) Studiowałem informatykę kwantową w latach 2004-2007, ale od tego czasu straciłem orientację w tej dziedzinie. W tamtym czasie było dużo szumu i dyskusji na temat QC potencjalnie rozwiązującej wszelkiego rodzaju problemy, przewyższającej klasyczne...
Udowodniono, że adiabatyczne obliczenia kwantowe są równoważne „standardowym” lub obliczeniom kwantowym opartym na modelu bramkowym. Jednak obliczenia adiabatyczne pokazują obietnice problemów związanych z optymalizacją, w których celem jest zminimalizowanie (lub zmaksymalizowanie) funkcji, która...
W tej odpowiedzi wyjaśniono algorytm Grovera. Wyjaśnienie wskazuje, że algorytm w dużej mierze opiera się na operatorze dyfuzji Grovera , ale nie podaje szczegółów na temat wewnętrznych działań tego operatora. W skrócie, operator dyfuzji Grovera tworzy „inwersję względem średniej”, aby iteracyjnie...
Algorytm Grovera służy między innymi do wyszukiwania elementu na nieuporządkowanej liście elementów o długości . Mimo że jest tu wiele pytań dotyczących tego tematu, nadal nie rozumiem tego.yy\mathbf{y}[x0,x1,...,xn−1][x0,x1,...,xn−1][\mathbf{x}_0, \mathbf{x}_1, ...,...
Algorytm wyszukiwania Grovera zwykle mówi się o znalezieniu zaznaczonego wpisu w nieposortowanej bazie danych. Jest to naturalny formalizm, który pozwala na bezpośrednie zastosowanie go do poszukiwania rozwiązań problemów NP (gdzie dobre rozwiązanie można łatwo rozpoznać). Chciałem dowiedzieć się...
Jestem dość zdezorientowany, w jaki sposób algorytm Grovera może być wykorzystywany w praktyce i chciałbym prosić o pomoc w wyjaśnieniu na przykładzie. Załóżmy, że baza danych elementów zawiera kolory: czerwony, pomarańczowy, żółty, zielony, cyjan, niebieski, indygo i fioletowy i niekoniecznie w...
Mylę się co do algorytmu Grovera i jego związku z klasami złożoności. Algorytm Grovera znajduje element w bazie danych (tak, że ) elementów z wywołaniami do wyroczni.kkkN=2nN=2nN=2^nf(k)=1f(k)=1f(k)=1∼N−−√=2n/2∼N=2n/2\sim \sqrt{N}=2^{n/2} Mamy więc następujący problem: Problem: Znajdź w bazie...
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?xxx Przykład Powiedzmy, że mam kubity. W ten sposób można zmapować klasycznych wartości.44424=1624=162 ^ 4 =...
Na stronie Wikipedii dotyczącej algorytmu Grovera wspomniano, że: „Algorytm Grovera można również wykorzystać do oszacowania średniej i mediany zbioru liczb” Do tej pory wiedziałem tylko, jak można go wykorzystać do przeszukiwania bazy danych. Ale nie jestem pewien, jak wdrożyć tę technikę, aby...
Jestem trochę zdezorientowany co do konieczności kubitu wyroczni w algorytmie Grovera. Moje pytanie brzmi: czy to zależy od tego, jak wdrażasz swoją wyrocznię, czy potrzebujesz kubitowej wyroczni, czy nie? A może jest jakiś powód, dla którego kubit wyroczni? (np. istnieją pewne problemy, których...
Próbuję się przyzwyczaić do IBM Q, implementując algorytm Grovera w trzech kubitach, ale mam trudności z implementacją wyroczni. Czy możesz pokazać, jak to zrobić lub zasugerować dobre zasoby, aby przyzwyczaić się do programowania obwodów IBM Q? Chcę zaznaczyć jeden arbitralny stan, odwracając...
W obliczeniach klasycznych możemy uruchomić wyszukiwanie klucza (na przykład AES), uruchamiając równolegle węzły obliczeniowe jak najwięcej. Oczywiste jest, że możemy również uruchomić wiele algorytmów Grovera. Moje pytanie brzmi ; czy możliwe jest przyspieszenie przy użyciu więcej niż jednego...
Nie wiem, co wprowadzić do Oracle w algorytmie Grovera. Czy oprócz superpozycjonowanych stanów kwantowych nie musimy wprowadzać tego, czego szukamy i gdzie znaleźć to, czego szukamy? Załóżmy na przykład, że mamy listę nazwisk osób {„Alice”, „Bob”, „Corey”, „Dio”} i chcemy sprawdzić, czy na...