Bouland, Adam ;
Mancinska, Laura ;
Zhang, Xue
Complexity Classification of TwoQubit Commuting Hamiltonians
Abstract
We classify twoqubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a twoqubit commuting Hamiltonian H which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one to sample from probability distributions which cannot be sampled from classically unless the polynomial hierarchy collapses. Furthermore, the only simulable Hamiltonians are those which fail to generate entanglement. This shows that generic twoqubit commuting Hamiltonians can be used to perform computational tasks which are intractable for classical computers under plausible assumptions. Our proof makes use of new postselection gadgets and Lie theory.
BibTeX  Entry
@InProceedings{bouland_et_al:LIPIcs:2016:5846,
author = {Adam Bouland and Laura Mancinska and Xue Zhang},
title = {{Complexity Classification of TwoQubit Commuting Hamiltonians}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {28:128:33},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5846},
URN = {urn:nbn:de:0030drops58469},
doi = {http://dx.doi.org/10.4230/LIPIcs.CCC.2016.28},
annote = {Keywords: Quantum Computing, Sampling Problems, Commuting Hamiltonians, IQP, Gate Classification Theorems}
}
2016
Keywords: 

Quantum Computing, Sampling Problems, Commuting Hamiltonians, IQP, Gate Classification Theorems 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Related Scholarly Article: 


Issue date: 

2016 
Date of publication: 

2016 