Информация – не просто математическое понятие, она всегда имеет физическое воплощение, которое в традиционной теории информации следует законам классической физики, а в квантовой информатике – законам квантового мира.

Исторически точное время появления понятия информации в физике не определено. Важным событием в теории может считаться появление в 1871 г. парадокса, называемого «демон Максвелла». Демон Максвелла – это такое существо, которое отделяет быстрые молекулы от медленных (или горячие от холодных). Таким образом, его действия приводят к возникновению разницы температур без совершения какой-либо работы, что должно нарушать второй закон термодинамики.

Рис. 14. Демон Максвелла

На рис. 14 показано, что демон создает разницу давлений путем открывания перегородки только в том случае, ког­да к ней слева приближается молекул больше, чем справа. Пока демон способен хранить в памяти результаты наблюдений относительно молекул, данные действия полностью обратимы. Однако при этом голова (память) демона нагревается. Шаг необратимости заключается не в приобретении информации, а в ее потере при очистке демоном своей памяти.

Большую часть теории информации, как классической, так и квантовой, можно охватить, анализируя различные постановки основного вопроса: «Какое количество информационного ресурса нужно для выполнения данной задачи обработки информации?»

Трудно предположить, что размер транзистора или аналогичного элемента будет меньше 10^-8 см (диаметр атома водорода), а рабочая частота – больше 10¹⁵ Гц (частота атомных переходов). Рассмотрим, например, задачу о разложении целого числа х на простые множители. Очевидный способ – это попробовать разделить х на числа от 2 до . Если число х имеет n знаков в двоичной записи, то придётся перебрать ~ ~2^n/2 вариантов. Существует хитроумный алгоритм, решающий ту же задачу примерно за exp(cn^1/3) шагов (с = const). Даже в этом случае, чтобы разложить на множители число из миллиона знаков, не хватит времени жизни Вселенной.

Например, сколько шагов вычислений необходимо для отыскания простых сомножителей данного 300-значного числа? Лучший классический алгоритм требует примерно 5^.10²⁴ шагов или около 150 тыс. лет при скорости вычислений порядка терагерц (1 000 ГГц). Используя преимущества квантовых состояний, квантовый алгоритм требует 5^.10¹⁰ шагов и выполняется меньше секунды при той же скорости (рис. 15).

Рис. 15. Задача о разложении целого числа х на простые множители

Существует, однако, другой способ ускорить процесс вычисления для некоторых специальных классов задач. Например, интерференция света может использоваться для вычисления преобразования Фурье. Однако с увеличением размера моделируемой физической системы количество необходимых вычислительных операций растёт не слишком быстро – степенным, или, как принято говорить в теории сложности, полиномиальным образом. (Как правило, число операций пропорционально величине Vt, где V – объём, t – время.) Таким образом, классическая физика слишком «проста» с вычислительной точки зрения. Квантовая механика устроена в этом смысле гораздо интереснее. Рассмотрим, например, систему из n спинов. Каждый спин обладает двумя базисными состояниями (0 = «спин вверх» и 1 = «спин вниз»), а вся система имеет 2" базисных состояний |x₁,…,x_n> (каждая из переменных x₁,…,x_n принимает значение 0 или 1). Согласно общим принципам квантовой механики, возможными состояниями системы являются также их суперпозиция. Суперпозиция является новым математическим объектом – вектором в 2ⁿ-мерном комплексном пространстве. Квадрат модуля амплитуды равен вероятности обнаружить систему в базисном состоянии при измерении значений переменных x_j. (Отметим, что такое измерение разрушает суперпозицию.) Общее состояние системы (т.е. суперпозиция) – это вектор единичной длины в 2ⁿ-мерном комплексном пространстве. Изменение состояния за определённый промежуток времени описывается унитарной матрицей размера 2ⁿ x 2ⁿ. Если промежуток времени очень мал (, где J – энергия взаимодействия), то эта матрица устроена достаточно просто; каждый из её элементов можно легко вычислить, зная взаимодействие между спинами. Если же мы хотим узнать изменение состояния системы за большой промежуток времени, то придётся перемножать такие матрицы. Для этого требуется экспоненциально большое число операций.