irljf

I strongly disagree. The IC and PCB analogy is not accurate. The equivalent would be saying that computer scientists should not need to learn about ion traps and SQUIDs, and I would agree with that. Quantum algorithms, on the other hand, are just algorithms, albeit ones in which you are allowed an extra operation. While now may or may not be the time to introduce this into CS courses, quantum information processing will only become more important over time, rather than less. The argument about them never superseding classical computers isn't something that there is any real support for, except that it is hard to build QCs at the moment. The same could have been said for classical computers not that long ago. It's not clear from your answer whether you know this or not, but quantum computers can perform classical computation. So, this is like in the 40s saying that there would always be a roll for human computers or mechanical computers, while now we would think that was a ridiculous position given at how good we have gotten at making ICs.

But this is like arguing that computer scientists shouldn't take algorithms courses. Actually, it's not just like it, it -is- arguing that they shouldn't bother learning to understand certain types of algorithms. Without that knowledge, how do you possibly know how to get an advantage from the co-processor beyond blind luck or hoping the API implements exactly the functionality you want?

Yes. Grover's algorithm searches a disordered database in time sublinear in the number of elements, and provides a quadratic speedup over any possible classical algorithm. There are similar results for finding collisions etc. There is no proof, however, that quantum computers offer an exponential advantage on decision problems without some additional assumption, although this is widely believed to be the case, due in part to the exponential improvement of Shor's factoring algorithm compared to the best -known- classical algorithms.

Yes, this is true for any unitary operation on a different subsystem, and is known as the no-signalling principle. But this doesn't let you remove the second system: you are still stuck with a mixed state on the first system, not a pure state (in your case the state is 1/2 |0><0| + 1/2 |1><1|).

I agree, but not all bugs are subtle. This seems to be the equivalent to someone having trouble with "hello world" because they forgot to include iostream.

infparadox: This isn't about credentials, but da-bacon is the "Bacon" in Bacon-Shor codes.

I think you are misunderstanding the situation or the math. You say "For example, consider a two subsystems entangled with each other, |q1>|q2>." But this system is -not- entangled, it is a separable state by definition, since you wrote it as a tensor product. For the state to be entangled, it needs to be a sum over separable states: sum_i a_i |x_i>|y_i>, with 0<=a_i<1. In this case, you cannot simply factor the state because of the summation. The second system is not in a pure state individually, nor is the first, it is only the joint state of the system which is pure. The reduced state for a single subsystem cannot be pure if it is entangled to other subsystems (due to the need for the summation in order for the state to be entangled: if you can remove the summation, as in the case where [x_0 = 0, x_1 = 1, y_0 = 0, y_1 = 0] then there is no entanglement).

Now, in the case of a separable state |q1>|q2>, you can indeed just consider the state of each subsystem individually as |q1> and |q2>, so you are correct in this regard. However, entangled states are not of this form, and cannot be treated in this way. It's an elementary mistake that many beginners make.

Yes, Eq. 16 certainly does not follow from 15. They should have a mixed state of the system. You should recognize this, since it's the graph isomorphism approach everyone tries.

infparadox: It's a subsystem, not a subspace. When you discard a subsystem which is entangled (as they specifically say it is) the result cannot be a pure state, and you need to express it in the dentist matrix formalism by taking the partial trace over the discarded system. What they wrote is not correct.