Fetching the paper…

Reading the bibliography…

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

2009

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

Rudolph, Terry

Original
PDF
Post on X

Understand

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.

Built on

L. G. Valiant, Theoret. Comput. Sci. 8
1979
Earlier work this paper cites.
A. Ehrenfeucht and M. Karpinski, The Computational Complexity of (XOR, AND)-Counting Problems, ICSI Technical Report TR-90-033, July 1990
1990
Earlier work this paper cites.
Y. Shi, Quantum Information and Computation, 3
2003
Earlier work this paper cites.

Similar

C.D. Godsil and I. Gutman in Algebraic Methods in Graph Theory, Vol. I, II,(Szeged, 1978), North-Holland, Amsterdam-New York, 1981; N. Karmarkar, R. Karp, R. Lipton, L. Lovasz, M. Luby, SIAM J. Comput. 22
2004
Cited alongside, same era.
C. M. Dawson et al, Quantum Information and Computation, 5
2005
Cited alongside, same era.
M. Loebl and I. Moffatt, arxiv:0705.4548
Original
Cited in the paper.
T.-C. Wei and S. Severini, arxiv:0905.0012
Original
Cited in the paper.

Then

L. Gurvits, On the Complexity of Mixed Discriminants and Related Problems, Mathematical Foundations of Computer Science 2005, Springer Berlin / Heidelberg Vol. 3618, (2005)
Original
2005
Later among the works it cites.
M. Freedman, A. Kitaev, M. Larsen and Z. Wang, Bull. Amer. Math. Soc. 40
2006
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…