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

Квантовое блуждание — квантовый аналог классического случайного блуждания. Как и в случае классических случайных блужданий, квантовые блуждания допускают формулировки как в дискретном, так и в непрерывном времени.

Квантовое блуждание используется при разработке рандомизированных алгоритмов. Для решения некоторых задач оракула квантовые блуждания обеспечивают экспоненциальное ускорение по сравнению с любым классическим алгоритмом.[1] Квантовые блуждания также обеспечивают полиномиальное ускорение по сравнению с классическими алгоритмами для решения многих практических задач, таких как задача различения элементов, [2] задача нахождения треугольника, и вычисление деревьев NAND. Хорошо известный алгоритм Гровера также можно рассматривать как алгоритм квантового блуждания.

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

Смотри также

• Квантовый эффект Зенона

Примечания

1. A. M. Childs, L. J. Schulman, and U. V. Vazirani, Quantum algorithms for hidden nonlinear structures, Proc. 48th IEEE Symposium on Foundations of Computer Science, pp. 395–404, 2007, arXiv:0705.2784.
2. Andris Ambainis, Quantum walk algorithm for element distinctness, SIAM J. Comput. 37 (2007), no. 1, 210–239, arXiv:quant-ph/0311001, preliminary version in FOCS 2004.