search

bollu / bollu.github.io

code + contents of my website, and programming life
http://bollu.github.io/
361 stars 23 forks source link

Grobner basis is an overkill. It is a system of linear equations #9

Closed pcpthm closed 4 years ago

pcpthm commented 5 years ago

Referring #computing-equivalent-gate-sets-using-grobner-bases.

The problem is a system of linear equations with 2^n - 2 variables a, axorb, axorc, etc. and 2^n - 1 equations (2^n equations with trivial 0 = 0 equation): 1*a + 1*b + 1*axorc + 1*bxorc = 1 (mod 8) for (a, b, c) = (1, 1, 0) etc. For example n = 3:

A =
[1 0 1 0 1 0]
[0 1 1 0 0 1]
[1 1 0 0 1 1]
[0 0 0 1 1 1]
[1 0 1 1 0 1]
[0 1 1 1 1 0]
[1 1 0 1 0 0]

b = (0, 1, 1, 0, 1, 0, 0, 1)

I know nothing about Sage but I implement this: https://gist.github.com/pcpthm/9bf91ed750cb2b4abc4009475680d908.

Linear equation on integer (not necessary prime) modulo ring can be solved by modified Gaussian eliminations in O(N^3) time where N is size of matrix ~ 2^n. This is still exponential in term of n but considerably faster / less power. Probably specialized algorithm can be implemented via FFT-like or something with O(N^2 * poly(n)) runtime.

Perhaps the matrix can be analyzed to get the idea of general solution.

bollu commented 5 years ago

Oh, sweet :) I didn't know that modified gaussian elimination worked on non-prime rings. I was under the impression that it required far more module theory than that!