Pytania otagowane jako grovers-algorithm

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.

3
Czy istnieje wyjaśnienie dla laika, dlaczego algorytm Grovera działa?
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 )O(n)O(n)O ( n--√)O(n)O(\sqrt{n}) czas. W szczególności chciałbym zobaczyć zrozumiałą intuicję …
2
Czy od czasu Grovera i Shora nastąpił naprawdę przełomowy postęp w dziedzinie algorytmów kwantowych?
(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 komputery, ale w praktyce były tylko dwa teoretyczne przełomy: Algorytm Shora, który …
2
Czy kwantowe obliczenia adiabatyczne mogą być szybsze niż algorytm Grovera?
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 jest w jakiś sposób związana z problemem - to znaczy znalezienie wystąpienia, które minimalizuje (lub maksymalizuje) tę …
4
Algorytm Grovera: gdzie jest lista?
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, ..., \mathbf{x}_{n-1}]nnn Przeszukiwanie listy, klasyczny sposób Zwykle zaprojektowałbym funkcję wyszukiwania w ten sposób Więc podaję listę i poszukiwany element jako dane …
2
Jak działa operator dyfuzji Grovera i dlaczego jest optymalny?
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 sprawić, że drobne różnice we wcześniejszych krokach są wystarczająco …
3
Jakie aplikacje ma algorytm wyszukiwania Grovera?
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ę o innych zastosowaniach poszukiwania Grovera, aby znaleźć minimum, średnią i medianę zbioru …
2
Algorytm Grovera: przykład z prawdziwego życia?
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 tej kolejności. Moim celem jest znalezienie Reda w bazie …
3
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?xxx Przykład Powiedzmy, że mam kubity. W ten sposób można zmapować klasycznych wartości.44424=1624=162 ^ 4 = 16 Moja nieposortowana baza danych zawiera następujące elementy: …
4
Algorytm Grovera i jego związek z klasami złożoności?
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 danych, tak abykkkf(k)=1f(k)=1f(k)=1 Teraz jestem świadomy, że nie jest to problem desision, dlatego nasze …
2
Implementacja wyroczni algorytmu Grovera na IBM Q przy użyciu trzech kubitów
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 jego znak, tak jak ma to zrobić wyrocznia. …
1
Dlaczego kubit wyroczni jest potrzebny w algorytmie Grovera?
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 nie można rozwiązać bez kubitu wyroczni, lub …
1
W jaki sposób algorytm Grovera służy do oszacowania średniej i mediany zbioru liczb?
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 oszacować średnią i medianę zbioru liczb. Co więcej, …
2
Czy możemy przyspieszyć algorytm Grovera, uruchamiając równoległe procesy?
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 algorytmu Grovera, jak w przypadku klasycznego przetwarzania?
1
Algorytm Grovera: co wprowadzić do Oracle?
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 liście znajduje się „Dio”. Następnie Oracle powinien …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.