Оглавление
Скотт Ааронсон. Квантовые вычисления со времен Демокрита
Предисловие
А теперь – настоящее предисловие
Что нового
Благодарности
1. Атомы и пустота
2. Множества
Пустое множество
Правила логики первого порядка
Аксиомы Пеано для неотрицательных целых чисел
Аксиомы теории множеств
3. Гёдель, Тьюринг и все-все-все
Машины Тьюринга
Дополнительный бонус
Упражнение
Дополнительная литература
4. Разум и машины
Загадки
Ответы на упражнения из предыдущей главы
5. Палеосложность
Дополнительная литература
Загадка 1 из предыдущей главы
Загадка 2 из предыдущей главы
6. P, NP и все-все-все
Живой уголок
Задачи
7. Случайность
Загадки
8. Крипто
Ответы на загадки из главы 7
Крипто
Генераторы псевдослучайных последовательностей
Односторонние функции
Криптография с открытым ключом
9. Квант
Вероятность меньше 0 %?
Смешанные состояния
Правило возведения в квадрат
Действительные и комплексные числа
Линейность
Дополнительная литература
10. Квантовые вычисления
Развычисления
Отношения с классическими классами сложности
Квантовые вычисления и NP-полные задачи
Квантовые вычисления и многомировая интерпретация
Дополнительная литература
11. Пенроуз
Открываем черный ящик
Рискну утверждать очевидное
Все на поезд всеохватной квантовой гравитации!
12. Декогеренция и скрытые переменные
В пропасть
История 1. Декогеренция
Декогеренция и второе начало термодинамики
История 2. Скрытые параметры
Уйма запрещающих теорем
Примеры теорий со скрытыми параметрами
Теория потока
Теория Шрёдингера
Механика Бома
13. Доказательства
Что такое доказательство?
Вероятностные доказательства
Доказательства с нулевым разглашением
Вероятностно проверяемое доказательство
Сложность моделирования теорий со скрытыми параметрами
14. Насколько велики квантовые состояния?
15. Скептики о квантовых вычислениях
16. Обучение
Загадка
17. Интерактивные доказательства, нижняя оценка сложности схемы и многое другое
Интерактивные доказательства
18. Поиграем с антропным принципом[152]
19. Свобода воли
Парадокс Ньюкома
20. Путешествия во времени
21. Космология и вычислительная сложность
22. Задавайте вопросы!
Отрывок из книги
«Квантовые вычисления со времен Демокрита» – достойный кандидат на звание самой странной книги, когда-либо опубликованной издательством Кембриджского университета. Ее необычность начинается с названия, которое загадочным образом не объясняет, о чем, собственно, говорится в этой книге. Быть может, это очередной учебник по квантовым вычислениям – модной области науки на стыке физики, математики и информатики, которая уже лет двадцать обещает миру новый тип компьютера, но пока не создала реального устройства, способного на что-нибудь более впечатляющее, чем разложение 21 на множители 3 × 7 (правда, с высокой вероятностью)? Если так, то что добавит именно эта книга к десяткам других, в которых уже изложены основы теории квантовых вычислений? Или, может быть, эта книга – наивная попытка связать квантовые вычисления с историей древнего мира? Но какое отношение может иметь Демокрит – древнегреческий философ-атомист – к книге, содержание которой по крайней мере наполовину было бы откровением для ученых даже в 1970-е годы, не говоря уже о IV веке до н. э.?
Теперь, когда я прочел эту книгу, я должен признать, что поистине блестящий и невыразимо оригинальный взгляд автора на всё – от квантовых вычислений (заявленных в заголовке) до теорем Гёделя и Тьюринга, от вопроса о соотношении между P и NP до интерпретации квантовой механики, от искусственного интеллекта до парадокса Ньюкома и проблемы исчезновения информации в черной дыре – вынес мне мозг и заставил полностью пересмотреть свою картину мира. Так что если кто-то просматривает эту книгу в магазине, то я несомненно посоветовал бы этому человеку немедленно ее приобрести. Я также хотел бы добавить к этому, что автор необычайно хорош собой.
.....
В главе 12 рассматривается то, что я считаю главной концептуальной проблемой квантовой механики: не то, что будущее неопределенно (а кому до этого есть дело?), но то, что прошлое также неопределенно! Я разбираю две очень разные реакции на эта проблему: во-первых, популярное среди физиков обращение к декогеренции и «эффективной стреле времени» на базе Второго начала термодинамики; и во-вторых, «теории со скрытыми параметрами», такие как теория волны-пилота (она же теория де Бройля – Бома). Я считаю, что теории со скрытыми параметрами, даже если они будут отвергнуты, ставят перед нами необычайно интересные математические вопросы.
В оставшейся части книги рассматривается приложение всего изложенного выше к тем или иным серьезным, захватывающим или противоречивым вопросам математики, информатики, философии и физики. В этих главах значительно больше, чем в начальных, уделено внимание недавним исследованиям, в основном в области квантовой информации и вычислительной сложности, но также в области квантовой гравитации и космологии; мне представляется, что появляется некоторая надежда пролить свет на эти «коренные вопросы». Поэтому мне кажется, что именно последние главы устареют первыми! Несмотря на кое-какие не слишком существенные логические завязки, в первом приближении можно сказать, что эти последние главы можно читать в любом порядке.
.....
