Journal article

### The complexity of approximating complex-valued Ising and Tutte partition functions

Abstract:

We study the complexity of approximately evaluating the Ising and Tutte partition functions with complex parameters. Our re- sults are partly motivated by the study of the quantum complexity classes BQP and IQP. Recent results show how to encode quantum computations as evaluations of classical partition functions. These re- sults rely on interesting and deep results about quantum computation in order to obtain hardness results about the dificulty of (classically) evaluating the partition func...

Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

### Access Document

Files:
• (pdf, 590.7KB)
Publisher copy:
10.1007/s00037-017-0162-2

### Authors

More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
Springer Verlag Publisher's website
Journal:
Computational Complexity Journal website
Volume:
26
Issue:
4
Pages:
765-833
Publication date:
2017-09-13
Acceptance date:
2017-02-17
DOI:
EISSN:
1420-8954
ISSN:
1016-3328
Pubs id:
pubs:680717
URN:
uri:6b1b3ef0-9556-472d-b9a1-d36bde086ec2
UUID:
uuid:6b1b3ef0-9556-472d-b9a1-d36bde086ec2
Local pid:
pubs:680717
Keywords: