A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
arXiv:0801.4833 · doi:10.1007/s11128-008-0084-7
Abstract
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.
12 pages, 2 figures
References in corpus (13)
- Strengths and Weaknesses of Quantum Computing
- Multi-party entanglement in graph states
- On the Power of One Bit of Quantum Information
- Simulating quantum computation by contracting tensor networks
- A practical scheme for quantum computation with any two-qubit entangling gate
- The BQP-hardness of approximating the Jones Polynomial
- Universal Quantum Computation through Control of Spin-Orbit Coupling
- On measurement-based quantum computation with the toric code states
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- Quantum algorithms for spin models and simulable gate sets for quantum computation
- On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
- Several natural BQP-Complete problems
- On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
Cited by in corpus (6)
- Quantum Algorithm Implementations for Beginners
- Quantum algorithms for classical lattice models
- Completeness of classical spin models and universal quantum computation
- Classical Ising model test for quantum circuits
- Classical spin systems and the quantum stabilizer formalism: general mappings and applications
- Quantum computation and the evaluation of tensor networks