As matrizes de Pauli são um conjunto de matrizes 2x2 que aparecem muito comumente na física quântica (não, você não precisa conhecer nenhuma física quântica para esse desafio). Se incluirmos a identidade no conjunto, as quatro matrizes são:

 σ0 =      σ1 =      σ2 =      σ3 = 
[1  0]    [0  1]    [0 -i]    [1  0]
[0  1]    [1  0]    [i  0]    [0 -1]

Multiplicando dois destes dará sempre uma outra matriz Pauli, embora possa ser multiplicada por uma das fases complexas 1, i, -1, -i. Por exemplo ,.σ1σ3 = -iσ2

Sua tarefa é multiplicar um número de matrizes Pauli e retornar a matriz e a fase resultantes. A entrada será fornecida como uma sequência de dígitos não vazia 0para 3representar as matrizes para . A saída deve ser uma cadeia de caracteres contendo um único dígito para a matriz resultante, opcionalmente precedida por , ou para indicar a fase ( é para ).σ0σ3i--i--1

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

Você não deve usar nenhum recurso interno (ou de terceiros) relacionado às matrizes Pauli.

Isso é código de golfe, a resposta mais curta (em bytes) vence.

Casos de teste

1 => 1
13 => -i2
000 => 0
123 => i0
03022 => 3
02132230 => -i3
1320130100032 => i2
311220321030322113103 => -2
0223202330203313021301011023230323 => -i0
1323130203022111323321112122313213130330103202032222223 => -1

Pitão, 47 bytes

Eu acho que isso ainda é jogável. Mas supera muito o CJam.

p.U&-=T*q3l{[0bZ)^_1%-Zb3xbZmvdz@+c"i - -i")khT

Experimente on-line: Demonstration or Test Suite

Explicação

Determinar o tipo de matriz resultante é simplesmente armazenar todos os números.

Ao multiplicar 2 matrizes A*B, a fase muda, se não uma das matrizes for σ0e A != B.

                                                 implicit: T=10, z=input string
                            mvdz                 evaluate each char of the input 
 .U                                              reduce: b=first value, for Y in mvdz[1:]
    -=T                                            T -= ...
        q3l{[0bZ)                                     (3 == len(set([0,b,Z])))
       *         ^_1%-Zb3                             * (-1)^((Z-b)%3)
   &                                               and
                         xbY                       update b by (b xor Y)
                                 +c"i - -i")k    the list ["i", "-", "-i", ""]
                                @            hT  take the element at index T+1 (modulo wrapping)
p                                                print phase and matrix

Python 2, 108 89 87 86 bytes

x=y=0
for m in map(int,raw_input()):x+=m*y and(m-y)%3*3/2;y^=m
print"--i"[~x%4::2]+`y`

(Obrigado a @grc e @xnor pela ajuda)

Explicação

Vamos dividir o coeficiente e a matriz base. Se focarmos apenas na matriz base, obteremos esta tabela de multiplicação (por exemplo , 13é -i2, então colocamos 2):

  0123

0 0123
1 1032
2 2301
3 3210

que passa a ser a mesma coisa que fazer xor bit a bit.

Agora vamos nos concentrar nos coeficientes. Se deixarmos 0123denotar 1,i,-1,-irespectivamente, obtemos:

  0123

0 0000
1 0031
2 0103
3 0310

Para isso, primeiro verificamos se qualquer número é 0 m*y, cuidando da coluna esquerda e da linha superior. Adicionar (m-y)%3então fornece:

  0123

0 0000
1 0021
2 0102
3 0210

que está perto, exceto que temos em 2vez de 3. Nós explicamos isso realizando *3/2.

Para indexação, notamos que, se pegarmos a string "--i"e selecionarmos cada segundo caractere a partir dos índices 0123que obtivermos "-i","-","i","".

Retina , 77 bytes

Pensei em usar essa oportunidade para exibir um novo recurso Retina: loops de vários estágios. Isso deve reduzir consideravelmente muitas tarefas (especialmente a substituição condicional).

ii
-
+`(.)\1|0

(.)-|(\d)(\d)
-$1$3$2
12
i3
23
i1
31
i2
)`(\d)i
i$1
^\D*$
$&0

Retina é minha própria linguagem de programação baseada em regex. O código-fonte pode ser agrupado em estágios: cada estágio consiste em duas linhas em que o primeiro contém a regex (e potencialmente alguma configuração) e a segunda linha é a sequência de substituição. As etapas são aplicadas ao STDIN em ordem e o resultado final é impresso em STDOUT.

Você pode usar o acima diretamente como um arquivo de origem com a -sopção de linha de comando. No entanto, não estou contando a opção, porque você também pode colocar cada linha em um arquivo separado (então você perde 15 bytes para as novas linhas, mas adiciona +15 para os arquivos adicionais).

Explicação

A novidade desta solução é )a penúltima etapa. Isso fecha um loop de vários estágios. Não há correspondência (, o que significa que o loop inicia implicitamente no primeiro estágio. Portanto, os sete primeiros estágios são repetidos até que uma passagem completa pelos sete pare de alterar o resultado. Esses 7 estágios simplesmente realizam várias transformações que reduzem gradualmente o número de matrizes na cadeia e combinam fases. Quando alcançamos o resultado final, nenhum dos sete padrões corresponde mais e o loop termina. Depois, adicionamos um 0 se ainda não houver um dígito no resultado (como os estágios acima simplesmente eliminam todas as identidades, incluindo o resultado).

Aqui está o que as etapas individuais fazem:

ii
-

Combina todos os pares de iem -para reduzir os caracteres da fase.

+`(.)\1|0
<empty>

Agora, se houver dois caracteres idênticos consecutivos restantes, são uma --ou duas matrizes idênticas. Nos dois casos, multiplicá-los fornece a identidade. Mas como não precisamos de identidades, removemos todas elas e as identidades explícitas 0também. Esta etapa é repetida em si mesma +até que o resultado pare de mudar. Isso garante que coisas como 123321sejam resolvidas completamente, de forma que a próxima etapa possa assumir que todos os pares de dígitos são distintos.

(.)-|(\d)(\d)
-$1$3$2

Na verdade, são duas transformações separadas em uma (para golfitude). Observe que se a primeira alternativa corresponder $2e $3estiver vazia, e se a segunda corresponder $1estiver vazia. Portanto, isso pode ser decomposto nessas duas etapas:

(\d)(\d)
-$2$1

Isso apenas troca todos os pares de dígitos e adiciona um sinal de menos. Desde que removeu todos os 0s e todos os pares idênticos, isto só irá corresponder 12, 23, 31, 21, 32, 13. Essa etapa pode parecer estranha, mas me permite verificar apenas metade desses casos mais tarde, porque os que não puderem ser processados ​​serão trocados aqui na próxima iteração.

A outra parte do estágio acima foi:

(.)-
-$1

Isso gradualmente move os -sinais para a esquerda (uma posição por iteração). Faço isso de modo que, em última análise, todos estejam próximos um do outro e sejam resolvidos na etapa anterior.

12
i3
23
i1
31
i2

Agora, esses três estágios simplesmente resolvem os três pares de produtos. Como eu disse acima, isso capturará apenas metade dos casos relevantes, mas a outra metade será tratada na próxima iteração, após a etapa anterior ter trocado todos os pares.

)`(\d)i
i$1

Este é o último estágio do loop. É semelhante ao que se desloca -para a esquerda, exceto i. A principal diferença é que este troca iapenas com dígitos. Se eu usasse (.)i, nos casos em que eu recebesse um -iou i-os dois, seriam trocados indefinidamente e o programa não seria encerrado. Portanto, isso apenas os troca à direita dos -sinais. Isso é suficiente - desde que todos -e iapareçam juntos em algum momento, eles possam ser resolvidos corretamente.

^\D*$
$&0

A etapa final (fora do loop). Lembre-se de que sempre excluímos todas as identidades; portanto, se o resultado for realmente a identidade (vezes uma fase), não teremos mais o dígito necessário na saída; por isso, o adicionamos novamente.

Como exemplo, aqui estão todas as formas intermediárias de 0223202330203313021301011023230323(pulando estágios que não executam nenhuma alteração):

0223202330203313021301011023230323

321321312        # Remove identities
-23-31-12-132    # Swap all pairs
-23-31-i3-132    # Resolve 12
-i1-31-i3-132    # Resolve 23
-i1-i2-i3-132    # Resolve 31
-i-1i-2i-3-312   # Move - to the left and swap pairs
-i-1i-2i-3-3i3   # Resolve 12
-i-i1-i2-3-i33   # Move i to the left
-i-i1-i2-3-i     # Remove identities
--ii-1i-2-3i     # Move - to the left
--ii-i1-2-i3     # Move i to the left
----i1-2-i3      # Resolve ii
i1-2-i3          # Remove identities
i-1-2i3          # Move - to the left
i-1-i23          # Move i to the left
-i-1i-32         # Move - to the left and swap pairs
-i-i1-32         # Move i to the left
--ii-1-23        # Move - to the left and swap pairs
--ii-1-i1        # Resolve 23
----1-i1         # Resolve ii
1-i1             # Remove identities
-1i1             # Move - to the left
-i11             # Move i to the left
-i               # Remove identities. Now the loop can't change this any longer.
-i0              # Fix the result by adding in the 0.

CJam, 58 56 bytes

Estou certo de que isso pode ser muito praticado, mas aqui vai:

L'i'-"-i"]q{+:G$i:XA<X{GiB%_2m8%!+m<XB%gX3%3-z*}?s}*\0=o

Experimente on-line aqui ou execute o pacote completo aqui