Интерактивные доказательства с помощью Postselection?

Определите, что вычислительная модель MPostBQP идентична PostBQP, за исключением того, что мы разрешаем полиномиально много измерений в кубитах перед последующим выбором и окончательным измерением.

Можем ли мы привести какие-либо доказательства того, что MPostBQP более мощный, чем PostBQP?

Определите MPostBQP [k], чтобы разрешить многократные измерения и последующий выбор, прежде чем мы сделаем окончательное измерение. Выберите индексирование, чтобы MPostBQP [1] = PostBQP и MPostBQP [2] = MPostBQP и так далее. (Обновление: формальное определение дано ниже.)

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

У нас есть AM [K] $\subset$ MPostBQP [к]?

Это действительно известно $k=1$, который говорит М.А. $\subset$PP. Чтобы показать это для$k=2$ будет означать MPostBQP = PP, только если AM $\subset$PP. Поскольку существует оракул, относительно которого AM не содержится в PP , это может дать утвердительный ответ на мой первый вопрос.

Наконец, для случая полиномиально много раундов,

Есть ли у нас PSPACE $\subset$MPostBQP [поли]? Если это так, это равенство?

Это было бы философски интересно (по крайней мере для меня), потому что это сообщило бы нам, что «поддающийся лечению» класс проблем для «постселектного колдуна» включает (или есть ) весь PSPACE.

РЕДАКТИРОВАТЬ: меня попросили формальное определение MPostBQP. (Я обновил, что следует.)

MPostBQP [k] - класс языков $L \subset \{0,1\}^*$ для которого существует однородное семейство квантовых цепей полиномиального размера $\{C_n\}_{n \geq 1}$ такой, что для всех входов $x$приведенная ниже процедура дает значение true с вероятностью не менее $2/3$ если $x \in L$и с вероятностью не более $1/3$ если $x \notin L$, Процедура, которая допускает некоторые варианты, которые могут зависеть от$L$ (но нет $x$), определяется следующим образом:

Процедура: Шаг 1. Примените унитарный оператор, соответствующий$C_n$ в состояние ввода $\left\vert 0\cdots 0\right> \otimes \left\vert x \right>$, Обратите внимание на длину первого$\left\vert0\cdots 0\right>$ регистр не более чем полиномиальной длины $x$, Шаг 2. Для$i = 1 \cdots k$: Если $i$является четным, затем измеряет любое желаемое количество кубитов из первого регистра (самое большее, полиномиально много, учитывая размер регистра). Если$i$ будет нечетным, а затем постселектом, поэтому выбранный одиночный кубит в первом регистре измеряется как $\left\vert 0 \right>$(и иметь гарантию, что вероятность не равна нулю, поэтому поствыбор действителен, конечно). Шаг 3. Наконец, измеряем последний кубит в первом регистре и возвращаем true, если мы измеряем$\left \vert 1 \right>$ и ложь в противном случае.

У нас есть MPostBQP [0] = BQP, MPostBQP [1] = PostBQP и MPostBQP: = MPostBQP [2]. Я пытаюсь отразить классы Артура-Мерлина, где AM [0] = BPP, AM [1] = MA и AM [2] = AM.

РЕДАКТИРОВАТЬ (27.03.11 в 17:00): Похоже, идут дебаты о том, как следует определять поствыборы в этом контексте. Очевидно, я имею в виду определение, которое не упрощает мой вопрос! :) Определение, которое я принял, состоит в следующем: « Отбор» по k-му биту означает, что мы проецируем состояние в подпространство, в котором k-й бит$0$и нормализуй. Оказывается, что в схеме, в которой мы проводим предварительный отбор до проведения измерений, мы можем получить окончательную статистику, рассматривая условные вероятности в схеме, в которой поствыборы заменяются измерениями. Однако я утверждаю, что эта характеристика нарушается, когда измерения и поствыборы перемежаются. Я думаю, что путаница проистекает из людей, использующих это «определение условной вероятности» (которое работает в особом случае, из которого я обобщаю) в качестве определения поствыбора, а не определения «вынужденного измерения», которое я только что дал, которое явно зависит от порядок из-за отсутствия коммутативности. Надеюсь, это поможет!

РЕДАКТИРОВАТЬ (27.03.11 9 PM): Я уже определил поствыбор в чисто государственном формализме. Ниль дал анализ в формализме матрицы плотности, который не согласуется с моим для примера с 3 кубитами. Виновником, опять же, является определение поствыбора. Определите поствыбор в настройках матрицы плотности следующим образом. Учитывая матрицу плотности$M$переписать его как смесь разделяемых состояний $M = \sum p_i \left\vert a_i \right> \left< a_i \right\vert$, Позволять$\left\vert A_i \right>$быть результатом поствыбора (на некотором кубите) с использованием формализма чистого состояния, который я определил выше. Определите результат поствыбора на$M$ быть $\sum p_i \left\vert A_i \right> \left< A_i \right\vert$,

Это более разумное определение, потому что оно не дает нам результатов, которые говорят о том, что после пост-выбора мы изменяем статистику событий (измерений), которые мы уже наблюдали. Это$p_i$Это вероятность монет, которые мы уже «подбросили». Мне не имеет смысла говорить, что мы вернемся назад во времени и сместим бросок монеты, который уже произошел, потому что это сделает текущий поствыбор более вероятным.

РЕДАКТИРОВАТЬ (28.03.11 13:00): Ниль признает, что с моими определениями проблема имеет смысл и не упрощает - но с условием, что я не должен называть это поствыбором . Учитывая количество путаницы, я должен согласиться с ним. Итак, давайте назовем то, что я определил, как выбор , который выполняет «принудительное измерение». Мне, вероятно, следует изменить название классов сложности, которые я тоже определил (чтобы в них не было «Post»), поэтому давайте назовем их QMS [k] (квант-мера-выбор).

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

В этом случае аргументы, приведенные в других ответах мной и Нилом, больше не верны. На самом деле легко увидеть, что$P^{PP[k]}\subseteq$ MPostBQP [k], так как MPostBQP$[k]$ может рассматриваться как машина BQP, которая может сделать $k$ запросы к оракулу PP, и, следовательно, $P^{\# P}\subseteq$ MPostBQP .

Итак, теперь у нас есть нетривиальная нижняя граница, как насчет верхней границы? Ну, ясно, что проблема в PSPACE , но мы можем сделать лучше? На самом деле, я думаю, что мы можем.

Мы можем записать любое вычисление в MPostBQP в виде последовательности слоев вида: квантовое вычисление с последующим поствыбором и последующим измерением одного кубита. Действительно, это может быть альтернативный способ сформулировать MPostBQP [k], как вычисление, состоящее из$k$такие слои (это немного отличается от определения Шона, которое, как я полагаю, предназначено для подсчета только количества поствыборов), за которым следует заключительный слой классической постобработки. Я буду использовать это определение MPostBQP [k] в следующем, так как это приводит к более эстетически приятному результату.

Ниже обновлено с оригинальной версии, чтобы исправить дыру в доказательстве.

Сначала мы хотим вычислить результат измерения первого измеренного кубита (не отобранного!). Для этого сначала отметим, что любое квантовое вычисление может быть выражено с использованием только вентилей Адамара и Тоффоли, а также амплитуды$\alpha_w$ определенного вычислительного базисного состояния $|w\rangle$ в выводе можно записать как сумму не более $2^{H}$ сроки $a_{j,w}$, где $H$общее число ворот Адамара, каждое из которых соответствует уникальному вычислительному пути. Очевидно, что$a_{j,w} = \pm 2^{-H/2}$, Вероятность получения конечного состояния$|w\rangle$ затем дается $\alpha_w^2 = (\sum_j a_{j,w})^2 = \sum_{i,j} a_{j,w}a_{i,w}$, Мы хотим рассчитать общую вероятность измерения 1. Пусть$S_0$ быть набором вычислительных базисных состояний, которые удовлетворяют критериям пост-выбора (т. е. кубит после выбора равен 1) и дают 0 для измеренного кубита, и позволяют $S_1$быть набором вычислительных базовых состояний, которые удовлетворяют критериям пост-выбора и дают 1 для измеренного кубита. Мы можем определить

В этом случае вероятность измерения 1, обусловленного 1 для выбранного кубита, определяется как $\frac{\pi_1^+ - \pi_1^-}{\pi_1^+ - \pi_1^- - \pi_0^- + \pi_0^+}$, Как мы можем определить это с 4 вызовами к оракулу #P. Мы используем это, чтобы произвести случайный бит$b_1$ который равен 1 с вероятностью $X_1$так же, как квантовое измерение. Таким образом, MPostBQP [1] находится в$BPP^{\# P[4]}$,

Далее вычисляем результат измерения второго кубита. Для этого мы выполняем те же самые запросы #P, что и для первого слоя, но в схеме, полученной путем объединения первых двух слоев, и где мы отбираем 1 для каждого из выбранных после этого кубитов, но также и для$b_1$ для результата измерения 1. Обратите внимание, что, хотя это поствыбор по состояниям 3 кубитов, а не 1, это тривиальная модификация $\# P$запросы, просто добавив вспомогательную функцию, которая устанавливается только в том случае, если все 3 кубита удовлетворяют требуемым условиям, и вместо этого выбрав пост-выборку для этой вспомогательной функции. Затем он генерирует правильные условные вероятности вывода для результата второго измеренного кубита, который мы помечаем$b_2$, Обратите внимание, что теперь мы использовали 8 вызовов к оракулу #P .

Мы повторяем этот процесс итеративно, чтобы на уровне $j$ мы выбираем 1 для всех $j$ предшествующие пост-выбранные кубиты и на $b_{i<j}$ для всех предыдущих измерений и пометить результат соответствующего $P^{\# P}$ машина $b_j$, В общей сложности это потребовало$4j$ оракульные запросы.

Таким образом, мы имеем MPostBQP [k]$\subseteq P^{\# P[4k]}$, что в сочетании с предыдущим результатом, $P^{PP[k]}\subseteq$ MPostBQP$[k]$, подразумевает, что $P^{PP[k]} \subseteq$ MPostBQP [k]$\subseteq BPP^{\# P[4k]}$и, следовательно, MPostBQP $= P^{\# P}$,

[Пересмотрено.] Я пересмотрел свой ответ на основе ваших изменений на ваш вопрос, я сохранил содержание моего первоначального ответа, но сделал его короче. Более подробное описание процесса «симуляции» было заменено, но я полагаю, что это можно увидеть, просмотрев историю редактирования этого поста.

Большинство людей поймут «поствыбор» в смысле условной вероятности. Действительно, текущая версия статьи в Википедии на PostBQP описывает это так; и рассматривается как операция с операторами плотности (в которой применяется абсолютно положительное отображение без увеличения следа Φ, такое, что Φ ²  = Φ, а затем перенормирует след), восстанавливается это определение.

Учитывая это определение поствыбора, ваше определение алгоритма MPostBQP [ k ] может быть смоделировано алгоритмом PostBQP , откладывая поствыборы и выполняя их одновременно подходящим способом. Это более или менее явно указано на странице 3 статьи Ааронсона « Квантовые вычисления, поствыбор и вероятностное полиномиальное время», в которой представлен класс PostBQP .

Это может быть продемонстрировано в явном виде, отметив, что для последовательности битов P ₁  ,   P ₂  , ..., которые должны быть выбраны пост ( например, в 1обычном состоянии), нет никакой разницы между условием их нахождения 1в середине вычисление и согласование для них находятся 1в конце вычисления, пока значения этих битов не изменяются в промежуточный период. Затем, вместо пост-выбора каждого из них по отдельности 1, мы можем вычислить их логическое И перед пост-выбором, а затем пост-выбор по этому соединению.1, Кроме того, вычисление И может выполняться в любой точке между последним преобразованием бита и его последующим выбором. Это никоим образом не повлияет на совместную статистику каких-либо свойств государства.

Таким образом, используя общее определение поствыбора в терминах условных вероятностей, мы бы имели MPostBQP [ k ] =  PostBQP для всех k  > 0.

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

[Править.] Ради чистоты я удалил вычисленный пример. Я полагаю, что это можно увидеть, просмотрев историю редактирования этого поста.

Из вашего определения MPostBQP может показаться , что это просто PostBQP в модном костюме. Вместо того, чтобы пытаться убедить вас в том, что измерения могут быть переупорядочены, возможно, вы найдете более убедительным доказательство MPostBQP = PP , поскольку известно, что PostBQP = PP (см. Quant-ph / 0412187 ). Чтобы доказать это, мы разделяем это на две задачи:

1. доказывая, что ПП$\subseteq$MPostBQP и
2. доказывая, что MPostBQP$\subseteq$ PP

Первая задача тривиальна, так как PP = PostBQP = MPostBQP [1]$\subseteq$MPostBQP . Второе задание - это действительно главный вопрос здесь, но на него можно ответить, сделав простую адаптацию к доказательству того, что PostBQP = PP , приведенному в quant-ph / 0412187 (см. Страницу доказательства в Википедии на PostBQP ).

Следующее адаптировано из эскиза доказательства Википедии для PostBQP = PP .

Мы можем записать схему, соответствующую любому вычислению MPostBQP, в виде последовательности унитарных вентилей и поствыборов . Без ограничения общности мы можем предположить, что после того, как кубит был выбран последним, на него больше никогда не воздействуют. Таким образом, квантовое состояние, полученное в конце вычисления, определяется как $|\psi\rangle = \prod_i (P_i^1 \prod_j A^{ij}) |x\rangle$, где $P_i^1$ обозначает проектор для кубита $i$ на $|1\rangle$ подпространство и $A^{ij}$являются матрицами, соответствующими элементарным воротам. Обратите внимание, что без ограничения общности мы можем предположить, что все записи в$A^{ij}$ реальны за счет дополнительного кубита.

Теперь пусть $\{p_i\}$ быть набором кубитов, которые выбраны после, и пусть $q$быть выходным кубитом. Мы определяем$\pi_0 = \sum_{w \in S_0} \psi_w^2$ а также $\pi_1 = \sum_{w \in S_1} \psi_w^2$, где $S_0$ ($S_1$) - это набор вычислительных базисных состояний, для которых $p_i = 1 \forall i$ а также $q=0$ ($q=1$). Определение MPostBQP затем гарантирует, что либо$\pi(1) \geq 2\pi(0)$ или $\pi_0 \geq 2\pi_1$, Идея состоит в том, чтобы построить машину ПП для сравнения$\pi_0$ а также $\pi_1$, выражающий$\psi_w$часть конечной волновой функции $\psi$ соответствует определенному вычислительному базовому состоянию $w$, как сумма по путям и замена индексов $i$ а также $j$ на $A^{ij}$ с одним индексом $k$ работает от 1 до $G$, мы получаем $\psi_w = \sum_{\alpha_1 ... \alpha_G} A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$,

Таким образом, идея состоит в том, чтобы построить машину PP, которая принимает с вероятностью$\frac{1}{2}(1+C(\pi_1-\pi_0))$ для некоторых $C>0$, с того времени $x \in L$ будет означать, что $\frac{1}{2}(1+\pi_1-\pi_0)> \frac{1}{2}$ а также $\frac{1}{2}(1+\pi_1-\pi_0) < \frac{1}{2}$ если $x \notin L$,

Теперь давай $\alpha = \{\alpha_i\}$ а также $F(A,w,\alpha,X) = A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$, затем$\pi_1 - \pi_0 = \sum_{w \in S_1} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X) - \sum_{w \in S_0} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X)$,

Такая машина PP может быть определена следующим образом:

1. Выберите вычислительное базовое состояние $w$ равномерно наугад
2. Если $w \notin S_0 \cup S_1$затем остановитесь и примите с вероятностью $1/2$и отклонить иначе.
3. Выберите две последовательности $\alpha$ а также $\alpha'$ из $G$ вычислительные базисные состояния равномерно случайным образом.
4. вычисление $X = F(A,w,\alpha,x)F(A,w,\alpha',x)$,
5. Если $w\in S_1$ тогда с вероятностью прими $\frac{1+X}{2}$и отклонить иначе. В качестве альтернативы, если$w\in S_0$ тогда с вероятностью прими $\frac{1-X}{2}$и отклонить иначе.

Это тогда помещает MPostBQP [k]$\subseteq$ПП , для всех$k$и, следовательно, MPostBQP не более мощный, чем PostBQP .