# Complexity of product preparations

Previous problem: Separability from spectrum

Next problem: Reversibility of entanglement assisted coding

# 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$.

# Literature

 Literature on optimal cloning is relevant