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

В качестве первого шага можно сказать даже, что вы просматриваете каждую строку отдельно. Просмотр каждой строки занимает всего √N времени, а затем вы можете вернуться назад и собрать все результаты воедино. После этого можно провести поиск Гровера по √N строк, каждый проход займет время N1/4; полное время при этом получится равным N3/4.

Это первый способ решить задачу. Позже другие люди открыли более простой и удачный способ ее решения с использованием метода квантовых случайных блужданий. Сводится, однако, все к тому, что при наличии двумерной базы данных размером со вселенную мы реально можем просмотреть ее в поисках конкретного объекта прежде, чем он исчезнет за космологическим горизонтом. Можно провести только один такой поиск или, в лучшем случае, постоянное их число, но по крайней мере можно найти таким образом одну вещь, в которой мы отчаянно нуждаемся.

22. Задавайте вопросы!

Напомню: эта книга основана на курсе лекций, прочитанном мной в 2006 г. В последний день занятий, следуя прекрасной традиции, заведенной еще Ричардом Фейнманом, я предложил студентам задавать мне любые вопросы. У Фейнмана, по правилам, можно было спрашивать о чем угодно, за исключением политики, религии и итогового экзамена. В моем случае никакого экзамена не предусматривалось, и я даже не стал исключать политику и религию. В этой главе собраны некоторые из вопросов, которые мне тогда задали, вместе с моими ответами.

Студент: Задумываетесь ли вы об использовании теоретической информатики в физике? Может быть, она могла бы ограничить что-то или натолкнуть нас на какие-то новые физические теории? Как вы считаете, не можем ли мы с ее помощью открывать физические теории, которые обеспечат нам более мощные модели, чем квантовые вычисления?

Скотт: Можно ли считать BQP концом пути или нас ждут новые открытия? Фантастический вопрос, и мне хотелось бы, чтобы об этом думало как можно больше людей. Я в этом вопросе поведу себя как политик и не стану отвечать прямо, поскольку очевидный ответ звучит очень просто: «Не знаю». Мне кажется, вся идея науки состоит в том, что если мы не знаем ответа, мы не пытаемся высосать его из пальца или еще как. Мы стараемся обосновывать свои ответы. Так что пока все, что нам известно, согласуется с гипотезой о том, что квантовые вычисления — действительно конец пути. Грег Куперберг привел аналогию, которая мне понравилась. Он сказал, что есть люди, которые говорят: вот, мы перешли от классической механики к квантовой, какие нас еще ждут сюрпризы? Но, может быть, здесь как с Землей. Сначала люди считали, что Земля плоская, а затем, открыв ее шарообразность, говорили, что, может быть, она обладает топологией бутылки Клейна. Да, в заданном направлении есть неожиданности, но когда вы в них разобрались и их приняли, дальше в этом направлении уже может не быть дальнейших неожиданностей.

Земля сегодня такая же круглая, какой была при Эратосфене. Мы с вами говорили о странном свойстве квантовой механики, о том, что она кажется очень хрупкой теорией. Даже в общей теории относительности можно представить какие-то изменения и нововведения, скажем торсионные поля или еще что-то. Но в квантовой механике очень трудно что-то варьировать, в ней сразу же возникают противоречия. Разумеется, это никак не доказывает, что за ней ничего нет. В XVIII веке, вероятно, тоже казалось, что невозможно играть с евклидовой геометрией, не порождая противоречий. С другой стороны, сам факт, что нечто можно себе представить, не означает, что на проработку этого нечто следует тратить время. Итак, существуют ли реальные мысли о том, что могло бы стоять за квантовой механикой?

Ну, по квантовой гравитации имеются такие идеи, в которых, похоже, нет даже унитарности — даже вероятности там в сумме не дают единицы. Оптимист здесь воскликнул бы: «Ага! Мы нашли что-то за пределами квантовой механики!» А пессимист сказал бы, что все эти теории (в их нынешнем виде) полная чепуха, и когда специалисты по квантовой гравитации разберутся наконец в том, чем занимаются, унитарность вернется. Еще есть явления, которые, кажется, немного меняют наши представления о квантовой механике. Среди них проблема исчезновения информации в черной дыре:

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

Проблема в том, что, оказавшись внутри черной дыры, вы даже не приближаетесь к горизонту событий. Вы направляетесь прямо в сингулярность. С другой стороны, если черная дыра должна постепенно выпускать из себя информацию, то представляется, что эта информация должна каким-то образом находиться на горизонте событий или совсем рядом с ним. Это особенно верно, поскольку мы знаем, что количество информации в черной дыре пропорционально площади ее поверхности. Но вы, с вашей точки зрения, находитесь где-то далеко внутри. Так что создается впечатление, что информация должна находиться в двух местах одновременно.

Во всяком случае, одно из предположений, которые выдвигают такие люди, как Герард т'Хоофт и Ленни Сасскинд, состоит в том, что да, информация действительно «дублируется». На первый взгляд, это нарушение унитарности, в первую очередь теоремы о запрете клонирования. Но, с другой стороны, как можно увидеть обе копии этой информации? Если вы внутри черной дыры, вы никогда не увидите внешнюю копию. Можно представить себе, что если кому-то отчаянно захочется выяснить, нарушается ли здесь теорема о запрете клонирования, — настолько отчаянно, что он готов будет пожертвовать ради этого своей жизнью, — то можно сначала измерить внешнюю копию, а затем прыгнуть в черную дыру и поискать там копию внутреннюю. Но вот что забавно: кое-кто уже успел посчитать, что произойдет, если попытаться так сделать; выяснилось, что придется очень долго ждать, пока информация выйдет наружу в виде излучения Хокинга, и к тому времени, когда одна копия выйдет наружу посредством излучения Хокинга, другая уже достигнет сингулярности. Такое впечатление, что какой-то цензор не позволяет вам увидеть обе копии этой информации одновременно. Так что с точки