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?
It's more like arguing that computer scientists shouldn't have to learn how ICs are fabricated and how PCBs are designed. They can learn if they want, but they shouldn't have to.
Quantum algorithms are so vastly different in nature from classical algorithms that it will necessarily be its own branch of science. It takes an entirely different mode of thinking; for example, basic physics laws forbid you from copying a qubit that is in an arbitrary quantum state. That's right, you cannot copy a quantum variable as that would violate fundamental laws of the universe as we know it. Most computer scientists are not used to that kind of thinking. However traditional computer science thinking will not vanish, because quantum computers will never be a replacement for classical computers; they are good at speeding up very specific classes of computations and not particularly suited for general computing or building interfaces with the outside world.
Quantum computer science and classical computer science will be two fields of study that will both continue to evolve in their own right.
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.
I'm not an expert on quantum programmig but the impression I kind of got is that you don't just go around writing quantum programs like you would for a classical computers. Instead, you have very particular problems where very particular quantum algorithms are more efficient than the classical ones.
If I had to bet I would guess that quantum programming is going to be more like "linear programming", where instead of programming the algorithm instructions you program by preparing the inputs that you will pass to the specialized subsystem.
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.
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.
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.
I am not expert in the field, I just took a course, but I know that a mixed state is not the same as an entangled state. In their case it is entangled not mixed and so there is no need to take the partial trace. For example, consider a two subsystems entangled with each other, |q1>|q2>. I we want to apply an operator U on the second subsytem we apply I(x)U or we can simply consider the second subsystem and apply U|q2>. This is valid as long as the entanglement holds and Identity gates are assumed to be applied on the first subsystem.
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.
I think I made a misunderstanding by the |q1>|q2> notation. Consider the entangled 2-qubits system a|00>+b|11>. The prob of the 2nd qubit is |0> is |a|^2 and the prob of 2nd qubit is |1> is |b|^2. Now apply I(x)NOT, then the system is a|01>+b|10>. The prob of 2nd qubit to be |0> is now |b|^2 and prob of 2nd qubit is |1> is |a|^2. The same can be obtained by considering the 2nd qubit only as a|0>+b|1> and apply NOT only on the second qubit, without making any operation on the first qubit and without breaking the entanglement.
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|).
Well, I still don't see any thing wrong with the math. Even the authors rewrite the equations as sum(|A_k>|C_k>) instead of sum(|C_k>) and apply I(x)M_x instead of applying only M_x on |C_k> alone, this will not change the following equations.
