The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
O cálculo da função de partição do modelo de Ising em um gráfico tem sido investigado em ambos os lados da ciência da computação e da física estatística, produzindo resultados férteis de casos P, casos FPTAS/FPRAS, inaproximabilidade e intratabilidade. Recentemente, a computação quântica baseada em medição, bem como o recozimento quântico, abrem outra ponte entre dois campos, relacionando uma rede de tensores de árvore que representa um estado de gráfico quântico a uma decomposição de classificação do gráfico. Este artigo torna esta ponte mais larga em ambas as direções. Um algoritmo $O^*(2^{ rac{omega}{2} bw(G)})$-time é desenvolvido para a função de partição em n-gráfico de vértice G com decomposição de galhos em largura bw(G), Onde O* ignora um fator polinomial em n e ω é o parâmetro de multiplicação da matriz menor que 2.37287. São fornecidos algoritmos relacionados de $O^*(4^{rw( ilde{G})})$ tempo para a rede de tensores de árvore que são de interesse na computação quântica, dada a decomposição de classificação de um grafo subdividido $ ilde{G}$ com largura $rw(ilde{G})$. Esses algoritmos são parâmetros exponenciais, ou seja, O*(cp) para constante c e parâmetro p, e tal algoritmo não é conhecido para um caso mais geral de cálculo do polinômio de Tutte em termos de bw(G) (o melhor momento atual é O*(min{2n, bw(G)O(bw(G))})) com resultado negativo em termos de largura de clique, em relação à largura de classificação, em ETH.
Hidefumi HIRAISHI
The University of Tokyo
Hiroshi IMAI
The University of Tokyo
Yoichi IWATA
National Institute of Informatics
Bingkai LIN
National Institute of Informatics
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Hidefumi HIRAISHI, Hiroshi IMAI, Yoichi IWATA, Bingkai LIN, "Parameterized Algorithms to Compute Ising Partition Function" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1398-1403, September 2018, doi: 10.1587/transfun.E101.A.1398.
Abstract: Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An $O^*(2^{ rac{omega}{2} bw(G)})$-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of $O^*(4^{rw( ilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $ ilde{G}$ with width $rw( ilde{G})$. These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1398/_p
Copiar
@ARTICLE{e101-a_9_1398,
author={Hidefumi HIRAISHI, Hiroshi IMAI, Yoichi IWATA, Bingkai LIN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Parameterized Algorithms to Compute Ising Partition Function},
year={2018},
volume={E101-A},
number={9},
pages={1398-1403},
abstract={Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An $O^*(2^{ rac{omega}{2} bw(G)})$-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of $O^*(4^{rw( ilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $ ilde{G}$ with width $rw( ilde{G})$. These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.},
keywords={},
doi={10.1587/transfun.E101.A.1398},
ISSN={1745-1337},
month={September},}
Copiar
TY - JOUR
TI - Parameterized Algorithms to Compute Ising Partition Function
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1398
EP - 1403
AU - Hidefumi HIRAISHI
AU - Hiroshi IMAI
AU - Yoichi IWATA
AU - Bingkai LIN
PY - 2018
DO - 10.1587/transfun.E101.A.1398
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2018
AB - Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An $O^*(2^{ rac{omega}{2} bw(G)})$-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of $O^*(4^{rw( ilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $ ilde{G}$ with width $rw( ilde{G})$. These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.
ER -