Ограниченные вероятностные распределения по глубине

Два связанных вопроса об ограниченных вычислениях глубины:

1) Предположим, что вы начинаете с n битов, и начинаться с бита i может быть 0 или 1 с некоторой вероятностью p (i) независимо. (Если это упрощает задачу, мы можем предположить, что все p (i) s равны 0,1 или 1/2.или даже то, что все они 1/2.)

Теперь вы делаете ограниченное число раундов вычислений. В каждом раунде вы применяете обратимые классические ворота на непересекающихся наборах битов. (Исправьте ваш любимый набор универсальных классических реверсивных ворот.)

В конце вы получаете распределение вероятностей по строкам по n битам. Есть ли результаты по ограничению таких распределений?

Я ищу что-то похожее на лемму переключения Хастада, результат Боппаны, что общее влияние мало или теорема LMN.

2) Тот же вопрос, что и 1), но с ограниченными квантовыми цепями глубины.

Есть несколько сравнительно недавних работ Эмануэле Виолы и др., Которые касаются сложности распределений выборки. Они сосредоточены на ограниченной модели вычислений, таких как деревья решений с ограниченной глубиной или схемы с ограниченной глубиной.

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

Схемы с ограниченной глубиной не могут выбирать хорошие коды

Сложность Распределений

Короткий ответ.

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

Это, конечно, не говорит вам о том, что на самом деле будут иметь схемы ; особенно если вы заинтересованы в решении проблем с ограниченной ошибкой, а не в распределении вероятностей. Однако это означает, что анализ с точки зрения деревьев решений, как и в случае с леммой Хостада о переключении , вряд ли будет готов к классическому моделированию этих цепей.$\mathsf{QNC^0}$

Детали

Мы можем рассмотреть определение квантовых цепей с полилоговой глубиной, данное Феннером и соавт. (2005) :

Определение. - это класс семейств квантовых цепей для которых существует полином для которого каждый содержит входных кубитов и не более свежих вспомогательных элементов, использует только одиночные кубитные и управляемые-не-ворота, и имеет глубину .$\mathsf{QNC^k}$$\{C_n\}_{n\geqslant0}$$p$$C_n$$n$$p(n)$$O(\log^k(n))$

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

Бремнер, Йозса и Шеппард (2010) отмечают (см. Раздел 4), что, используя адаптацию техники телепортации в ворота из-за Терхала и Ди Винченцо (2004) , пост-выборка некоторых кубитов в Схема позволяет решать проблемы в . Используя их результаты по моделированию выбранных схем, это означает, что проблема классической выборки из выходного распределения произвольной схемы с логическим выходом, с мультипликативной ошибкой не более в вероятности выборки, заключается в невозможно со случайными полиномиальными контурами глубины, если полиномиальная иерархия не частично разрушается (в частности,$\mathsf{QNC^0}$$\mathsf{PostBQP = PP}$$\mathsf{QNC^0}$$\sqrt 2$$\mathsf{PH} \subseteq \Delta_3$ ).