Как хорошо известно, PARITY не может быть выполнено в многоразмерных схемах с постоянной глубиной, и на самом деле схемы с постоянным углублением требуют количества входов EXP.
А как насчет схем QUANTUM?
а) Можно ли выполнить PARITY с помощью квантового контура, который имеет постоянную глубину и число ворот?
б) Мой вопрос вообще имеет смысл?
Ответы:
Вопрос имеет смысл, и короткий ответ - это открытая проблема.
Вот длинный ответ: в зависимости от того, как вы определяете постоянные квантовые схемы с неограниченной глубиной, вы можете получить разные классы. 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 . Дополнительную информацию можно найти в обзоре квантовых цепей малой глубины, проведенных Бера, Грин и Гомером.
источник
Удивительно, но количество дополнительных рабочих кубитов (вспомогательных) имеет значение. Прямо сейчас известно, что PARITY отсутствует в QAC_0 с ограниченными вспомогательными элементами.Квантовые нижние оценки для разветвления дают одно доказательство для цепей, использующих самое большее линейно много вспомогательных, а doi: 10.1016 / j.ipl.2011.05.002 дает еще одно доказательство для цепей, не использующих вспомогательные элементы.
источник