Is there any known result regarding the hardness of the following problem:
Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that implements the same unitary.
I'm assuming that the ancilla qubits are supplied in computational basis states. It might be that the result is different depending on whether the ancilla bits are required to be left clean. I seem to recall a result stating that the verification of an ancilla qubit being left clean is a hard problem, but I don't know the specifics.
A related problem would be to require the circuits to be reversible classical circuits. I don't think this problem is strictly a subset however, as the unitary without ancillae could take 'shortcuts' using quantum operations not available in classical reversible circuits.