Считается (хотя не доказано), что квантовый компьютер может решать задачи экспоненциально большой сложности, в принципе недоступные никаким классическим вычислительным средствам.
В чём же принципиальное отличие квантового компьютера от классического?
Любая классическая машина использует алгоритмы, которые можно в меньшем масштабе проделать "в уме". То есть это действия, для выполнения которых в принципе не нужен "внешний мир", это "чистая логика" или "чистое мышление" (конечно, тут я утрирую; мои выводы верны только "в пределе").
Другое дело - квантовое вычисление. Это - чистой воды эксперимент (не мысленный - без реальной физической аппаратуры тут не обойтись). Получается, что есть задачи, чисто математические, которые можно решить только путём эксперимента. Другими словами, ответ надо спрашивать не у Разума (путём логических умозаключений), а у Природы (путём эксперимента). Математика становится экспериментальной наукой.
Такие вещи, как стирание границы между математикой и физикой, привлекают наше внимание к одному из тех вопросов, которые почему-то мало кто задаёт: каково происхождение сложности нашего мира? Мир представляется человеческому разуму неисчерпаемо богатым, и в то же время этот человеческий разум (в лице лучших своих представителей) пытается искать по возможности простые законы, или устои, на которых держится этот мир. То есть пытаются свести бесконечное разнообразие природы к каким-либо закономерностям, достаточно простым, чтобы они могли поместиться в голове. Представим себе, что это удалось, и найдены последние законы физики; тогда спрашивается, как же из простых законов получился сложный мир? Такие вопросы задаёт и обсуждает Дирак в статье "Отношение между математикой и физикой". Можно, конечно, сказать, что есть законы, т. е. уравнения движения (вполне определённые и простые), и есть начальные условия, на которые в принципе не накладывается никаких ограничений,и которые могут быть произвольно сложны. Так что сложность мира может проистекать из сложности начальных условий. Но тогда, даже зная точные уравнения движения, мы ничего ещё не знаем по-настоящему о мире: получается, что всё разнообразие явлений никак не выводится из законов (уравнений движения), а обусловлено начальными условиями, о которых мы ничего не знаем. Конечно, такая ситуация далека от идеалов познающего разума. Но давайте попробуем оценить мощь нашего разума оптимистичнее и представим себе, что мы достигли полного знания и о начальных условиях. То есть ачальные условия просты. Тогда откуда берётся сложность нашего мира??
Дирак отважился высказать ("пифагорейскую") гипотезу, что сложность берётся из математики, а именно, из свойств больших чисел. Представим возраст нашей Вселенной в атомных единицах; получится число типа 10^30 - 10^40; в планковских единицах - ещё больше. Представим себе, что вся информация о текущем состоянии Вселенной "зашифрована" в числе, выражающем её возраст. Тогда получается, что в самом начале Вселенная была проста, а потом стала очень сложной, причём законы (правила), по которым из возраста Вселенной выводится всё (средняя температура, плотность, расположение Галактик, результаты последнего тиража Спортлото и всё, что угодно), могут быть просты, а вся сложность Природы проистекает из сложности числа, выражающего возраст Вселенной. Причём само по себе число это вполне обозримо: в нём не так уж много десятичных знаков, и его вполне можно выписать на листочке бумаги. Но свойства этого числа (любого большого числа) неисчерпаемы человеческим разумом.
Что к этому можно добавить, отталкиваясь от идеи квантового компьютера?
1. Задача факторизации чисел - подтверждение тезиса о неисчерпаемой сложности больших чисел. То, что эта задача не решается классическими компьютерами, не доказано, но практика говорит, что скорее всего так и есть. Отличительные черты этой задачи: данное свойство числа (иметь такие-то и такие-то простые делители) очень просто формулируется (аналог простых законов природы), просто проверяется (разделить одно большое число на другое не представляет труда), но очень сложно его вычислить (то есть найти делители). Значит, большие числа действительно могут обеспечить сложность (разнообразие, неисчерпаемость) мира. (К квантовому компьютеру это не имеет прямого отношения, но это всплыло именно в связи с квантовым компьютером.)
2. Квантовое вычисление - это вопрос, задаваемый Природе, о какой-то математической задаче. Есть ли у Природы ответ? Если вся природа - это игра больших чисел, то в ней содержатся всевозможные свойства чисел (то есть вся математика), и главное - уметь задать вопрос. Для этого и нужен квантовый компьютер.
3. Конечно, вычисление конкретных событий из числа, представляющего возраст Вселенной, по своей сложности должно быть не по зубам классическим машинам. А квантовому компьютеру?
О чём ещё хотелось бы сказать:
а) об обратимых вычислениях;
б) как квантовый компьютер заставит нас лучше понимать квантовую механику.