Multiply Pauli Matrices

Question

The Pauli matrices are a set of 2x2 matrices which appear very commonly in quantum physics (no, you don't need to know any quantum physics for this challenge). If we include the identity in the set, the four matrices are:

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

Multiplying two of these will always give another Pauli matrix, although it may be multiplied by one of the complex phases 1, i, -1, -i. For instance, σ1σ3 = -iσ2.

Your task is to multiply a number of Pauli matrices and return the resulting matrix and phase. Input will be given as a non-empty string of digits 0 to 3 representing the matrices σ0 to σ3. The output should be a string containing a single digit for the resulting matrix, optionally preceded by i, - or -i to indicate the phase (- is for -1).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You must not use any built-in (or 3rd-party) features related to Pauli matrices.

This is code golf, the shortest answer (in bytes) wins.

Test Cases

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

Answer 1

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`

(Thanks to @grc and @xnor for the help)

Explanation

Let's split up the coefficient and the base matrix. If we focus on the base matrix only, we get this multiplication table (e.g. 13 is -i2, so we put 2):

  0123

0 0123
1 1032
2 2301
3 3210

which just happens to be the same thing as doing bitwise xor.

Now let's focus on the coefficients. If we let 0123 denote 1,i,-1,-i respectively, we get:

  0123

0 0000
1 0031
2 0103
3 0310

For this we first check if either number is 0 by doing m*y, taking care of the left column and top row. Adding in (m-y)%3 then gives:

  0123

0 0000
1 0021
2 0102
3 0210

which is close, except that we have 2 instead of 3. We account for this by performing *3/2.

For indexing, we notice that if we take the string "--i" and select every second character starting from indices 0123 we get "-i","-","i","".

Answer 2

Retina, 77 bytes

I thought I'd use this opportunity to show off a new Retina feature: multi-stage loops. This should shorten many tasks considerably (especially conditional replacement).

ii
-
+`(.)\1|0

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

Retina is my own regex-based programming language. The source code can be grouped into stages: each stage consists of two lines where the first contains the regex (and potentially some configuration) and the second line is the replacement string. The stages are then applied to STDIN in order and the final result is printed to STDOUT.

You can use the above directly as a source file with the -s command-line switch. However, I'm not counting the switch, because you can also just put each line in a separate file (then you lose 15 bytes for the newlines, but add +15 for the additional files).

Explanation

The new thing about this solution is the ) in the penultimate stage. This closes a multi-stage loop. There is no matching (, which means that the loop implicitly starts at the first stage. Hence, the first 7 stages are repeated until a full pass through all 7 of them stops changing the result. These 7 stages simply perform various transformations which gradually reduce the number of matrices in the string and combine phases. Once we reach the final result, none of the seven patterns matches any more and the loop ends. Afterwards, we append a 0 if there is no digit in the result yet (as the above stages simply drop all identities, including the result).

Here is what the individual stages do:

ii
-

Combines all pairs of i into - to reduce the phase characters.

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

Now if there are two consecutive identical characters left, it's either -- or two identical matrices. In either case, multiplying them gives the identity. But we don't need identities, so we just remove all of them, and the explicit identities (the 0s) as well. This stage is repeated in itself with + until the result stops changing. This ensures that things like 123321 get resolved completely, such that the next step can assume that all pairs of digits are distinct.

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

This is actually two separate transformations in one (for golfitude). Note that if the first alternative matches, $2 and $3 are empty, and if the second one matches $1 is empty. So this can be decomposed into these two steps:

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

This just swaps all pairs of digits and adds a minus sign. Since we removed all 0s and all identical pairs, this will only match 12, 23, 31, 21, 32, 13. This step may seem weird, but it allows me to only check for half of these cases later on, because the ones I can't process then will be swapped here in the next iteration.

The other part of the above stage was:

(.)-
-$1

This gradually moves - signs all the way to the left (one position per iteration). I do this such that ultimately they are all next to each other and get resolved in the earlier step.

12
i3
23
i1
31
i2

These three stages now simply resolve the three pairs of products. As I said above, this will only catch half of the relevant cases, but the other half will be taken care of in the next iteration, after the previous step swapped all pairs.

)`(\d)i
i$1

This is the last stage of the loop. It's similar to the one that shifts - to the left, except for i. The main difference is that this one swaps i only with digits. If I used (.)i then in cases where I get a -i or i- the two would be swapped indefinitely and the program wouldn't terminate. So this only swaps them to the right of the - signs. This is sufficient - as long as all - and i appear together at some point, they can be resolved correctly.

^\D*$
$&0

The final step (outside of the loop). Remember that we always deleted all identities, so if the result is actually the identity (times a phase), then we won't have the required digit in the output any more, so we add it back.

As an example, here are all the intermediate forms of 0223202330203313021301011023230323 (skipping stages that don't perform any changes):

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.

Answer 3

Pyth, 47 bytes

I guess this is still golfable. But it beats CJam by a lot.

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

Try it online: Demonstration or Test Suite

Explanation

Determining the resulting matrix type is simply xoring all the numbers.

While multiplying 2 matrices A*B, the phase changes, if non of the matrices is σ0 and 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

Answer 4

CJam, 58 56 bytes

I am sure this can be golfed a lot, but here it goes:

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

Try it online here or run the complete suite here