Квантовые вычисления со времен Демокрита - Скотт Ааронсон (2013)

Этот обмен репликами служит, по существу, краеугольным камнем всей книги. Одной из тем для моих рассуждений будет то, что квантовая механика снабжает, судя по всему, и Разум, и Чувства новыми аргументами в их 2400-летнем споре, хотя по-прежнему (я так считаю) не обеспечивает чистой победы ни для одной стороны.

В главах 2 и 3 я перехожу к обсуждению самой глубокой из всех имеющихся у нас областей знания, совершенно намеренно не зависящей от «грубых фактов» об окружающем мире, а именно математики. Даже здесь что-то внутри меня (и, как я подозреваю, внутри многих других компьютерщиков!) с подозрением относится к тем разделам математики, которые несут на себе явный отпечаток физики, – это, к примеру, дифференциальные уравнения в частных производных, дифференциальная геометрия, группы Ли и что угодно еще, выглядящее «слишком непрерывным». Поэтому я начинаю с самых «нефизических» разделов математики, известных на данный момент, – с теории множеств, логики и вопросов вычислимости. Я рассказываю о великих открытиях Кантора, Фреге, Гёделя, Тьюринга и Коэна, которые помогли нанести на карту контуры математических рассуждений как таковых и которые – в процессе демонстрации причин, по которым всю математику невозможно свести к фиксированному «механическому процессу», – продемонстрировали также, сколь значительную часть ее все же можно свести к такому процессу; заодно удалось прояснить, что, собственно, представляет собой сей «механический процесс». Поскольку я никак не могу от этого удержаться, в главе 4 я углубляюсь в давний спор о том, не сводится ли работа человеческого разума к «устоявшимся механическим процессам». Я стараюсь излагать позиции сторон в этом споре как можно беспристрастнее (хотя мои собственные пристрастия, несомненно, тоже заметны).

В главе 5 представлена молодая сестра теории вычислимости – теория вычислительной сложности, которая в дальнейшем играет в книге центральную роль. Я пытаюсь проиллюстрировать, в частности, как вычислительная сложность позволяет нам методично брать «глубокие философские загадки» о пределах человеческого знания и превращать их во «всего лишь» безумно сложные нерешенные математические задачи, в которых, по мнению некоторых, отражается большая часть того, что нам хотелось бы знать! Невозможно придумать лучший пример такого превращения, чем так называемая проблема перебора, или вопрос о равенстве классов сложности P и NP, о котором я расскажу в главе 6. Затем, в качестве разогрева перед квантовыми вычислениями, в главе 7 будут рассмотрены многочисленные применения классического понятия случайности – как в теории сложности вычислений, так и в других областях жизни; а глава 8 объяснит, как при помощи идей из области вычислительной сложности начиная с 1970-х гг. удалось по-настоящему революционизировать теорию и практику криптографии.

Все это – всего лишь подготовка сцены для самой тяжелой части книги – главы 9, в которой представлен мой взгляд на квантовую механику как «обобщенную теорию вероятностей». В главе 10 объясняются основы моей собственной научной области – квантовой теории вычислений, которую можно кратко определить как соединение квантовой механики и теории вычислительной сложности.

В качестве «награды» за упорство глава 11 предлагает критический разбор идей сэра Роджера Пенроуза, убежденного, как известно, в том, что мозг – это не просто квантовый компьютер, но квантовый гравитационный компьютер, способный решать невычислимые по Тьюрингу задачи, и что это или что-то подобное можно показать при помощи теоремы Гёделя о неполноте. Указать на проблемы и недостатки этих идей проще простого, и я это делаю, но еще интереснее, как мне кажется, задаться вопросом о том, не скрываются ли все же в рассуждениях Пенроуза крупицы истины.