Квантовая сортировка - Quantum sort - Wikipedia

А квантовая сортировка есть ли алгоритм сортировки который работает на квантовый компьютер. Любой алгоритм квантовой сортировки, основанный на сравнении, потребует не менее шаги[1] что уже достижимо классическими алгоритмами. Таким образом, для этой задачи квантовые компьютеры ничем не лучше классических. Однако в разновидностях с ограниченным пространством квантовые алгоритмы превосходят свои классические аналоги.[2]

Рекомендации

  1. ^ Høyer, P .; Neerbek, J .; Ши, Ю. (2001). «Квантовые сложности упорядоченного поиска, сортировки и различимости элементов». 28-й Международный коллоквиум по автоматам, языкам и программированию. С. 62–73. arXiv:Quant-ph / 0102078. Дои:10.1007/3-540-48224-5_29.
  2. ^ Клаук, Хартмут (2003). «Квантовые компромиссы во времени и пространстве для сортировки». Материалы тридцать пятого ежегодного симпозиума ACM по теории вычислений. arXiv:Quant-ph / 0211174. Дои:10.1145/780542.780553.