Virtual Parallel Computing and a Search Algorithm Using Matrix Product States

    Authors

    C. Chamon;E. R. Mucciolo

    Comments

    Authors: contact us about adding a copy of your work at [email protected]

    Abbreviated Journal Title

    Phys. Rev. Lett.

    Keywords

    QUANTUM COMPUTER; SYSTEMS; Physics, Multidisciplinary

    Abstract

    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(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.

    Journal Title

    Physical Review Letters

    Volume

    109

    Issue/Number

    3

    Publication Date

    1-1-2012

    Document Type

    Article

    Language

    English

    First Page

    4

    WOS Identifier

    WOS:000306604700001

    ISSN

    0031-9007

    Share

    COinS
     

    Accessibility Statement

    This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.