License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.21
URN: urn:nbn:de:0030-drops-88677
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8867/
Go to the corresponding LIPIcs Volume Portal

Bouland, Adam ; Fitzsimons, Joseph F. ; Koh, Dax Enshan

Complexity Classification of Conjugated Clifford Circuits

pdf-format:
LIPIcs-CCC-2018-21.pdf (0.7 MB)

Abstract

Clifford circuits - i.e. circuits composed of only CNOT, Hadamard, and pi/4 phase gates - play a central role in the study of quantum computation. However, their computational power is limited: a well-known result of Gottesman and Knill states that Clifford circuits are efficiently classically simulable. We show that in contrast, "conjugated Clifford circuits" (CCCs) - where one additionally conjugates every qubit by the same one-qubit gate U - can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary U can give rise to sampling tasks which cannot be efficiently classically simulated to constant multiplicative error, unless the polynomial hierarchy collapses. Furthermore, by standard techniques, this hardness result can be extended to allow for the more realistic model of constant additive error, under a plausible complexity-theoretic conjecture. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets.

BibTeX - Entry

@InProceedings{bouland_et_al:LIPIcs:2018:8867,
  author =	{Adam Bouland and Joseph F. Fitzsimons and Dax Enshan Koh},
  title =	{{Complexity Classification of Conjugated Clifford Circuits}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{21:1--21:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8867},
  URN =		{urn:nbn:de:0030-drops-88677},
  doi =		{10.4230/LIPIcs.CCC.2018.21},
  annote =	{Keywords: gate set classification, quantum advantage, sampling problems, polynomial hierarchy}
}

Keywords: gate set classification, quantum advantage, sampling problems, polynomial hierarchy
Collection: 33rd Computational Complexity Conference (CCC 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI