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

Принимая этот момент во внимание, позвольте мне заявить следующее: предположим, что вселенная (1 + 1) — мерна, то есть имеет одно пространственное и одно временное измерение, и характеризуется космологической константой Λ. Тогда класс задач, которые мы в состоянии решить, входит в DSPACE (1/Λ): это класс задач, которые способна решить детерминистская машина Тьюринга с использованием ~1/Λ клеток ленты. Более того, он равен DSPACE (1/Λ), в зависимости от того, какие допущения вы готовы сделать о физике процесса. И уж во всяком случае он включает DSPACE (1/√Λ).

Во-первых и в-главных: почему мы не можем сделать больше чем DSPACE (1/Λ)?

Ну, если подходить к вопросу формально, позвольте мне определить модель вычисления, которое я назову машиной Тьюринга для космологической константы. В этой модели у нас есть бесконечная лента для машины Тьюринга, но теперь на каждом шагу по времени, между каждыми двумя клетками, существует независимая вероятность Λ того, что сформируется новая клетка с символом «*» в ней. На первый взгляд это кажется разумной моделью того, как Λ будет влиять на вычисление. Далее, если считывающая головка машины находится на некоторой клетке, то клетки на расстоянии 1/Λ от нее будут выглядеть удаляющимися от головки со скоростью в среднем одна клетка за шаг. Таким образом, вы не можете рассчитывать добраться до этих клеток хоть когда-нибудь. Всякий раз, когда вы будете делать шаг в их направлении, где-то в промежутке, вероятно, будет возникать новая клетка. (В этой модели скорость света можно считать равной одной клетке за шаг по времени.) То есть класс задач, которые вы будете в состоянии решить, обязательно войдет в DSPACE (1/Λ), поскольку вы всегда можете просто записать содержимое клеток в пределах расстояния 1/Λ от текущего положения головки и не обращать внимания на все остальные клетки ленты.

Но можем ли мы в реальности получить DSPACE (1/Λ)? Можно придумать очень простой алгоритм, позволяющий это сделать. А именно: представьте себе свои 1/Λ битов как стадо животных, которые постоянно норовят разойтись в разные стороны. Вам приходится непрерывно сдерживать их при помощи лассо, подобно этакому космологическому ковбою. Иными словами, ваша считывающая головка будет просто шагать вперед и назад по очереди, сжимая биты, которые постоянно норовят расползтись, и одновременно выполняя вычисления с ними. Далее, вопрос в том, сможете ли вы на самом деле удержать биты при помощи лассо за время О (1/Λ)? Я не писал для этого доказательства, но я не думаю, что это можно сделать за время меньшее чем ~1/Λ² при помощи стандартной считывающей головки машины Тьюринга (не обладающей, к примеру, способностью уничтожать клетки ленты). С другой стороны, вы определенно можете удержать ~1/√Λ битов за время О(1/Λ). Следовательно, вы можете вычислить DSPACE (1/√Λ). Я предполагаю, что это строгая оценка.

Второй интересный момент — то, что в пространстве двух и более измерений вы не получите той же самой картины. В двух измерениях радиус тоже удваивается за время, примерно равное 1/Λ, но даже для того, чтобы посетить все биты, которые нужно удерживать, здесь требуется время порядка 1/Λ². Так что мы можем спросить, существует ли что-то, что мы можем сделать за время 1/Λ на двумерной квадратной решетке, чего мы не можем сделать за время 1/Λ на одномерной ленте. Вы здесь имеете 1/Λ² пространство, и интуитивно кажется, что невозможно за время 1/Λ использовать больше чем 1/Λ клеток решетки; непонятно, однако, действительно ли это так. Разумеется, если хочется повеселиться, вы можете задать все те же вопросы для квантовой машины Тьюринга.

Еще о чем можно спросить, это о сложности запросов (query complexity) в этой модели. К примеру, допустим, что вы потеряли ключи и они могут при этом оказаться в любой точке вселенной. Если они находятся где-то в пределах вашего космологического горизонта, а ваше пространство одномерно, то вы в принципе можете их найти. Вы можете пройти все пространство в пределах своего горизонта за время O(1/Λ). Но уже при двух измерениях число локаций, которые вы в состоянии проверить прежде, чем большая часть наблюдаемой вселенной отступит за горизонт, сходно лишь с корнем квадратным от числа всех возможных локаций. Вы можете выбрать какое-то отдаленное место, переместиться туда, — и к моменту вашего возвращения область удвоится в размерах.

В квантовом случае есть выход: воспользоваться алгоритмом Гровера! Напомню: алгоритм Гровера позволяет нам провести поиск в базе данных, содержащей N записей, всего за √N шагов. На первый взгляд этого достаточно, чтобы просмотреть двумерную базу данных размером порядка наблюдаемой вселенной. Но есть одна проблема. Представьте, как на самом деле работает алгоритм Гровера. Шаги-запросы в нем чередуются с шагами увеличения амплитуд. Для этого нужно собрать все эти амплитуды в одном месте, так чтобы над ними можно было осуществить предложенную Гровером операцию отражения. Если представить себе квантового робота, который ищет что-то в двумерной базе данных размером √N × √N, то ему потребуется всего лишь √N итераций алгоритма Гровера, поскольку всего в базе содержится N записей, но каждая итерация займет √N времени, поскольку роботу придется собирать результаты всех запросов. Это проблема, поскольку мы при этом не получаем, кажется, никаких преимуществ по сравнению с классическим случаем. Следовательно, предложенное решение по поиску в базе данных размером со вселенную, судя по всему, работать не будет. Хотя при трех измерениях оно, кажется, все же даст нам некоторое преимущество. Если представить себе трехмерный жесткий диск, то длина стороны здесь будет равна N1/3, так что нам потребуется √N итераций по Гроверу, каждая из которых займет время N1/3; в итоге суммарное время составит N5/6. Это, по крайней мере, чуть лучше, чем N. По мере увеличения числа измерений полное время будет постепенно приближаться к √N. К примеру, если бы пространство имело 10 полноценных измерений, мы имели бы суммарное время операции, равное N12/22.

В работе, написанной мною в соавторстве с Андрисом Амбайнисом[188] много лет назад, мы показали, что можно воспользоваться рекурсивным вариантом алгоритма Гровера для поиска в двумерной решетке с затратами времени порядка √N log3/2 N. Для трех и более измерений порядок времени составит просто √N. Я могу высказать кое-какие самые базовые догадки о том, как работает наш алгоритм. При этом используется стратегия «разделяй и властвуй», то есть вы делите свою решетку на кучку меньших решеток. После этого вы можете и дальше делить эти меньшие решетки на еще более мелкие подрешетки и применять к каждой