Quantum walks and their exceptional configurations

Prelegent: 

Nikolay Nahimov, University of Latvia

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.

Autor: Jarosław Miszczak | Data utworzenia: 15.02.2017 | Ostatnia modyfikacja: 18.06.2018

Historia zmian

Data aktualizacji: 18/06/2018 - 09:26; autor zmian: ()

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.
Data aktualizacji: 22/02/2017 - 12:26; autor zmian: (sebastian@iitis.pl)
Data aktualizacji: 21/02/2017 - 14:34; autor zmian: (sebastian@iitis.pl)
Data aktualizacji: 15/02/2017 - 09:23; autor zmian: ()
Data aktualizacji: 25/01/2017 - 11:42; autor zmian: ()

Quantum walks are quantum counterparts of classical random walks.
They have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems.
Most of the results, however, consider a search space containing a single marked element only.
We show that if the search space contains more than one marked element the quantum speed-up may disappear.
More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk has no speed-up over the classical exhaustive search.

In my talk I'm going to give an introduction to discreet-time coined quantum walk model,
introduce the concept of the exceptional configurations, i.e. configurations of two or more marked vertices for which probability to be found does not grow, and prove some generic theorems, such as the upper bound on the probability of finding a marked vertex. I will also sketch some possible algorithmic applications of the found phenomenon.
Data aktualizacji: 25/01/2017 - 11:41; autor zmian: ()

Quantum walks are quantum counterparts of classical random walks.
They have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems.
Most of the results, however, consider a search space containing a single marked element only.
We show that if the search space contains more than one marked element the quantum speed-up may disappear.
More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk has no speed-up over the classical exhaustive search.

In my talk I'm going to give an introduction to discreet-time coined quantum walk model,
introduce the concept of the exceptional configurations, i.e. configurations of two or more marked vertices for which probability to be found does not grow, and prove some generic theorems, such as the upper bound on the probability of finding a marked vertex. I will also sketch some possible algorithmic applications of the found phenomenon.
Data aktualizacji: 23/01/2017 - 19:55; autor zmian: Piotr Gawron (gawron@iitis.pl)

Quantum walks are quantum counterparts of classical random walks.
They have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems.
Most of the results, however, consider a search space containing a single marked element only.
We show that if the search space contains more than one marked element the quantum speed-up may disappear.
More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk has no speed-up over the classical exhaustive search.

In my talk I'm going to give an introduction to discreet-time coined quantum walk model,
introduce the concept of the exceptional configurations, i.e. configurations of two or more marked vertices for which probability to be found does not grow, and prove some generic theorems, such as the upper bound on the probability of finding a marked vertex. I will also sketch some possible algorithmic applications of the found phenomenon.
Data aktualizacji: 23/01/2017 - 19:55; autor zmian: Piotr Gawron (gawron@iitis.pl)

Quantum walks are quantum counterparts of classical random walks


They have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems.
Most of the results, however, consider a search space containing a single marked element only.
We show that if the search space contains more than one marked element the quantum speed-up may disappear.
More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk has no speed-up over the classical exhaustive search.

In my talk I'm going to give an introduction to discreet-time coined quantum walk model,
introduce the concept of the exceptional configurations, i.e. configurations of two or more marked vertices for which probability to be found does not grow, and prove some generic theorems, such as the upper bound on the probability of finding a marked vertex. I will also sketch some possible algorithmic applications of the found phenomenon.
Data aktualizacji: 23/01/2017 - 19:54; autor zmian: Piotr Gawron (gawron@iitis.pl)

Quantum walks are quantum counterparts of classical random walks


They have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems.
Most of the results, however, consider a search space containing a single marked element only.
We show that if the search space contains more than one marked element the quantum speed-up may disappear.
More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk has no speed-up over the classical exhaustive search.

In my talk I'm going to give an introduction to discreet-time coined quantum walk model,
introduce the concept of the exceptional configurations, i.e. configurations of two or more marked vertices for which probability to be found does not grow, and prove some generic theorems, such as the upper bound on the probability of finding a marked vertex. I will also sketch some possible algorithmic applications of the found phenomenon.
Data aktualizacji: 22/01/2017 - 13:05; autor zmian: Piotr Gawron (gawron@iitis.pl)

Quantum walks are quantum counterparts of classical random walks.
They have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems.
Most of the results, however, consider a search space containing a single marked element only.
We show that if the search space contains more than one marked element the quantum speed-up may disappear.
More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk has no speed-up over the classical exhaustive search.

In my talk I'm going to give an introduction to discreet-time coined quantum walk model,
introduce the concept of the exceptional configurations, i.e. configurations of two or more marked vertices for which probability to be found does not grow, and prove some generic theorems, such as the upper bound on the probability of finding a marked vertex. I will also sketch some possible algorithmic applications of the found phenomenon.
Data aktualizacji: 20/01/2017 - 12:28; autor zmian: Piotr Gawron (gawron@iitis.pl)