Другие статьи

 


 

 

Quantum walks

 

Квантовые блуждания

 

Daniel Reitzner, Daniel Nagaj, Vladimir Buzek

 

 

 

This tutorial article showcases the many varieties and uses of quantum walks. Discrete time quantum walks are introduced as counterparts of classical random walks. The emphasis is on the connections and differences between the two types of processes (with rather different underlying dynamics) for producing random distributions. We discuss algorithmic applications for graph-searching and compare the two approaches. Next, we look at quantization of Markov chains and show how it can lead to speedups for sampling schemes. Finally, we turn to continuous time quantum walks and their applications, which provide interesting (even exponential) speedups over classical approaches.

 

 

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

 

 

ЧИТАТЬ ПОЛНОСТЬЮ