11
I’m not sure this is a research-level question, however solving linear systems over $\mathbb F_p$ is a $\mathrm{Mod}_p\mathrm L$-complete problem, hence in particular it is in $\mathrm{NC}^2$. More generally, linear algebra over $\mathbb F_{p^k}$ (at least for $k$ fixed) can be reduced to the $\mathbb F_p$ case.
9
If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical solution $x$ to a system $Ax=b$" then the answer is no. As you mention, the final quantum state in Harrow, Hassidim, Lloyd's algorithm does not immediately give you ...
6
Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing.
The easiest way to see this is to note that IND-CPA (left-or-right indistinguishability) implies real-or-random indistinguishability under chosen-plaintext attack:...
6
Yes, it is well known it can be done by diagonalizing the matrix using row and column operations. An outline of the procedure is given in the paper The Complexity of Solving Equations over Finite Groups by Goldmann and Russell.
answered May 28 '13 at 9:06
Kristoffer Arnsfelt Hansen
4,0152 gold badges23 silver badges34 bronze badges
6
A result known for over 30 years is that Guassian Elimination over $\mathbb F_2$ can be done by a various decompositions which takes $O(n^\omega)$, where $\omega$ is the matrix multiplication constant.
References:
Ibarra, O. , Moran, S. , and Hui, R. 1982. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of ...
4
In the general case, your problem is NP-hard, if you are working over a finite field (say, the integers modulo $p$). It is easy to see that the language of such circuits that are not identically zero is in NP (if it isn't identically zero, there exists a witness: an input that makes its output non-zero).
Also, we can reduce SAT to this problem. Consider a ...
2
Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) and preconditioned (F)GMRES (or other Krylov subspace methods) for arbitrary matrices.
The crucial part here is the preconditioner. There was recently (=21th ...
Only top voted, non community-wiki answers of a minimum length are eligible
