Cite this problem as Problem 16.
What can be said about the algorithmic complexity of preparing , asymptotically, as a function of and the algorithmic complexity of preparing ? Take to be a state of qubits. By algorithmic complexity I mean the number of gates required to prepare the state from . This depends on the gate set used so the question concerns asymptotics. For the present purposes, one can take as a gate set all roations where is a product of Pauli matrices. The complexity of this gate is . It might be useful to consider a version of this question involving an approximation parameter also.
It may be possible to clone more efficiently than to prepare it, given that one knows .