Journal article icon

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...

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

Actions


Access Document


Files:
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

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP