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

DOI10.1007/S11128-008-0084-7MaRDI QIDQ1007123zbMATH OpenOpenAlexFDO

Authors Joseph Geraci

Publication date 27 March 2009

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.4833

zbMATH Keywords

quantum algorithmsIsing partition functionBQP-complete

Mathematics Subject Classification ID

Quantum computation (81P68) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Applications of graph theory to circuits and networks (94C15)

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.

Recommendations

• Classical Ising model test for quantum circuits
• On the exact evaluation of certain instances of the Potts partition function by quantum computers
• The complexity of approximating complex-valued Ising and Tutte partition functions
• Low depth quantum circuits for Ising models
• Commuting quantum circuits and complexity of Ising partition functions

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 5320307 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Approximate Counting and Quantum Computation
• Exact universality from any entangling gate without inverses
• Multiparty entanglement in graph states
• On the exact evaluation of certain instances of the Potts partition function by quantum computers
• On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
• Quantum Complexity Theory
• Quantum Computability
• Quantum computation and the evaluation of tensor networks
• Quantum computing and quadratically signed weight enumerators
• Simulating Quantum Computation by Contracting Tensor Networks
• Strengths and Weaknesses of Quantum Computing

Cited in

(7)

• Commuting quantum circuits and complexity of Ising partition functions
• On the exact evaluation of certain instances of the Potts partition function by quantum computers
• Calculation of partition function of Ising model on quantum computer
• Recombination operators and selection strategies for evolutionary Markov chain Monte Carlo algorithms
• Classical Ising model test for quantum circuits
• Completeness of classical spin models and universal quantum computation
• Quantum algorithms for classical lattice models

This page was built for publication: A new connection between quantum circuits, graphs and the Ising partition function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007123)