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?

Example Problem

  1. $|\psi_0\rangle$ was drawn uniformly at random from the space of 2-qubit (i.e. 4-level) pure states.

  2. $|\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$.

  3. $|\psi_1\rangle$ was measured along $Z \otimes Z$ and the result was +1, producing $|\psi_2\rangle$.

  4. 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?

  • 2
    $\begingroup$ Still trying to get around the no-cloning theorem? :-) $\endgroup$ – CuriousOne Apr 8 '16 at 19:26
  • $\begingroup$ @CuriousOne More like exploring the boundaries around it. Violate some of the assumptions, see how the conclusion varies. $\endgroup$ – Craig Gidney Apr 8 '16 at 19:32
  • $\begingroup$ If you are willing to violate the laws of nature, then everything is possible. Take for instance the third law of thermodynamics... get yourself a negative temperature bath... voila... instant perpetual motion machine! :-) $\endgroup$ – CuriousOne Apr 8 '16 at 19:43
  • 1
    $\begingroup$ What are you violating? Sounds like a perfectly reasonable protocol (if I interpret it correctly -- but admittedly I find it hard to follow what you are actually asking: It might help if you would be more concise). $\endgroup$ – Norbert Schuch Apr 8 '16 at 19:55
  • $\begingroup$ @NorbertSchuch In this case the precondition being violated is "no information about the state". It won't always allow ideal cloning, but the approximation will get better. I was very un-concise and explicit because of how much flak I got from CuriousOne when I asked a similar question yesterday. $\endgroup$ – Craig Gidney Apr 8 '16 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.