PARITY в QAC_0 (если это имеет смысл)

17

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

А как насчет схем QUANTUM?

а) Можно ли выполнить PARITY с помощью квантового контура, который имеет постоянную глубину и число ворот?

б) Мой вопрос вообще имеет смысл?

Билл ГАЗАРХ
источник
2
Это кажется актуальным: eccc.uni-trier.de/eccc-reports/1999/TR99-032
Росс Снайдер

Ответы:

20

Вопрос имеет смысл, и короткий ответ - это открытая проблема.

Вот длинный ответ: в зависимости от того, как вы определяете постоянные квантовые схемы с неограниченной глубиной, вы можете получить разные классы. QAC 0 обычно определяется как имеющий неограниченные веерные вентили Toffoli и однокубитные вентили. QAC 0 wf - это класс, в котором мы также разрешаем вентиль "разветвления", который копирует входной бит на многие выходы. (Он реализует | a> | 0> ... | 0> -> | a> | a> ... | a>) Этот класс действительно мощный, поскольку он содержит, кроме PARITY и AC 0 , также ACC 0 и TC 0 .

Таким образом, очевидный вопрос, который нужно задать, заключается в том, содержится ли PARITY в QAC 0 , и это открытая проблема. Это эквивалентно вопросу, является ли QAC 0 = QAC 0 wf . Я предполагаю, что вера в то, что PARITY не в QAC 0 . Дополнительную информацию можно найти в обзоре квантовых цепей малой глубины, проведенных Бера, Грин и Гомером.

Робин Котари
источник
TС0QAСС0
Сэмюэль Шлезингер
@SamuelSchlesinger: этот документ показывает, что вы можете вычислить порог, паритет, большинство и т. Д. Только с вентилями разветвления и 2- кубитными
Робин Котари
9

Удивительно, но количество дополнительных рабочих кубитов (вспомогательных) имеет значение. Прямо сейчас известно, что PARITY отсутствует в QAC_0 с ограниченными вспомогательными элементами.Квантовые нижние оценки для разветвления дают одно доказательство для цепей, использующих самое большее линейно много вспомогательных, а doi: 10.1016 / j.ipl.2011.05.002 дает еще одно доказательство для цепей, не использующих вспомогательные элементы.

dBera
источник