Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
двух гигантов показана на рис. 2.
В основе классической теории информации лежит определение непосредственно
информации. Здесь уместно следующее предупреждение. Как только теория
пытается из термина "информация" вытеснить, насколько это возможно,
естественный смысл этого понятия, она больше не может оценить всю полноту
этого слова в его повседневном понимании и видит в нем не больше, чем
физика элементарных частиц видит в понятии "очарование". Пока будем
считать понятие "информация" абстрактным. Его точное определение будет
дано в разделе 2.1. Большинство понятий теории информации относится к
1940 году - времени
12
Глава 1
Рис. 2. Зависимость между квантовой механикой и теорией информации.
Данная диаграмма не претендует на роль определения, поскольку
расположение элементов в некотором роде субъективно. Однако она указывает
на многие связи, описанные в статье
появления основополагающей работы Шеннона (Slepian 1974 г.). Данные о
том, что информация может быть преобразована из одной формы в другую,
кратко изложены и квантифицированы в теореме бесшумного кодирования
Шеннона (Shannon's noiseless coding theorem).
Эта теорема количественно определяет средства, необходимые для хранения
или передачи заданного объема информации. Шеннон также рассмотрел
фундаментальную задачу о связи при помехах и вывел основную теорему
Шеннона (см. раздел 2.4), которая является важным достижением
классической теории информации. Связь без ошибок даже
Введение
13
при помехах осуществляется посредством "кодов, исправляющих ошибки",
изучением которых по праву занимается одна из ветвей математики. Журнал
IEEE Transactions on Informations Theory практически полностью посвящен
разработке и анализу кодов, исправляющих ошибки. Новаторские работы в
этой области были выполнены Golay (1949) и Hamming (1950).
Основные положения информатики появились примерно в то же время, что и
теория информации Шеннона. Данный факт не является совпадением. Можно
утверждать, что Алан Тьюринг (Alan Turing 1912-1954) - отец информатики,
а пророк ее - Чарльз Бэббидж (Charles Babbage 1791-1871). Бэббидж
определил большинство существенных элементов современного компьютера,
хотя в то время еще не существовало технологий для осуществления его
идей. Прошло столетие и Тьюринг усовершенствовал "аналитическую машину"
Бэббиджа, предложив в середине 30-х годов универсальную машину Тьюринга.
Гений Тьюринга (см. Hodges 1983) заключается в том, что он точно
определил возможности вычислительной машины и в еще большей степени, чем
Бэббидж, подчеркивал роль программирования или, другими словами,
программного обеспечения. В своих исследованиях Тьюринг опирался на
работы таких великих математиков, как Дэвид Гильберт и Курт Гедель. С
1890-х по 1930-е годы Гильберт подчеркивал важность постановки
фундаментальных вопросов о природе математики. Вопрос: "Справедливо ли
данное математическое утверждение?" он предлагал заменить вопросом:
"Можно ли данным способом в принципе опровергнуть или доказать любое
математическое утверждение?" Ответ был неизвестен, однако Гильберт, как и
большинство математиков, чувствовал, что математика является,законченной
наукой и такие предположения, как, например, предположение Гольдбаха о
том, что любое четное число можно представить как сумму двух простых
чисел, могут быть либо доказаны, либо опровергнуты. Хотя логическая
последовательность доказательств может быть и неизвестна.
Гедель опровергнул эти идеи, доказав существование неразрешимых
математических утверждений, т. е. утверждений, которые нельзя ни
доказать, ни опровергнуть. Следующий важный вопрос был связан с
опознаванием подобных утверждений. Прогресс математики всегда зависел от
гибкости воображения, однако при суждении задним числом математические
доказательства выводятся автоматически, где каждый последующий шаг
неизбежно следует из предыдущего. Гильберт
14
Глава 1
задавался вопросом, можно ли заменить эту "неизбежность" каким-либо
автоматическим процессом. Другими словами, существует ли универсальный
математический метод, позволяющий доказать истинность или ложность любого
математического утверждения? После Геделя вопрос Гильберта был
переформулирован. Теперь он заключался в доказательстве не истины, а
разрешимости, и именно этим вопросом занимался Тьюринг.
По словам Ньюмана, смелость идеи Тьюринга заключалась в изобретении
бумажной перфоленты с символической логикой. Во время поиска
автоматических действий для разрешения математических вопросов Тьюринг
придумал полностью механическое устройство, являющееся фактически всем
известной пишущей машинкой (рис. 7. стр. 39). Особенность машины Тьюринга
заключалась в том, что, с одной стороны, это была машина высокого уровня,
предназначенная для решения сложных математических задач, с другой
стороны, она была достаточно проста и могла быть подвергнута подробному
анализу. Тьюринг использовал свою машину как теоретическую конструкцию
