Quantum walks
Квантовые блуждания
Daniel Reitzner, Daniel Nagaj, Vladimir Buzek
В данной обзорной статье представлено все многообразие взглядов и подходов к феномену квантовых блужданий. Теория квантовых блужданий с дискретным временем является развитием классической теории случайных блужданий. Сделан акцент на сходстве и различиях между этими двумя типами процессов (имеющих в своей основе существенно разную динамику), что необходимо для построения распределения случайных величин. Мы обсудим алгоритмы поиска на графе и сравним оба подхода. Далее, рассмотрим квантование цепей Маркова и покажем, как оно приводит к ускорению на выборочных схемах. В заключение мы перейдем к квантовым блужданиям с непрерывным временем и их приложениям, дающим интересный (даже - экспоненциальный) рост по сравнению с классическим подходом.