Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
This question is two-fold and considers general $n$-qubit operations on a quantum computer.
First, can a general $n$-qubit operation be implemented on a quantum computer without the use of ancilla qubits?
Second, can ancilla qubits help in reducing the depth of such general $n$-qubit operations and if yes, what is the relation between the two?
I'll assume you're interested in unitary, n-qubit operations. Then yes, any universal gate-set can approximate any given unitary, even though some unitaries may require an exponential number of gates for this. The Solovay-Kitaev theorem gives a constructive proof, so it gives a concrete algorithm to find a sequence of operations from the universal gate-set that approximates any given unitary to an arbitrary distance. (There are some technical requirements, such as the need for the inverse of all gates in the gate-set.)
If you're interested in exactly obtaining the unitary, then not all gate-sets are equivalent. This is the realm of quantum circuit synthesis. In this case, as in the approximate case, sometimes auxiliary qubits can decrease the gate-count or the depth of the resulting circuit. As an example, check these exact decompositions of Toffoli gates, with and without auxiliary qubits: https://arxiv.org/abs/0803.2316
