Complexity of product preparations – Open Quantum Problems

Cite this problem as Problem 16.

Problem

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.

Background

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