PIRSA:12040079

Virtual Parallel Computing and a Search Algorithm Using Matrix Product States

APA

Chamon, C. (2012). Virtual Parallel Computing and a Search Algorithm Using Matrix Product States. Perimeter Institute for Theoretical Physics. https://pirsa.org/12040079

MLA

Chamon, Claudio. Virtual Parallel Computing and a Search Algorithm Using Matrix Product States. Perimeter Institute for Theoretical Physics, Apr. 20, 2012, https://pirsa.org/12040079

BibTex

          @misc{ scivideos_PIRSA:12040079,
            doi = {10.48660/12040079},
            url = {https://pirsa.org/12040079},
            author = {Chamon, Claudio},
            keywords = {Quantum Matter},
            language = {en},
            title = {Virtual Parallel Computing and a Search Algorithm Using Matrix Product States},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2012},
            month = {apr},
            note = {PIRSA:12040079 see, \url{https://scivideos.org/index.php/pirsa/12040079}}
          }
          

Claudio Chamon Boston College

Talk numberPIRSA:12040079
Source RepositoryPIRSA
Collection

Abstract

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.