Simple encoding of a quantum circuit amplitude as a matrix permanent

2009/09/16 by Terry Rudolph · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Quantum Computing Algorithms and Architecture #Quantum many-body systems #cs.CC #quant-ph

paper · pdf · doi:10.1103/physreva.80.054302

6 figures

arxiv created 2009/09/16 · openalex publication_date 2009/11/25 · arxiv updated 2013/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A simple construction is presented which allows computing the transition amplitude of a quantum circuit to be encoded as computing the permanent of a matrix which is of size proportional to the number of quantum gates in the circuit. This opens up some interesting classical Monte Carlo algorithms for approximating quantum circuits.

Citations

• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• On the quantum computational complexity of the Ising spin glass partition function and of knot invariants

Cited by

• A linear-optical proof that the permanent is # P -hard