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

Далее, теорема о максимальном потоке и минимальном разрезе гласит, что обратное тоже верно, а значит, для любой сети максимальный поток и минимальный разрез на самом деле равны.

Упражнение (для тех, кто никогда этого не видел). Докажите теорему о максимальном потоке и минимальном разрезе.

Упражнение (трудное). При помощи теоремы о максимальном потоке и минимальном разрезе докажите, что для любого унитарного U и любого состояния |ψ〉 существует способ передать всю массу вероятности, или вероятностную меру, от s к t в сети G (U, |ψ〉), приведенной выше.

Итак, теперь у нас есть кандидат на роль теории скрытых параметров! Делаем так: при заданных U и |ψ〉 сначала находим «канонический» способ передать всю вероятностную меру от s к t в сети G(U, |ψ〉). Затем определяем стохастическую матрицу S через sij:= pij/|αi|2, где pij — количество вероятностной меры, переданной от |i〉 к |j〉. (Для простоты я проигнорирую то, что происходит при αi = 0.)

По построению такое S отображает вектор |αi|2 на вектор |βi|2. Оно обладает также таким замечательным свойством, что для любых i, j если uij = 0, то и sij = 0.

Почему?

Верно! Потому что если uij = 0, то никакая вероятностная мера не может пройти от |i〉 к |j〉.

Упражнение (еще более трудное). Докажите, что можно выбрать «канонические» максимальные потоки таким образом, что небольшое изменение U или |ψ〉 вызывает лишь небольшое изменение в матрице вероятностей перехода (pij).

Теория Шрёдингера

Итак, мы рассмотрели один остроумный пример теории скрытых параметров. Теперь я хочу показать вам пример, который лично я считаю еще более остроумным. Когда я начал размышлять о теории скрытых параметров, это было первое, что мне пришло в голову предложить. Позже я обнаружил, что Шрёдингер в почти забытой статье 1931 г.[97] предложил ту же идею.

Говоря конкретнее, идея Шрёдингера состояла в том, чтобы определить переходные вероятности в квантовой механике через решение системы связанных нелинейных уравнений. Проблема в том, что Шрёдингер не смог доказать, что его система имеет решение (тем более единственное решение); пришлось дождаться работы Масао Нагасавы[98] в 1980-е гг. К счастью, меня заботили только квантовые системы конечной размерности, где все намного проще и где я мог дать достаточно элементарное доказательство того, что система уравнений имеет решение.

Так в чем же здесь идея? Если вы помните, мы хотим заданную унитарную матрицу U каким-то образом «конвертировать» в стохастическую матрицу S, отображающую начальное распределение на конечное. По существу, это эквивалентно нахождению матрицы переходных вероятностей P, то есть неотрицательной матрицы, i-й столбец которой в сумме дает |αi|², а j-я строка в сумме дает |βi|². (Это всего лишь условие, при котором безусловные вероятности примут обычные квантово-механические значения.)

Поскольку мы хотим получить в результате неотрицательную матрицу, разумным первым шагом было бы заменить везде U на ее абсолютное значение:

Что дальше? Ага, мы хотим, чтобы i-й столбец в сумме давал |αi|². Поэтому давайте продолжим самым грубым ходом, какой только можно придумать, и для любого 1 ≤ i ≤ N просто нормализуем i-й столбец так, чтобы в сумме он давал |αi|²!

Дальше, мы также хотим, чтобы j-я строка в сумме давала |βi|². Как мы этого добьемся? Правильно, для любого 1 ≤ j ≤ N мы просто нормализуем j-ю строку так, чтобы в сумме она давала |βi|².

Конечно, после того как мы нормализуем строки, в общем случае i-й столбец уже не будет в сумме давать |αi|². Но это не проблема: мы просто нормализуем столбцы еще раз! После этого мы еще раз нормализуем строки (которые пострадали при нормализации столбцов), затем вновь нормализуем столбцы (пострадавшие при нормализации строк) и так далее до бесконечности.

Упражнение (трудное). Докажите, что этот итерационный процесс сходится для любых U и |ψ〉 и что предел этой последовательности — матрица P = (pij) переходных вероятностей, то есть неотрицательная матрица, i-й столбец которой дает в сумме |αi|², а j-я строка дает сумме |βi|².

Нерешенная задача (если вы ее решите, дайте мне знать). Докажите, что небольшое изменение U или |ψ〉 приводит лишь к небольшому изменению в матрице P = (pij) переходных вероятностей.

Механика Бома

У некоторых из вас мог возникнуть вопрос: почему я не упомянул самую знаменитую теорию скрытых параметров — механику Бома[99]? Дело в том, что для обсуждения механики Бома мне пришлось бы привлечь гильбертовы пространства бесконечной размерности (жуть!), частицы с их координатами и импульсами (жуть-жуть!) и другие идеи, которые противоречат всему, за что я выступаю как специалист по теоретической информатике.

И все же мне следовало бы рассказать вам немного о том, что такое механика Бома и почему она не влезает в мои рамки. В 1952 г. Дэвид Бом предложил детерминистскую теорию скрытых параметров, то есть теорию, в которой вы мало того что получаете переходные вероятности, но все эти вероятности равны либо нулю, либо единице! Чтобы добиться этого, он взял в качестве скрытого параметра положение частиц в R3. Затем он оговорил, что вероятностная мера того, где частицы находятся, должна «течь» вместе с волновой функцией, так что область пространства конфигураций с вероятностью ε всегда отображается на другую область с вероятностью ε.

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

Для иллюстрации продемонстрируем, как выглядят траектории бомовской частицы в знаменитом эксперименте с двумя щелями:

Опять же поразителен в этой теории ее детерминистский характер: стоит обозначить «настоящие» координаты всех частиц во Вселенной в любой конкретный момент времени, и тем самым вы определите их «настоящие» координаты на все прошлые и будущие времена. Так что, если хотите, можете представить себе, что Бог рассыпал частицы по Вселенной в соответствии с обычным распределением |ψ|²; но после этого Он вдребезги разбил свои игральные кости и позволил частицам дальше развиваться детерминистски. Такое предположение приведет вас в точности к тем же экспериментальным предсказаниям, как и обычная картина квантовой механики — та, в которой Бог бросает кости до опупения.

Ловушка