Complexity classification of two-qubit commuting hamiltonians

Adam Bouland, Laura Mancinska, Xue Zhang

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

5 Citations (Scopus)

Abstract

We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit 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 two-qubit 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.

Original languageEnglish
Title of host publication31st Conference on Computational Complexity, CCC 2016
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages28:1-28:33
Volume50
ISBN (Electronic)9783959770088
DOIs
Publication statusPublished - 1 May 2016
Event31st Conference on Computational Complexity, CCC 2016 - Tokyo, Japan
Duration: 29 May 20161 Jun 2016

Conference

Conference31st Conference on Computational Complexity, CCC 2016
CountryJapan
CityTokyo
Period29/05/161/06/16

Keywords

  • Commuting hamiltonians
  • Gate classification theorems
  • IQP
  • Quantum computing
  • Sampling problems

Fingerprint Dive into the research topics of 'Complexity classification of two-qubit commuting hamiltonians'. Together they form a unique fingerprint.

Cite this