Department of Physics, Boston University, Boston, Massachusetts 02215, USA.
Phys Rev Lett. 2012 Jul 20;109(3):030503. doi: 10.1103/PhysRevLett.109.030503.
We propose a form of parallel computing on classical computers that is based on matrix product states. The virtual parallelization is accomplished by representing bits with matrices and by evolving these matrices from an initial product state that encodes multiple inputs. Matrix evolution follows from the sequential application of gates, as in a logical circuit. The action by classical probabilistic one-bit and deterministic two-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(n2) 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.
我们提出了一种基于矩阵乘积态的经典计算机上的并行计算形式。虚拟并行化是通过用矩阵表示位，并通过从编码多个输入的初始乘积态演化这些矩阵来实现的。矩阵演化遵循门的顺序应用，就像在逻辑电路中一样。经典概率单比特和确定性双比特门（如 NAND）的作用是通过矩阵运算来实现的，与量子计算不同，它可以复制位。我们提出了一种探索这种计算方法来解决搜索问题和计算解的数量的方法。我们认为，如果测试解（证据）的经典计算成本需要少于 O(n^2) 在 n 位上作用的局部双比特门，则可以在亚指数时间内完全解决搜索问题。因此，对于这种受限类型的搜索问题，虚拟并行化方案比 Grover 的量子算法更快。
