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.TQC.2018.8
URN: urn:nbn:de:0030-drops-92551
Go to the corresponding LIPIcs Volume Portal

van Dam, Wim ; Wong, Raymond

Two-qubit Stabilizer Circuits with Recovery II: Analysis

LIPIcs-TQC-2018-8.pdf (0.7 MB)


We study stabilizer circuits that use non-stabilizer qubits and Z-measurements to produce other non-stabilizer qubits. These productions are successful when the correct measurement outcome occurs, but when the opposite outcome is observed, the non-stabilizer input qubit is potentially destroyed. In preceding work [arXiv:1803.06081 (2018)] we introduced protocols able to recreate the expensive non-stabilizer input qubit when the two-qubit stabilizer circuit has an unsuccessful measurement outcome. Such protocols potentially allow a deep computation to recover from such failed measurements without the need to repeat the whole prior computation. Possible complications arise when the recovery protocol itself suffers from a failed measurement. To deal with this, we need to use nested recovery protocols. Here we give a precise analysis of the potential advantage of such recovery protocols as we examine its optimal nesting depth. We show that if the expensive input qubit has cost d, then typically a depth O(log d) recovery protocol is optimal, while a certain special case has optimal depth O(sqrt{d}). We also show that the recovery protocol can achieve a cost reduction by a factor of at most two over circuits that do not use recovery.

BibTeX - Entry

  author =	{Wim van Dam and Raymond Wong},
  title =	{{Two-qubit Stabilizer Circuits with Recovery II: Analysis}},
  booktitle =	{13th Conference on the Theory of Quantum Computation,  Communication and Cryptography (TQC 2018)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-080-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{111},
  editor =	{Stacey Jeffery},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-92551},
  doi =		{10.4230/LIPIcs.TQC.2018.8},
  annote =	{Keywords: stabilizer circuit, recovery circuit, magic state}

Keywords: stabilizer circuit, recovery circuit, magic state
Collection: 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)
Issue Date: 2018
Date of publication: 16.07.2018

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