Claudio Chamon, Eduardo R. Mucciolo
We propose a form of parallel computing on classical computers that is based
on matrix product states. The virtual parallelization is accomplished by
evolving all possible results for multiple inputs, with bits represented by
matrices. The action by classical probabilistic 1-bit and deterministic 2-bit
gates such as NAND are implemented in terms of matrix operations and, as
opposed to quantum computing, it is possible to copy bits. We present a way to
explore this method of computation to solve search problems and count the
number of solutions. We argue that if the classical computational cost of
testing solutions (witnesses) requires less than O(n^2) local two-bit gates
acting on n bits, the search problem can be fully solved in subexponential
time. Therefore, for this restricted type of search problem, the virtual
parallelization scheme is faster than Grover's quantum algorithm.
View original:
http://arxiv.org/abs/1202.1809
No comments:
Post a Comment