Takahashi, Yasuhiro ;
Tani, Seiichiro
Power of Uninitialized Qubits in Shallow Quantum Circuits
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
polynomialtime classical algorithm with the oracle can estimate
the elements of any unitary matrix corresponding to a
constantdepth 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
nearlogarithmicdepth 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:157:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8490},
URN = {urn:nbn:de:0030drops84907},
doi = {10.4230/LIPIcs.STACS.2018.57},
annote = {Keywords: quantum circuit complexity, shallow quantum circuit, uninitialized qubit}
}
27.02.2018
Keywords: 

quantum circuit complexity, shallow quantum circuit, uninitialized qubit 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 