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

DOI10.1007/S11128-008-0084-7zbMATH Open1160.81330arXiv0801.4833OpenAlexW2053152590MaRDI QIDQ1007123FDOQ1007123

Authors: Joseph Geraci 

Publication date: 27 March 2009

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

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.

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

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

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)

Cites Work

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

Cited In (6)

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

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)