A new connection between quantum circuits, graphs and the Ising partition function

摘要

We present a simple construction that maps quantum circuits to graphs and vice-versa. Inspired by the results of D. A. Lidar linking the Ising partition function with quadratically signed weight enumerators (QWGTs), we also present a problem for the additive approximation of a function over hypergraphs related to the generating function of Eulerian subgraphs for ordinary graphs. Further, if E is an oracle that returns approximations of this function, we prove that PE = BQP. We also discuss connections with the Ising partition function.