• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algorytm Grovera

    Przeczytaj także...
    Komputer kwantowy – układ fizyczny do opisu którego wymagana jest mechanika kwantowa, zaprojektowany tak, aby wynik ewolucji tego układu reprezentował rozwiązanie określonego problemu obliczeniowego.Informatyka kwantowa – dziedzina łącząca informatykę i mechanikę kwantową, zajmująca się wykorzystaniem własności układów kwantowych do przesyłania i obróbki informacji (patrz też informacja kwantowa).
    Algorytm kwantowy – rodzaj algorytmu przeznaczonego do działania na maszynie kwantowej (komputer kwantowy). Dotychczas powstało kilkanaście algorytmów wykorzystujących możliwości oferowane przez maszyny kwantowe. Należą do nich algorytmy Grovera, Deutscha, Simona, Shora, Kitaeva i Bernsteina-Vaziraniego.

    Algorytm Groveraalgorytm kwantowy przeznaczony do działania na komputerze kwantowym, opublikowany w 1996 przez Lova K. Grovera.

    Algorytm dotyczy przeszukiwania bazy danych składającej się z M elementów w celu znalezienia w niej elementu wyróżnionego. Jest to problem podobny do „odwrotnego” przeszukiwania książki telefonicznej. W książce zawierającej M danych chcemy znaleźć nazwisko posiadacza danego numeru. O ile liczba kroków niezbędna do rozwiązania problemu za pomocą algorytmu klasycznego jest rzędu M, o tyle kwantowy algorytm Grovera potrzebuje jedynie około M kroków, a więc pozwala na kwadratowe przyspieszenie czasu realizacji programu.

    Baza danych – zbiór danych zapisanych zgodnie z określonymi regułami. W węższym znaczeniu obejmuje dane cyfrowe gromadzone zgodnie z zasadami przyjętymi dla danego programu komputerowego specjalizowanego do gromadzenia i przetwarzania tych danych. Program taki (często pakiet programów) nazywany jest „systemem zarządzania bazą danych” (ang. database management system, DBMS).

    Algorytm dotyczy poszukiwania danego elementu w nieposortowanym N-elementowym zbiorze. Problem wyszukiwania sprowadza się do wyznaczenia, na drodze przekształceń unitarnych, odpowiedniego indeksu określającego dany element w zbiorze.

    Zobacz też[]

  • informatyka kwantowa
  • komputer kwantowy
  • kryptologia kwantowa
  • Przypisy

    1. Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001

    Bibliografia[]

  • Mika Hirvensalo, Algorytmy kwantowe, WSiP, Warszawa 2004, ISBN 83-02-09155-3
  • Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003, ISBN 83-87674-57-5



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.02 sek.