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

а в последнем — «забудет», и ей придется выбирать случайным образом между i и j. Как обычно повторив этот «фокус» полиномиальное число раз, можно сделать вероятность ошибки экспоненциально малой. (Обратите внимание: для этого не требуется наблюдать более чем одну траекторию скрытого параметра; все повторы могут делаться в пределах одной-единственной траектории.)

При каких же допущениях касательно теории скрытого параметра все это работает? Первое сводится к тому, что если у вас есть группа кубитов и вы применяете вентиль Адамара к одному из них, то вы должны получить лишь переход между базисными состояниями скрытого параметра, которые различны в первом кубите.

Заметьте, что это допущение сильно отличается от требования «локальности» теории скрытых параметров в смысле, о котором обычно говорят физики, и слабее его. Никакая теория скрытых параметров не может быть локальной. Это доказал один парень по фамилии Белл.

А второе допущение состоит в том, что теория скрытых переменных «устойчива» к небольшим ошибкам в унитарных матрицах и квантовых состояниях. Это допущение необходимо для того, чтобы разумным образом определить класс сложности DQP.

Как мы уже видели, DQP включает в себя как BQP, так и задачу об изоморфности графов. Но интересно, что по крайней мере в модели с черным ящиком DQP не содержит NP-полных задач. Более формально, существует оракул A, такой, что NPA ⊄ DQPA. Доказательство этого утверждения формализует интуитивный вывод о том, что даже если скрытый параметр вовсю прыгает вокруг квантового стога сена, вероятность того, что он когда-либо отыщет иголку, исчезающе мала. Оказывается, в модели со скрытыми параметрами можно просмотреть неупорядоченный список размера N при помощи N1/3 запросов вместо √N запросов, которые получаются из алгоритма Гровера; несколько лучше, но и эта величина по-прежнему экспоненциальна. В общем, суть в том, что даже DQP имеет серьезные ограничения по вычислительной сложности.

14. Насколько велики квантовые состояния?

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

Лично я придерживаюсь немного другой точки зрения: теоретическая информатика — посредник между физическим миром и платоновым миром идей. С учетом этого название «теоретическая информатика» как минимум неточно; может быть, лучше было бы называть ее «количественной эпистемологией». Это своего рода изучение способности конечных существ, таких как мы с вами, к познанию математических истин. Надеюсь, мне удалось отчасти показать вам это.

Как примирить это с представлением о том, что любое реальное применение компьютера должно быть основано на физике? Не поменяются ли при этом местами физика и информатика?

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

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

Грубо говоря, многомировая интерпретация ответила бы: «Абсолютно точно». Это позиция, которую Дэвид Дойч защищает очень красноречиво; но если различные вселенные (или компоненты волновой функции), используемые в алгоритме Шора, не присутствуют здесь физически, то где же было разложено число на простые множители?

Мы говорили также о механике Бома, которая говорит «да», но при этом уточняет, что один компонент вектора «более реален», чем остальные. Далее, есть еще подход, который раньше называли копенгагенским, а сегодня чаще зовут байесовским, информационно-теоретическим и множеством других имен.

В байесовском подходе квантовое состояние — это экспоненциально длинный вектор амплитуд в более или менее том же смысле, в каком классическое распределение вероятности есть экспоненциально длинный вектор вероятностей. Если вы возьмете монетку и бросите ее 1000 раз, вы бы получили некоторое множество из 21000 возможных исходов, — но ведь мы не готовы по этой причине рассматривать все эти исходы как физически реальные!

Здесь я должен пояснить, что я не говорю о формализме квантовой механики; с этим согласны (почти) все. Я спрашиваю, описывает ли квантовая механика реальный «объект экспоненциального размера», существующий в физическом мире. Так что, принимая копенгагенский подход, вы заранее объявляете, что этот экспоненциально длинный вектор находится у нас «только в головах».

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

Теперь, когда у нас появились квантовые вычисления, можем ли мы привлечь интеллектуальный потенциал теории вычислительной сложности к решению подобных вопросов? Мне жаль вас разочаровывать, но мы не можем рассудить этот спор при помощи вычислительной сложности. Он недостаточно хорошо определен и формализован. Тем не менее, хотя мы и не можем объявить одну из перечисленных