A simple encoding of a quantum circuit amplitude as a matrix permanent

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.

6 figures

References in corpus (2)

• 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 in corpus (10)

• Average-case complexity versus approximate simulation of commuting quantum computations
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• A Linear-Optical Proof that the Permanent is #P-Hard
• Quantum circuits and low-degree polynomials over F_2
• The Computational Complexity of Linear Optics
• Quantum supremacy of the many-body fluctuations in the occupations of the excited particle states in a Bose-Einstein-condensed gas
• Symbolic Synthesis of Clifford Circuits and Beyond
• On the role of coherence for quantum computational advantage
• Generalized Boolean Functions and Quantum Circuits on IBM-Q
• Quantum estimation bound of Gaussian matrix permanent