Algorytm Deutscha-Jozsy – algorytm kwantowy utworzony przez Dawida Deutscha i Richarda Jozsa w 1992 poprawiany później przez Richarda Cleve, Artura Ekerta, Chiarę Macchiavello i Michele Mosca w 1998. Sam algorytm nie ma dużej wartości praktycznej – jest to jeden z pierwszych przykładów algorytmu kwantowego, który jest wykładniczo szybszy od każdego możliwego deterministycznego, klasycznego algorytmu. Algorytm Deutscha-Jozsy jest również deterministyczny, to znaczy zawsze zwraca poprawną odpowiedź.
Sformułowanie problemu W problemie Deutscha-Jozsy mamy "czarną skrzynkę", która tworzy funkcję taką że:
jest funkcją stałą (tj. wszystkie wartości ma równe 0 albo wszystkie wartości ma równe 1) lub
jest funkcją zbalansowaną. (tj. przypisuje wartości 0 oraz 1 tak, że jest tyle samo wartości 0 co 1).
Innymi słowy: "czarna skrzynka" generuje n bitów w taki sposób, że (1) wszystkie bity są równe 0 albo wszystkie bity są równe 1, (2) albo 0 i 1 są wygenerowane w równych ilościach, ale w dowolnej kolejności.
Zadanie polega na określeniu, czy jest stała, czy zbalansowana. Klasyczny algorytm Deterministyczny algorytm rozwiązujący problem Deutscha-Jozsy wymaga w najgorszym przypadku ewaluacji funkcji gdzie jest liczbą bitów. Aby udowodnić, że jest stała, potrzebne jest obliczenie funkcji w n/2+1 punktów. W najlepszym przypadku, jeżeli już pierwsze dwie sprawdzone wartości funkcji będą różne, to dowodzi, że jest zbalansowana. Konwencjonalny algorytm randomizowany wymaga wykonania ewaluacji funkcji, aby uzyskać poprawną odpowiedź z dużym prawdopodobieństwem (błąd z prawdopodobieństwem ). Aby na pewno uzyskać poprawną odpowiedź (algorytm deterministyczny), wymagane jest wyznaczenie wartości funkcji. Algorytm Deutscha-Jozsy zwraca zawsze poprawną odpowiedź już po jednej ewaluacji funkcji
Historia Algorytm Deutscha-Jozsy jest uogólnieniem wcześniejszej (1985) pracy Dawida Deutscha, która pokazuje rozwiązanie prostszego problemu. Konkretnie, mamy daną funkcję binarną, której dziedziną jest 1 bit: i pytamy, czy jest stała.
Algorytm proponowany początkowo przez Deutscha nie był właściwie deterministyczny. Algorytm dawał poprawną odpowiedź z prawdopodobieństwem 50%. W 1992, Deutsch i Jozsa wymyślili deterministyczny algorytm, który został uogólniony na przypadek funkcji, której argumentem jest bitów. W przeciwieństwie do aktualnego algorytmu, wymagał on dwukrotnego obliczenia wartości funkcji.
Późniejsze ulepszenia algorytmu Deutscha wprowadził Cleve (i inni), czego efektem było powstanie deterministycznego algorytmu, który wymaga jednokrotnej ewaluacji funkcji Temu algorytmowi nadano imiona Deutscha-Jozsy, aby uczcić innowacyjne zmiany wprowadzone przez tych naukowców.
Algorytm Deutscha-Jozsy stanowił inspirację dla algorytmu Shora i Grovera, dwóch najbardziej rewolucyjnych algorytmów kwantowych.
Dekoherencja Aby algorytm Deutscha-Jozsy działał, wyrocznia obliczająca z musi być wyrocznią kwantową, która nie dokonuje dekoherencji Wyrocznia w swoim wywołaniu musi również niszczyć informację o stanie
Algorytm Deutscha Algorytm Deutscha to szczególny przypadek algorytmu Deutscha-Jozsy. Sprawdza się w nim warunek: Jest to równoważne sprawdzeniu (gdzie to dodawanie modulo 2, na które można patrzeć jak na kwantową bramkę XOR zaimplementowaną jako kontrolowana bramka NOT) – jeśli wyjdzie zero, to jest stała, w przeciwnym przypadku nie jest stała.
Algorytm zaczyna się ustaleniem dwubitowego stanu A: i zaaplikowaniu przekształcenia Hadamarda do każdego kubitu, co daje stan B:
Dana jest kwantowa implementacja funkcji która przekształca w Zastosowanie tej funkcji do stanu B daje:
Ignorujemy ostatni bit i z dokładnością do globalnego czynnika fazowego (przemnożenia całości przez ) otrzymujemy stan:
Zastosujmy do każdego kubitu tego stanu bramkę Hadamarda; bramka ta tworzy następujące superpozycje stanów bazowych i :
Działając bramkami Hadamarda na każdy kubit otrzyma się stan:
wtedy i tylko wtedy, jeśli zmierzono 0, a wtedy i tylko wtedy, jeśli zmierzono 1. Wynika z tego, iż z prawdopodobieństwem równym 100% wiemy, czy jest stała, czy zbalansowana.
Algorytm Deutscha-Jozsy Ustalmy kubitowy stan A: (pierwsze bitów jest w stanie a ostatni ). Do każdego kubitu A stosowana jest bramka Hadamarda, która z każdego kubitu tworzy superpozycję; w wyniku czego powstaje stan B:
thumb|400px|Obwód kwantowy algorytmu Deutscha-Jozsy
Następnie, kwantowa wyrocznia przekształca stan w co daje:
Po podstawieniu w miejsce oraz ten wzór przekształca się do:
W tym momencie stan ostatniego kubitu może zostać zignorowany. Po zastosowaniu przekształceń Hadamarda ponownie na pierwszych bitach otrzyma się:
gdzie
Prawdopodobieństwo zmierzenia stanu wynosi:
Wyrażenie to przyjmuje wartość 1, jeśli funkcja jest stała (interferencja konstruktywna). Jeżeli zaś funkcja jest zbalansowana, to przyjmuje wartość 0 (interferencja destruktywna).
Zobacz też
algorytm kwantowy bramka kwantowa
Przypisy
Linki zewnętrzne Deutsch’s lecture about Deutsch algorithm (ang.) Implementation of the Deutsch-Jozsa algorithm in the Scala programming language (ang.)
Kategoria:Algorytmy kwantowe