Так что даже
суперкомпьютеры будугцего не смогут регпать вычислительные задачи, имеюгцие
экспоненциальную сложность. Рассмотрим, например, задачу о
разложении целого числа х на простые множители. Очевидный способ —
это попробовать разделить х на числа от 2 до ^/х. Если число х имеет
п знаков в двоичной записи, то придётся перебрать ~ ^ ~ 2"/2
вариантов. Сугцествует хитроумный алгоритм, регпаюгций ту же задачу
примерно за ехр(сгг"^'^) гпагов (с = const). Даже в этом случае, чтобы
разложить на множители число из миллиона знаков, не хватит времени
жизни Вселенной. (Возможно, есть и более эффективные алгоритмы,
но от экспоненты, по-видимому, избавиться не удастся. )
Сугцествует, однако, другой способ ускорить процесс вычисления
для некоторых специальных классов задач. Дело в том, что обычные
компьютеры не используют всех возможностей, предоставляемых
природой. Это утверждение может показаться слигпком очевидным: в
природе есть множество процессов, совергпенно непохожих на операции с
нулями и единицами. Можно попытаться использовать эти процессы
'Бэббидж начал работу над проектом «аналитической машины» в 1833 году. Пренолагалось, что, в отличие от уже существовавших в то время
вычислительных устройств, это будет универсальный компьютер. Бэббидж посвятил разработке
компьютера всю жизнь, но ему так и не удалось осуществить свою мечту. (Более
простая, но неуниверсальная «разностная мащина» была построена частично, но
проект был вполне реалистичен— в 1991 году мащина была полностью воспроизведена
по чертежам Бэббиджа. )
10 Введение
для создания аналоговой вв1числителвной машинв:. Например,
интерференция света может иснолвзоватвся для вв1числения преобразования
Фурье. Однако в большинстве случаев выигрыш в скорости не является
принципиальным, т. е. слабо зависит от размера устройства.
Причина
заключается в том, что уравнения классической физики (например,
уравнения Максвелла) эффективно решаются на обычном цифровом
компьютере. Что значит эффективно? Вычисление интерференционной
картины может занять в миллионы раз больше времени, чем реальный
эксперимент, потому что скорость света велика, а длина волны мала. Однако с увеличением размера моделируемой физической системы
количество необходимых вычислительных операций растёт пе слишком
быстро — степенным, или, как принято говорить в теории сложности,
полиномиальным образом. (Как правило, число операций пропорцио-
нальпо величине Vt, где V — объём, at — время. ) Таким образом,
классическая физика слишком «проста» с вычислительной точки зрения. Квантовая механика устроена в этом смысле гораздо интереснее. Рассмотрим, например, систему из п снинов. Каждый снин обладает
двумя базисными состояниями (О = «снин вверх» и 1 = «снин вниз»), а
вся система имеет 2" базисных состояний \xi, . . . , х„) (каждая из
неременных xi,... ,x„ принимает значение О или 1). Согласно общим
принципам квантовой механики, возможными состояниями системы
являются также суперпозиции вида ^^ ^ Cj;^^ j;^ |ж1, . . . , ж„), где
Сж1,... ,ж„ — комплексные числа, называемые амплитудами.