Сокращение лог-пространства от схем Parity-L до CNOT?

Вопрос.

В своей работе « Улучшенное моделирование цепей стабилизатора» Ааронсон и Готтесман утверждают, что имитация схемы CNOT является ⊕L-полной (при сокращении пространства журнала). Ясно, что оно содержится в ⊕L ; как держится результат твердости?

Эквивалентно: есть ли сокращение лог-пространства от итерированных матричных произведений по модулю 2 до итерированных произведений элементарных матриц (обратимых матриц, которые реализуют преобразования строк) mod 2?

Детали

Контролируемым НЕ (или CNOT ) операция является обратимой булева операция, формы где изменяется только j- ^й бит, и что бит изменяется путем добавления по модулю 2 для любых различных позиций h и j . Нетрудно понять, если мы интерпретируем

{C N O T}_{h, j} (x_{1}, \dots, x_{h}, \dots, x_{j}, \dots, x_{n}) = (x_{1}, \dots, x_{h}, \dots, x_{j} \oplus x_{h}, \dots, x_{n})

$\mathsf{CNOT}_{\!h,j} (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j\,, \;\ldots\;, x_n) \;\;=\;\; (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j \oplus x_h\,, \;\ldots\;, x_n)$

x_{h}

$x_h$

x = (x_{1}, \dots, x_{n})

$\mathbf x = (x_1\,, \;\ldots\;, x_n)$ как вектор над ℤ / 2ℤ, это соответствует преобразованию элементарной строки по модулю 2, которое мы можем представить в виде матрицы с 1s по диагонали и одной недиагональной позицией. Тогда схема CNOT является матричным произведением, состоящим из произведения некоторых элементарных матриц этого типа.

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

⊕L [является] классом всех задач, которые могут быть решены недетерминированной машиной Тьюринга в логарифмическом пространстве, которая принимает, если и только если общее число принимающих путей является нечетным. Но есть альтернативное определение, которое, вероятно, является более интуитивным для не-компьютерщиков. Это то, что ⊕L - это класс задач, которые сводятся к моделированию схемы CNOT полиномиального размера, то есть схемы, состоящей полностью из вентилей NOT и CNOT, действующих на начальное состояние | 0 ... 0⟩. (Легко показать, что эти два определения эквивалентны, но для этого потребуется сначала объяснить, что означает обычное определение!)

Целевая аудитория статьи включала в себя значительное количество ученых, не занимающихся информатикой, поэтому стремление к элите не является необоснованным; Я надеюсь, что кто-то может прояснить, как выполняется эта эквивалентность.

Ясно, что моделирование произведения таких матриц может быть выполнено в ⊕L как частный случай оценки коэффициентов итерированных матричных произведений (mod 2), что является полной проблемой (при сокращении пространства журналов) для ⊕L . Кроме того, поскольку матрицы CNOT просто выполняют операции с элементарными строками, любая обратимая матрица может быть разложена как произведение матриц CNOT. Однако: не ясно, как мне разложить даже обратимую матрицу mod 2 на произведение матриц CNOT путем сокращения логарифмического пространства . (Действительно, как отметил Эмиль Йержабек в комментариях, исключения Гаусса достаточно для вычисления определителей mod 2, что является ⊕L -полной проблемой: так что прямая атака путем разложения, например, обратимые матрицы как произведения элементарных матриц кажутся неосуществимыми в лог-пространстве, если только L = ⊕L .) Не говоря уже о матричных произведениях, которые не являются обратимыми. Так что, кажется, требуется более умное сокращение.

Я надеюсь, что кто-то может предоставить эскиз этого сокращения или ссылку ( например, текст, для которого это упражнение, если оно простое).

cc.complexity-theory counting-complexity linear-algebra logspace Ниль де Бодрап
источник

Я полагаю, что вычисление определителей mod

также является ⊕L-полным, поэтому гауссовское исключение mod

является ⊕L-сложным.

2

$2$

2

$2$

Эмиль Йержабек поддерживает Монику

@ EmilJeřábek: Я думаю о вашем замечании и пытаюсь понять, означает ли это, что имитация схем CNOT не завершена для ⊕L, если L = ⊕L . (Рассмотрим произведение одной матрицы или произведение одной матрицы с единичной матрицей!) Это кажется почти слишком простым; я что-то пропустил? Я предполагаю, что, возможно, это исключает только сокращение «многие к одному».

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

Я не думаю, что это так просто. ⊕L - это класс задач решения, тогда как умножение матриц по F_2 - это функциональная проблема. ⊕L-версия умножения матриц - запрашивать определенный бит результата (скажем, левый верхний элемент матрицы). Может ли существовать алгоритм лог-пространства, который принимает последовательность матриц и создает последовательность элементарных матриц, чтобы произведения обеих последовательностей имели одинаковый верхний левый элемент? Это намного слабее, чем истинное гауссовское исключение. На самом деле, претензии Ааронсона и Готтесмана звучат правдоподобно для меня, хотя я не уверен, как это доказать.

Эмиль Йержабек поддерживает Монику

@ EmilJeřábek: Я думаю о том, что большинство проблем решения decisionL основаны на проверке индивидуальных коэффициентов задач, которые являются естественными для DET (обычно говорят о функциональных проблемах как о ⊕L-полных , однако злоупотребление ими терминология, которая есть); и что моя интуиция для матричных продуктов состоит в том, что достаточно сложно, чтобы было трудно организовать произвольно для любого отдельного коэффициента, что два матричных продукта должны быть равны для этого коэффициента таким образом, что вы не можете быть достаточно уверены, что все остальные коэффициенты также будут согласованы.

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

Я понял: подсчет принимающих путей машины лог-пространства равнозначен подсчету путей в ациклическом графе, который можно представить умножением верхних треугольных матриц с 1 на диагонали. Последнее может быть легко выражено как произведение элементарных матриц явным образом, без исключения Гаусса.

Эмиль Йержабек поддерживает Монику

Начнем с -полной задачи подсчета mod числа путей длины от вершины до вершины в ориентированном графе . Мы применяем несколько сокращений пространства журнала следующим образом. $\oplus L$ $2$ $n$ $s$ $t$ $G=(V,E)$

Пусть - такой граф, что и $G'=(V',E')$ $V'=V\times\{0,\dots,n\}$ (т. е. мы берем копиювершин , делаем ребра из й копии в -ную копию в соответствиис ребрами , и добавить все петли). Тогда исходная задача эквивалентна подсчету путей длины от до $E'=\{((u,i),(v,i+1):i<n,(u,v)\in E\}\cup\{(w,w):w\in V'\}$ $n+1$ $G$ $i$ $(i+1)$ $G$ $n$ $s'=(s,0)$ $t'=(t,n)$ в . $G'$

Кроме того, является ациклическим, и мы можем явно определить перечисление , чтобы все ребра в исключением автопетл, переходили от к для некоторого , Без ограничения общности и . Пусть - матрица смежности $G'$ $V'=\{w_k:k\le m\}$ $G'$ $w_k$ $w_l$ $k<l$ $w_0=s'$ $w_m=t'$ $M$ $G'$ по данному перечислению. Тогда является верхней треугольной матрицей с числом по диагонали, а число путей длины от до равна верхний правый элемент . $M$ $1$ $n$ $s'$ $t'$ $M^n$

Легко видеть, что где - элементарная матрица, единственным недиагональным элементом которой является в строка и столбец . Таким образом, мы свели исходную задачу к вычислению верхнего правого элемента произведения элементарных матриц. В

M = \prod_{j = m}^{1} \prod_{i = 0}^{j - 1} E_{i, j} (M_{i, j}),

$M=\prod_{j=m}^1\prod_{i=0}^{j-1}E_{i,j}(M_{i,j}),$

E_{i, j} (a)

$E_{i,j}(a)$

a

$a$

i

$i$

j

$j$

\oplus L

$\oplus L$ В этом случае вычисление выполняется по модулю

, т.е. мы рассматриваем матрицы над

. (В этом случае элементарными матрицами могут быть только

, которые мы можем игнорировать, и

, которые могут быть смоделированы одним вентилем CNOT, как упоминалось в вопросе .) Если мы рассмотрим их как целочисленные матрицы, мы получим

-полную задачу, а если мы рассмотрим их по модулю

, то получим

-полную задачу.

2

$2$

F_{2}

$\mathbb F_2$

E_{i, j} (0) = I

$E_{i,j}(0)=I$

E_{i, j} (1)

$E_{i,j}(1)$

# L

$\#L$

k

$k$

{M o d}_{k} L

$\mathrm{Mod}_kL$

Эмиль Йержабек поддерживает Монику
источник

Я имею в виду, что она

полна для элементарных матриц с неотрицательными целыми коэффициентами. С произвольными целыми числами это DET-завершено.

# L

$\#L$

Эмиль Йержабек поддерживает Монику

Следующее, вероятно, является стандартным, но я раньше не видел его явно: чтобы показать, что нахождение числа путей длины n точно в (возможно, циклическом) орграфе является ⊕L-полным , обратите внимание, что это равносильно вычислению коэффициентов некоторых степень произвольной матрицы над

, которая является ⊕L -полной . Этот ответ, в сущности, сводится к сокращению питания матрицы (используя стандартную конструкцию M в качестве блочной матрицы, состоящей только из копий произвольной матрицы смежности G в верхних недиагональных блоках и 1 на диагонали) к схемам CNOT , Хороший ответ!

F_{2}

$\mathbb F_2$

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

Вам не нужно проходить матрицу, чья ⊕L-полнота труднее доказать. ⊕L определяется путем подсчета mod 2 принимающих путей недетерминированного пространства логарифмической машины Тьюринга (полагаю, что с полиномиальными часами времени, так что число гарантированно будет конечным), что совпадает со счетом путей в графе конфигурации машина (легко организовать, чтобы все пути заканчивались в одной и той же конфигурации и чтобы пути имели одинаковую длину, заставляя машину зацикливаться, пока не истечет ее время, а затем войти в фиксированное состояние приема).

Эмиль Йержабек поддерживает Монику

Я полагаю, что, сосредоточившись на идеях, изложенных в статье « Стуктура» и важности классов Logspace-MOD, автором Buntrock et al. Я стал гораздо более привычным к мышлению с точки зрения количества путей произвольной длины в ациклическом орграфе и DET- подобных проблем, таких как матричные произведения и степени, которые естественно связаны с ним.

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

Сокращение лог-пространства от схем Parity-L до CNOT?

Вопрос.

Детали

Ответы: