Читать онлайн «Классические и квантовые вышисления»

Автор Андре Мари де Шенье

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