Suppose I give you a state $|\psi\rangle$, and tell you a sequence of measurements that have been performed on it. The measurements are not guaranteed to be orthogonal to each other, or to cover the entire state-space.
Your goal is to produce an approximate clone of $|\psi\rangle$. Something that will be difficult to distinguish from the original $|\psi\rangle$. The measurement results provide valuable information for beating the fidelity of the optimal uninformed cloning method.
How easy is this to do, supposing we have access to a quantum computer?
$|\psi_0\rangle$ was drawn uniformly at random from the space of 2-qubit (i.e. 4-level) pure states.
$|\psi_0\rangle$ was measured along the first qubit's diagonal X+Z axis and the result was -1. The measurement perturbed $|\psi_0\rangle$, giving $|\psi_1\rangle$.
$|\psi_1\rangle$ was measured along $Z \otimes Z$ and the result was +1, producing $|\psi_2\rangle$.
We want to approximately clone $|\psi_2\rangle$.
Naive Classical Solution
Classically, we could simulate hitting a maximally-mixed density matrix $\rho$ with a post-selection for each measurement (in order). We then produce the described $\rho$ with a quantum computer. Finally, when performing the optimal uninformed cloning method on a quantum computer, we concatenate $\rho$ onto $|\psi\rangle$ before projecting onto their symmetric subspace (normally we'd have used a maximally-mixed state instead of $\rho$).
The problem with this solution is that we have to operate on a huge density matrix classically. For an $n$-qubit system and a list of $m$ measurements, it takes $O(m 4^n)$ time.
Naive Quantum Solution
We can avoid the $4^n$ cost of the classical solution by performing the measurements and post-selections with a quantum computer initialized with a random state. However, since we don't live a Post-BQP universe, the post-selection procedure is actually just measuring, hoping the answer comes out right, and starting over if it didn't.
Optimistically assuming each measurement is 50/50, we get a lower bound of $\Omega(2^m)$ on the worst-case time.
(If the measurements were guaranteed to be orthogonal, and had to be described in terms of a quantum circuit to perform the necessary basis transformation, we could just use them as a description of how to initialize a subset of $|\psi\rangle$ and be done in polynomial time. The overlap is what causes so much trouble.)
How efficiently can optimal measurement-informed approximate cloning be performed? Is there a solution that's polynomially expensive in terms of both the number of qubits and the number of measurements?