Complexity of product preparations

From OpenQIProblemsWiki
Jump to: navigation, search

Cite as: http://qig.itp.uni-hannover.de/qiproblems/16

Previous problem: Separability from spectrum

Next problem: Reversibility of entanglement assisted coding

Problem

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

Background

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

Literature

Literature on optimal cloning is relevant