Каковы последствия

Шива Кинтали только что объявил (круто!) Результат, что изоморфизм графов для ограниченных графов ширины является трудным $\geq 4$ $\oplus L$ . Неофициально мой вопрос: "Насколько это сложно?"

Мы знаем, что неравномерно , см. Ответы на этот вопрос . Мы также знаем, что маловероятно, что , см. Ответы на этот вопрос . Как удивительно было бы, если ? Я слышал, что многие говорят, что не будет шокирующим, как . $NL \subseteq \oplus L$ $\oplus L = P$ $L=\oplus L$ $L=NL$ $P=NP$

Каковы последствия ? $L=\oplus L$

Определение: - это набор языков, распознаваемых недетерминированной машиной Тьюринга, которые могут различать только четное число или нечетное число путей «принятия» (а не нулевое или ненулевое число путей принятия), и который в дальнейшем ограничен работой в логарифмическом пространстве. $\oplus L$

cc.complexity-theory complexity-classes logspace Аарон Стерлинг
источник

Ответы:

Wigderson доказал , что . По стандартным рассуждениям, означает . (Возьмите машину в . Она имеет эквивалентную машину в $NL/poly \subseteq \oplus L/poly$ $L = \oplus L$ $L/poly = NL/poly$ $M$ $NL/poly$ $M'$ . Возьмем языка пар экземпляр-совет . Если этот язык в , затем жестко прописывать соответствующий советмы получаем машиныэквивалентный .) $\oplus L/poly$ $\oplus L$ $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$ $L$ $a$ $L/poly$ $M$

Я думаю, что это было бы удивительно: недетерминированные программы ветвления были бы эквивалентны детерминированным программам ветвления (вплоть до полиномиальных факторов).

Райан Уильямс
источник

(Результат Widgerson был включен в категорию NL / поли = UL / поли .)

Хорошо, если то моделирование цепей стабилизатора находится в , поскольку Ааронсон и Готтесман (Physical Review A 70, 052328) доказали, что такое моделирование завершено для при сокращении пространства журнала или, что еще слабее, чем моделирование сетей CNOT в , Эквивалентно, если моделирование таких схем в , то . Лично я бы обнаружил, что это удивительно, но не так, как со стула, я нахожу удивительным. $L=\oplus L$ $L$ $\oplus L$ $L$ $L$ $L = \oplus L$ $P=NP$

Джо Фитцсимонс
источник

Спасибо. Есть ли интуитивно понятное объяснение того, что могут делать цепи стабилизатора? Я не знаком с ними.

Аарон Стерлинг

@AaronSterling: схемы стабилизатора являются ограниченной моделью квантовых вычислений; они генерируются вентилями CNOT (обратимо вычисляющими XOR двух входных битов) и двумя вентилями, которые не имеют непосредственных аналогов в классических вычислениях. Действуя на «классические» входы (так называемые вычислительные базовые состояния) или на входы, которые являются лишь слегка более общими, чем «классические» входы, они могут эффективно моделироваться с точки зрения симплектических преобразований по модулю 2, несмотря на то, что они являются квантово-механическими по вкусу ( и только немного стесняется быть способным к универсальности для квантовых вычислений).

Ниль де Боудрап,

@AaronSterling: они являются подмножеством всех квантовых цепей, которые включают CNOTS (по существу, XOR + разветвление), а также ряд квантовых вентилей, которые могут создавать равные суперпозиции (например, вентили Адамара). Если вы знакомы с квантовыми вычислениями, то схемы соответствуют тем операторам, которые отображают операторы Паули на другие операторы Паули при сопряжении, действуя на классический вход (или на вход, который можно получить из классического ввода через другую групповую схему Клиффорда).

Джо Фицсимонс

Я думаю, что нам нужна «неожиданная» иерархия, с «падением с моего стула» наверху :)

Суреш Венкат