How to tensor product in J, and what makes matrix product special

[LdBeth]

I'm doing some quantum computing exercises in J, for some background
simulating quantum computing device is mostly about applying
unitary matrices to complex number vectors, which fits well with APL
like languages.

We all know that (generalized) matrix product in APL/J works well on
rank 1 array as if it is already raveled:

]S=2 2$1 0 0 0j1
1 0
0 0j1
]one=:0 1
0 1
S +/ . * one
0 0j1
S (+/ . *) ,. one
0
0j1


An important concept used in quantum computing is tensor product, which
is essentially taking the outer product of the two arrays and
join them together.

The best definition I could find so far is

tp =: {{ (,./^:(#$y)) x */ y }}
(i.2 2)tp i.4 4
0 0 0 0 0 1 2 3
0 0 0 0 4 5 6 7
0 0 0 0 8 9 10 11
0 0 0 0 12 13 14 15
0 2 4 6 0 3 6 9
8 10 12 14 12 15 18 21
16 18 20 22 24 27 30 33
24 26 28 30 36 39 42 45

But this definition does not generalize well to rank 1 arrays, i.e.

one tp one
0 0
0 1

Where I want it to work like generalized matrix product:

one tp&.(,. :.,) one
0 0 0 1

Any comments?

---
LdBeth

[Viktor Grigorov]

Awhile back, I'd asked for a similar thing, a tensor _inner_ product. Raul Miller responded. I have the whole (or its majority) saved in my snippets file.

NB. Viktor Grigorov mentioned a need for a tensor product.
NB. I have been trying to think of a good simple expression, but there's special cases.
NB. Still, I figured maybe someone might make use of this:

tip=:{{assert.1=#,m
select.m=.{.,m
case.0 do.*/
NB. case.1 do.+/ .*
NB. case.2 do.+/@(,/)@(*"2 _)
NB. case. _ do.+/@,@(*"_)
case.do.+/@(,/^:(m-1))@(*"(m,_))end.}}

NB. Example use:

(i.2 3) 1 tip i.3 4
20 23 26 29
56 68 80 92
(i.2 3) +/ .* i.3 4
20 23 26 29
56 68 80 92
(i.2 3 5) 2 tip i.3 5 7
7105  7210  7315  7420  7525  7630  7735
18130 18460 18790 19120 19450 19780 20110

NB. Basically, the m argument to tip (tensor inner product) is the number
NB. of pairs of dimensions in the argument arrays which should be summed
NB. in the tensor product.

NB. You can use _ if you want all dimensions to be paired.

NB. The commented out lines in the definition could be removed or instated
NB. (with the NB. toggled out) and that should make no difference in the
NB. result, other than a slightly different intermediate representation of
NB. the inner product.

NB. As you can see in my above quicky examples, the m argument to tip is
NB. the number of (inner) dimensions which must match between the two
NB. array arguments. These dimensions vanish from the shape of the result.



NB. I should add that the definition of tip which I supplied assumes
NB. you're running the current j903 beta.
NB. Here's a definition which works on earlier released versions of J:

tip=:1 :0
assert. 1=#,m
select. m=. {.,m
case. 0 do. */
NB. case. 1 do. +/ .*
NB. case. 2 do.
NB. +/@(,/)@(*"2 _)
NB. case. _ do.
NB. +/@,@(*"_)
case. do.
+/@(,/^:(m-1))@(*"(m,_))
end.
)

NB. I should add that if you need the matched dimensions of the right
NB. argument to be reversed, you could replace " in the definition with a
NB. conjunction which reverses the order of those dimensions in that
NB. argument. For example, you could replace " with irank:

irank=:2 :0
urank=. {:3$&.|.n
yrank=. #$y
transpose=. |.(-urank){.i.yrank
x u"n transpose|:y
)

NB. (This leaves some edge cases unhandled -- negative n and degenerate y
NB. -- but support for those cases could be added if this were truly
NB. useful.)

$ (i.2 3 5 7) +irank 2 i.2 3 7 5
2 3 5 7

NB. But, like you said, it all depends on the definitions. And, it seemed
NB. to me that working with the natural behavior of " was good.

NB. (And you can always transpose manually, outside of the inner product
NB. definition.)


NB. Oops, I goofed.
NB. it's x that needs its trailing dimensions reversed, not y.
NB. And, because of how this works, x should have all of its dimensions
NB. reversed. So irank is not actually needed.
NB. So, here's an implementation that works like you had suggested:

tip=:1 :0
assert. 1=#,m
select. m=. {.,m
case. 0 do. */
NB. case. 1 do. +/ .*
NB. case. 2 do.
NB. +/@(,/)@(*"2 _)
NB. case. _ do.
NB. +/@,@(*"_)
case. do.
+/@(,/^:(m-1))@((* |:)~"(m,_))
end.
)

$(i.2 3 7 5) 2 tip i.5 7 11 13
2 3 11 13

NB. mm...
NB. I guess when working with tensors, 0 tip 1 would be the identity operation.
NB. For example:

(i.3 3 3)-:0 tip&1 i.3 3 3
1

NB. But it's also possible to find identity tensors for other tip operations.

(i.3 3 3) -:(i.3 3 3)1 tip =i.3
1
(i.3 3 3) -:1 tip&(=i.3) i.3 3 3 NB. alternate phrasing
1

NB. I have not thought about this enough to write an elegant id tensor
NB. generator, but it's easy enough to brute force:

genid=:4 :0
r=.0*raw=.i.(2*x)#y
p=: p:i.(1+x)#y
for_n.,raw do.
sel=.raw=n
try=. p x tip sel
if. try-:p**try do.
r=.r+sel
end.
end.
r
)

(i.3 3 3)-: (i.3 3 3) 2 tip 2 genid 3
1
(i.3 3 3)-: (i.3 3 3) 3 tip 3 genid 3
1


 


May 9, 2024, 21:04 by and...@foxmail.com:

> To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.
>

[Jan-Pieter Jacobs]

Tensor product is the same as the Kronecker product (at least in the quantum computing context).

A while back I wrote a generic Kronecker product that works for any dimension, which at that time was just a fun thing that was fun to generalise and I did not have a good use for, but later I found that in quantum computing it is handy:

https://code.jsoftware.com/wiki/Essays/Kronecker_Product

see the last part of the last code block.

If you find any mistakes in the definition, let me know, but from my experience, it should be fine.

Jan-Pieter

[LdBeth]

>>>>> In <CANS99cbPu77xttMtaVP6y6UA0tWPzDvqR4X8+JjgLzmmS=z5...@mail.gmail.com>
>>>>> Jan-Pieter Jacobs <janpiete...@gmail.com> wrote:
> [1 <text/plain; UTF-8 (7bit)>]
> [2 <text/html; UTF-8 (quoted-printable)>]

> Tensor product is the same as the Kronecker product (at least
> in the quantum computing context).

> A while back I wrote a generic Kronecker product that works
> for any dimension, which at that time was just a fun thing
> that was fun to generalise and I did not have a good use for,
> but later I found that in quantum computing it is handy:

> https://code.jsoftware.com/wiki/Essays/Kronecker_Product

> see the last part of the last code block.

> If you find any mistakes in the definition, let me know, but
> from my experience, it should be fine.

> Jan-Pieter

At certain point this morning I derived

tp=: *&:$ $0,@:|:*/ NB. wrong except for 1D array

which is close to the idea of your generalization, although I was not
able to figure out how to generate the permuted axis for |:

Your generalization does give the required the property for tensor
product in quantum computing, gives correct result for 2D arrays and
generalized to 1D and higher dimensions, thanks for the help!

Vikor> Awhile back, I'd asked for a similar thing, a tensor _inner_
Vikor> product. Raul Miller responded. I have the whole (or its
Vikor> majority) saved in my snippets file.

The inner product works differently than the outer product I requested
here but still thanks for providing the definition for making the
question complete.

---
LdBeth

[LdBeth]

NB. Generalized to arbitrary dimensions (not scalar, Jan-Pieter Jacobs, 2021-10-01) 
kpnd =: cs ($,) as |: *"0 _
NB. cs calculates final shape
cs =: ([: */&:> >.&# {.!.1&.> ;)&$
NB. as calculates required axis shuffle
as =: ([: ~.@,@|: ;&i. +&> 0 , [)&(#@$)

A slightly improvisation to avoid the boxes:

kpnd =: cs ($,) as |: */
cs =: ([: */ ,:!.1)&:$
as =: ~.@,@|:@(,:&:i. + 0 , [)&:(#@$)

---

LdBeth