2012/08/31 by Kristan Temme, Temme, Kristan, Pawel Wocjan +1
Computer Science · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.DM #cs.DS #quant-ph
paper · pdf · doi:10.48550/arxiv.1208.6589
arxiv created 2012/08/31 · arxiv updated 2012/09/03
We present an efficient algorithm for computing the permanent for matrices of size N that can written as a product of L block diagonal matrices with blocks of size at most 2. For fixed L, the time and space resources scale linearly in N, with a prefactor that scales exponentially in L. This class of matrices contains banded matrices with banded inverse. We show that such a factorization into a product of block diagonal matrices gives rise to a circuit acting on a Hilbert space with a tensor product structure and that the permanent is equal to the transition amplitude of this circuit and a product basis state. In this correspondence, a block diagonal matrix gives rise to one layer of the circuit, where each block to a gate acting either on a single tensor component or on two adjacent tensor components. This observation allows us to adopt matrix product states, a computational method from condensed matter physics and quantum information theory used to simulate quantum systems, to evaluate the transition amplitude.