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.STACS.2018.57
URN: urn:nbn:de:0030-drops-84907
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8490/
Go to the corresponding LIPIcs Volume Portal


Takahashi, Yasuhiro ; Tani, Seiichiro

Power of Uninitialized Qubits in Shallow Quantum Circuits

pdf-format:
LIPIcs-STACS-2018-57.pdf (0.6 MB)


Abstract

We study the computational power of shallow quantum circuits with O(log n) initialized and n^{O(1)} uninitialized ancillary qubits, where n is the input length and the initial state of the uninitialized ancillary qubits is arbitrary. First, we show that such a circuit can compute any symmetric function on n bits that is classically computable in polynomial time. Then, we regard such a circuit as an oracle and show that a polynomial-time classical algorithm with the oracle can estimate the elements of any unitary matrix corresponding to a constant-depth quantum circuit on n qubits. Since it seems unlikely that these tasks can be done with only O(log n) initialized ancillary qubits, our results give evidences that adding uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O(log n) initialized ancillary qubits. Lastly, to understand the limitations of uninitialized ancillary qubits, we focus on near-logarithmic-depth quantum circuits with them and show the impossibility of computing the parity function on n bits.

BibTeX - Entry

@InProceedings{takahashi_et_al:LIPIcs:2018:8490,
  author =	{Yasuhiro Takahashi and Seiichiro Tani},
  title =	{{Power of Uninitialized Qubits in Shallow Quantum Circuits}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{57:1--57:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8490},
  URN =		{urn:nbn:de:0030-drops-84907},
  doi =		{10.4230/LIPIcs.STACS.2018.57},
  annote =	{Keywords: quantum circuit complexity, shallow quantum circuit, uninitialized qubit}
}

Keywords: quantum circuit complexity, shallow quantum circuit, uninitialized qubit
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018


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