  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.
