Коротко и по существу.
1) Базовая точка отсчёта — машина Тьюринга и Church–Turing: любая «механическая» процедура вычисляема МТ; привычная мера сложности — время/память МТ. Расширение: «расширенная» (эффективная) теза Чёрча–Тьюринга (ECTT) утверждает, что любая разумно реализуемая модель вычислений симулируется вероятностной/детерминированной МТ с не более чем полиномиальным замедлением.
2) Параллельные модели (PRAM, многопроцессорные архитектуры, схемы):
- Что меняют:
- Вводят распределение ресурсов: время + число процессоров. Появляются новые «эффективные» классы, напр. $NC$ — задачи, решаемые в полилогарифмическое время на полиномиальном числе процессоров (т.е. эффективно параллелизуемые).
- Многие практические ускорения: для задач с независимыми подзадачами время снижается асимптотически (параллельный алгоритм вместо последовательного).
- Чем не превосходят классическую модель (формально):
- Не расширяют класс вычислимых функций — любой PRAM можно симулировать МТ; наоборот, МТ симулируется PRAM с полиномиальным/полилинейным накладным временем. Формально «полиномиальная» устойчивость: если задача в $P$, то она остаётся вычислимой; параллельная сила — это в основном перераспределение временной сложности в число процессоров.
- Существуют P‑полные задачи, которые, по общему мнению, не в $NC$ (то есть «внутренне последовательны»), так что параллелизм не даёт асимптотического выигрыша для всех задач.
- Практически важны дополнительные ограничения: синхронизация, коммуникация, пропускная способность, память — которые часто нивелируют теоретические выигрыши.
3) Квантовые компьютеры:
- Что меняют:
- Используют суперпозицию, запутанность и интерференцию, что даёт алгоритмические ускорения: пример — Шор даёт факторизацию за полиномиальное время (классически известные алгоритмы требуют субэкспоненциального/экспоненциального времени в наилучших известных вариантах), Гровер даёт квадратичное ускорение поиска: классический $O(N)$ → квантовый $O(\sqrt{N})$.
- Появляется класс $BQP$ (кванто-полиномиальное время) который, вероятно, больше $BPP$ (классич. вероятностный), то есть ECTT как «любая реалистичная модель симулируется с полином. замедливанием» подвергается сомнению.
- Чем не превосходят классическую машину в формальном смысле:
- Не расширяют понятие вычислимости: никакие задачи «невычислимые на МТ» не становятся вычислимыми на квантовом компьютере.
- Сложностные верхние границы: $BQP$ укладывается в большие классы, например $BQP\subseteq PP\subseteq PSPACE$ (т.е. квант можно симулировать классическим алгоритмом с экспоненциальным замедлением или в полиномиальной памяти).
- Не доказано и маловероятно (по текущим знаниям), что квант решает NP‑полные задачи за полиномиальное время; нет общепринятого результата, что $NP\subseteq BQP$.
- Практические ограничения: ошибка декогеренции, контроль над количеством кубитов, накладные расходы на ошибкоустойчивость (коды, коррекция) уменьшают реальный выигрыш.
4) Обобщающее сравнение и выводы:
- Что меняется концептуально: появляются дополнительные ресурсы (процессоры, квантовый параллелизм) и новые измерения сложности (глубина схемы, число процессоров, квантовые ресурсы), а значит меняются границы «эффективного» для конкретных задач (некоторые задачи получают асимптотическое ускорение).
- Что остаётся неизменным: классы вычислимости остаются теми же; большинство «фундаментальных» ограничений (некот. иерархии классов, P‑полнота, верхние границы вроде $BQP\subseteq PSPACE$) сохраняются; любые реальные модели в конечном счёте симулируются классической МТ (возможно с полиномиальным или экспоненциальным замедлением).
- Практический вывод: параллельные и квантовые модели расширяют инструментарий и меняют сложность конкретных задач (иногда радикально), но не опровергают формальную теорию вычислимости и лишь частично и условно (с инженерными ограничениями) изменяют представление об эффективности алгоритмов; фундаментальные теоретические границы остаются вопросом изучения (напр., соотношения $P$, $BQP$, $NP$ и др.).