A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs

Understand

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 BQP-complete problem for the additive approximation of a function over hypergraphs related to the generating function of Eulerian subgraphs for ordinary graphs.
• We discuss connections with the Ising partition function.