Hacker News Reader

Comment by da-bacon | Hacker News Reader

Eq. 16.

As a grad student in quantum computing we used to have a game where we would race to see who could be the first one to spot the flaw in a paper that claimed an efficient quantum polynomial time algorithm for NP-complete problems.

My bet after a few minutes looking at the paper is Eq. 16. Eq. 15 is computing the clauses with a traditional clause oracle \sum_x |x>|C(x)> where C(x) is a vector of the clauses evaluated on the input x. Eq. 16 claims that one can ignore the first register and this becomes \sum_x |C(x)>. That's not correct: the system is entangled across those two registers, and the partial portion of one of those systems is a mixed state. In particular there is no coherence between the |C(x)> states. The next step relies crucially on this property.

View on HN

My guess is that the problem lies in the M_x operator, which is similar to the Grover rotation operator but supposedly only acts on the control qubits and another control-control qubit (see my other comment here). Would love to get your opinion on that!

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.

I don't think there is a problem in that, they are just considering a subspace of the system.

Reply on news.ycombinator.com