Seminar: Quantum walks and their exceptional configurations

Prelegent: 

Nikolay Nahimov

Data: 

22/02/2017 - 13:00

Błądzenie kwantowe to odpowiednik kwantowe błądzenia losowego. Są one przydatne przy projektowaniu algorytmów kwantowych, które przewyższają ich klasyczne wersje dla różnych problemów wyszukiwania. Większość wyników rozważa przestrzeń poszukiwań zawierającą tylko jeden wyraźny element. Pokażemy, że jeśli przestrzeń poszukiwań zawiera więcej niż jeden zaznaczony element kwantowe przyśpieszenie może zniknąć. Dokładniej, przeanalizujemy wyszukiwanie kwantowe na ogólnych grafach i pokażęmy szeroką klasę konfiguracji zaznaczonych wierzchołków, dla których wyszukiwanie według odległości kwantowej nie ma przewaagi nad klasyczną. Wystąpienie zawiera wprowadzenie do dyskretnego błądzenia kwntowego oraz wprowadza pojęcie konfiguracji wyjątkowych.Naszkicowane zostaną również zastosowania algorytmiczne.