The Budapest Quantum Optics Group

Previous Next


Quantum speedup of the Markov chain based search - an algorithmic approach of quantum walks

András Gilyén

(MTA Wigner RCP SZFI)

Time: Thu Oct 2 13:00:00 2014
Location: Building 1, Room 123

Szegedy Márió megmutatta, hogy hogyan lehet egy diszkrét idejű szimmetrikus bolyongás kvantumos verzióját definiálni úgy, hogy a kvantumos verzió négyzetesen gyorsabban "terjedjen". A módszert azóta többen továbbgondolták, sikerült tetszőleges reverzibilis Markov láncra általánosítani az eredményt. Az előadásban az alap módszer bemutatásán túl kitérek majd az algoritmikus alkalmazásokra is, különös tekintettel az egész módszer kiindulópontjául szolgáló Ambainis-féle elemkülönbözőségi algoritmusra. Ezzel az algoritmussal kapcsolatban felvázolok pár saját ötletet, ami az algoritmus meglehetősen komplikált implementációját egyszerűsíti.