A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

Parameterized Algorithms to Compute Ising Partition Function Algoritmos parametrizados para calcular a função de partição de ising

Hidefumi HIRAISHI, Hiroshi IMAI, Yoichi IWATA, Bingkai LIN

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1398-1403
Data de publicação
2018/09/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E101.A.1398
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria

autores

Hidefumi HIRAISHI
  The University of Tokyo
Hiroshi IMAI
  The University of Tokyo
Yoichi IWATA
  National Institute of Informatics
Bingkai LIN
  National Institute of Informatics

Palavra-chave