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

Actions


Access Document


Files:
Publisher copy:
10.1007/s00037-017-0162-2

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
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
Source identifiers:
680717
Keywords:
Pubs id:
pubs:680717
UUID:
uuid:6b1b3ef0-9556-472d-b9a1-d36bde086ec2
Local pid:
pubs:680717
Deposit date:
2017-02-19

Terms of use


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