Redução do espaço de log dos circuitos Parity-L para CNOT?

Questão.

Em seu artigo Simulação aprimorada de circuitos estabilizadores , Aaronson e Gottesman afirmam que a simulação de um circuito CNOT é completa em L (sob reduções no espaço de log). É claro que está contido em ⊕L ; como se mantém o resultado da dureza?

Equivalentemente: há uma redução do espaço de log do módulo 2 dos produtos da matriz iterada para produtos iterados das matrizes elementares (as matrizes invertíveis que realizam transformações de linha) mod 2?

Detalhes

Uma operação NÃO controlada (ou CNOT ) é uma operação booleana reversível, no formato que apenas o j- ^ésimo bit é alterado e esse bit ser alterado por adição de módulo 2, para qualquer posição distinta h e j . Não é difícil ver, se interpretarmos

{C N O T}_{h, j} (x_{1}, ..., x_{h}, ..., x_{j}, ..., x_{n}) = (x_{1}, ..., x_{h}, ..., x_{j} \oplus x_{h}, ..., 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)$ como um vetor acima de ℤ / 2ℤ, isso corresponde a um módulo de transformação de linha elementar 2, que podemos representar por uma matriz com 1s na diagonal e uma única posição fora da diagonal. Um circuito CNOT é então um produto de matriz que consiste em um produto de algumas matrizes elementares desse tipo.

O artigo de Aaronson e Gottesman mencionado acima (que, incidentalmente a essa pergunta, é sobre uma classe de circuitos quânticos que podem ser simulados em L ) possui uma seção sobre complexidade computacional. No início desta seção, eles descrevem ⊕L da seguinte maneira:

⊕L [é] a classe de todos os problemas solucionáveis por uma máquina de Turing de espaço logarítmico não determinístico, que aceita se e somente se o número total de caminhos aceitáveis for ímpar. Mas há uma definição alternativa que provavelmente é mais intuitiva para não cientistas da computação. Isso é que ⊕L é a classe de problemas que se reduz à simulação de um circuito CNOT de tamanho polinomial, ou seja , um circuito composto inteiramente de portas NOT e CNOT, atuando no estado inicial | 0 ... 0⟩. (É fácil mostrar que as duas definições são equivalentes, mas isso exigiria que explicássemos primeiro o que a definição usual significa!)

O público-alvo do artigo incluiu um número substancial de não cientistas da computação, portanto, o desejo de escapar não é razoável; Espero que alguém possa esclarecer como essa equivalência se aplica.

Claramente, a simulação de um produto dessas matrizes pode ser realizada em ⊕L como um caso especial de avaliação de coeficientes de produtos de matriz iterada (mod 2), que é um problema completo (em reduções de espaço de log) para ⊕L . Além disso, como as matrizes CNOT apenas realizam operações de linha elementares, qualquer matriz invertível pode ser decomposta como um produto das matrizes CNOT. No entanto: não está claro como decompor até mesmo uma matriz inversível mod 2 em um produto de matrizes CNOT por uma redução do espaço de log . (De fato, como observado por Emil Jeřábek nos comentários, a eliminação gaussiana é suficiente para calcular os determinantes mod 2, que é um problema completo de ⊕L : portanto, um ataque direto por decomposição, por exemplo matrizes invertíveis como produtos de matrizes elementares parece não ser viável no espaço de log, a menos que L = ⊕L .) Para não falar de produtos de matriz que não são invertíveis. Portanto, parece ser necessária uma redução mais inteligente.

Espero que alguém possa fornecer um esboço dessa redução ou uma referência ( por exemplo, um texto para o qual este é um exercício, se for simples).

cc.complexity-theory counting-complexity linear-algebra logspace Niel de Beaudrap
fonte

Suponho que os determinantes da computação mod

também estejam completos em L, portanto o mod

eliminação gaussiano é difícil em L.

2

$2$

2

$2$

Emil Jeřábek apoia Monica no dia 07/02

@ EmilJeřábek: Estou pensando em sua observação e estou tentando ver se isso implica imediatamente que simular circuitos CNOT não está completo para ⊕L, a menos que L = ⊕L . (Considere um produto de uma matriz ou um produto de uma única matriz com a matriz de identidade!) Isso parece quase fácil demais; estou esquecendo de algo? Suponho que talvez isso exclua apenas reduções muitos para um.

Niel de Beaudrap 07/07

Eu não acho tão fácil assim. ⊕L é uma classe de problemas de decisão, enquanto a multiplicação de matrizes sobre F_2 é um problema de função. A versão ⊕L da multiplicação da matriz é pedir um bit específico do resultado (por exemplo, a entrada superior esquerda da matriz). Pode haver um algoritmo de espaço de log que pega uma sequência de matrizes e produz uma sequência de matrizes elementares para que os produtos de ambas as sequências tenham o mesmo elemento superior esquerdo? Isso é muito mais fraco que a verdadeira eliminação gaussiana. Na verdade, a alegação de Aaronson e Gottesman parece plausível para mim, embora eu não tenha certeza de como provar isso.

Emil Jeřábek apoia Monica no dia

@ EmilJeřábek: Estou pensando em como a maioria dos problemas de decisão ⊕L se baseia na verificação de coeficientes individuais de problemas naturais para o DET (é comum falar de problemas de função como sendo ⊕L-completo , no entanto, um abuso de terminologia que é); e que minha intuição para produtos matriciais é que é suficientemente complicado que seja difícil organizar ad-hoc, para qualquer coeficiente único , que dois produtos matriciais sejam iguais para esse coeficiente de maneira que você não possa ter certeza que todos os outros coeficientes concordarão também.

Niel de Beaudrap

Entendi: contar caminhos aceitos de uma máquina de espaço de log equivale a contar caminhos em um gráfico acíclico , que pode ser representado pela multiplicação de matrizes triangulares superiores com 1 na diagonal. Este último pode ser facilmente expresso como um produto de matrizes elementares de maneira explícita, sem eliminação gaussiana.

Emil Jeřábek apoia Monica no dia

Vamos começar com o problema completo de contar mod o número de caminhos de comprimento do vértice ao vértice em um gráfico direcionado . Aplicamos algumas reduções de espaço de log da seguinte maneira. $\oplus L$ $2$ $n$ $s$ $t$ $G=(V,E)$

Seja o gráfico tal que e $G'=(V',E')$ $V'=V\times\{0,\dots,n\}$ (isto é, tomamos cópias de ‘vértices s, faça bordas ir do th cópia para a th cópia de acordo com bordas 's, e adicione todos os auto-loops). Então o problema original é equivalente a contar caminhos de comprimento de até $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)$ em . $G'$

Além disso, é acíclico, e podemos definir explicitamente uma enumeração modo que todas as arestas em além dos auto-loops, vão de a por alguns . Sem perda de generalidade, e . Seja a matriz de adjacência de $G'$ $V'=\{w_k:k\le m\}$ $G'$ $w_k$ $w_l$ $k<l$ $w_0=s'$ $w_m=t'$ $M$ $G'$ escreva a enumeração fornecida. Então é uma matriz inteira triangular superior com na diagonal e o número de caminhos de comprimento de até é igual ao elemento superior direito de . $M$ $1$ $n$ $s'$ $t'$ $M^n$

É fácil ver que onde é a matriz elementar cuja única entrada não-diagonal é em linha e coluna . Dessa maneira, reduzimos o problema original para calcular o elemento superior direito de um produto de matrizes elementares. No

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$ Nesse caso, o cálculo é o módulo

, ou seja, consideramos as matrizes acima de

. (Nesse caso, as matrizes elementares podem ser apenas

, que podemos ignorar, e

, que podem ser simuladas por uma única porta CNOT, como mencionado na pergunta ). Se nós os consideramos como matrizes de inteiros, temos um

problema -completo, e se considerarmos los modulo

, temos um

problema -completo.

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$

Emil Jeřábek apoia Monica
fonte

Quero dizer, é

completo para matrizes elementares com coeficientes inteiros não negativos. Com números inteiros arbitrários, é DET-completo.

# L

$\#L$

Emil Jeřábek apóia Monica 10/02

O seguinte é provavelmente padrão, mas eu nunca o tinha visto explicitamente antes: para mostrar que encontrar o número de caminhos de comprimento precisamente n em um dígrafo (possivelmente cíclico) é ⊕L - completo , observe que isso equivale a coeficientes de computação de alguns poder de uma matriz arbitrária sobre

, que é ⊕L - completo . Essa resposta é essencialmente como uma redução da alimentação da matriz (usando uma construção padrão de M como uma matriz de blocos que consiste apenas em cópias da matriz de adjacência arbitrária de G nos blocos fora da diagonal superior e 1 na diagonal) nos circuitos CNOT . Boa resposta!

F_{2}

$\mathbb F_2$

Niel de Beaudrap

Você não precisa passar pela alimentação da matriz, cuja ⊕L-completude é mais difícil de provar. ⊕L é definido contando no mod 2 os caminhos aceitos de uma máquina de Turing não-determinística do espaço de logs (presumo que com relógio de ponto polinomial, de modo que o número seja garantido como finito), que é o mesmo que contar caminhos no gráfico de configuração do máquina (é fácil organizar que todos os caminhos terminem na mesma configuração e que os caminhos tenham o mesmo comprimento, fazendo a máquina entrar em loop até que o relógio expire e depois entrar em um estado de aceitação fixo).

Emil Jeřábek apoia Monica

Suponho que a partir enfocando as idéias no papel Stucture ea importância das classes LOGSPACE-Mod por Buntrock et al. , Me acostumei muito a pensar em termos de número de caminhos de comprimento arbitrário em um dígrafo acíclico e de problemas semelhantes ao DET , como produtos e potências matriciais que estão naturalmente conectados a ele.

Niel de Beaudrap

Redução do espaço de log dos circuitos Parity-L para CNOT?

Questão.

Detalhes

Respostas: