Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Alexey Rovdo, Вы писали:
AR>>Алгоритм Шора опирается на квантовое дискретное преобразование Фурье (ДПФ), которое выполняется на квантовом компьютере как чередующиеся друг за другом преобразования Адамара над отдельными кубитами и операции условного поворота фазы в одном кубите ...
AVK>Отлично. Только вот какое это имеет отношение к:
AVK>Поэтому не путайте две разных вещи: "эмуляцию работы квантового
AVK>компьютера" и "моделирование квантового компьютера для конкретной
AVK>задачи с точно определенными параметрами".
AVK>Для пояснения таких различий тонкости алгоритма Шора совершенно не нужны.
Есть два понятия
эмуляция и
симуляция. Так вот отличие их как-раз в том, что в случае симуляции мы имеем дело с моделью (возможно, с приближенной моделью), а вот в случае эмуляции мы строим алгоритм (машину Тьюринга), который воспроизводит поведение эмулируемой системы (
Тезис Тьюринга-Черча утверждает, что любой алгоритм может быть выполнен машиной Тьюринга).
Существует масса
оговорок и пояснений к этой концепции. Долгое время искали математические задачи, которые не поддаются вычислению с помощью машины Тьюринга (т.е. не могут быть алгоритмизованы). Пытались сформулировать более сильное положение тезиса в виде:
Every function that can be physically computed can be computed by a Turing machine
(каждая функция, которая физически может быть вычислена, может быть вычислена на машине Тьюринга)
Считается, что это утверждение опровергнуто в работе: Willem Fouché, Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
Т.е. существуют функции, которые человек может вычислить, но машина Тьюринга не может.
PS: Что же касается квантовых алгоритмов, то я не представляю себе "эмуляцию" линейного преобразования в гильбертовых пространствах ...