Complexity of product preparations

Cite this problem as Problem 16.


What can be said about the algorithmic complexity of preparing \vert \psi \rangle \vert\psi\rangle ... (n\text{ times}), asymptotically, as a function of \textstyle n and the algorithmic complexity of preparing \vert \psi \rangle ? Take \vert \psi \rangle to be a state of \textstyle m qubits. By algorithmic complexity I mean the number of gates required to prepare the state from \vert 0 \rangle . 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 \textstyle \text{exp}(i \phi \sigma_u) where \textstyle \sigma_u is a product of Pauli matrices. The complexity of this gate is \vert\phi\vert. It might be useful to consider a version of this question involving an approximation parameter also.


It may be possible to clone \vert \psi \rangle more efficiently than to prepare it, given that one knows \vert \psi \rangle.