3 ms·

So you can make a grid with less than 40 quantum atom pairs, each of which is coupled in some way to another atom, and since measuring one atom guarantees the o

So you can make a grid with less than 40 quantum atom pairs, each of which is coupled in some way to another atom, and since measuring one atom guarantees the other atom is in the opposite state, you can bypass Heisenberg uncertainty. But wait. To solve an NP problem of size n, you need square(n) atoms. But 40 atoms is barely more than 36, so you can solve a NP problem of size 6, which is easy and possible. I think brute force on an NP problem is factorial(n) So factorial(6) == 6 ! == 6 * 5 * 4 * 3 * 2 * 1 == 720. Am I misunderstanding something here ?

karmakaze 4y ago
The other atom is not in the 'opposite state' for all properties, rather it has one property which is entangled so whatever accuracy you just measured, you know to the same accuracy of the other in the entangled property only. Also 40 bits in superposition can represent 2^40 possibilities.
- aaplok 4y ago
  > 40 bits in superposition can represent 2^40 possibilities. In classical QC yes, is this the case any longer in the Rydberg blockade configuration? From what I understood from the article, it's what GP said: the atom configuration implements the independent set problem using entanglement. So the number of qubits is the order of the graph, which is the size of the problem. I'm not sure where the quadratic bound is derived from, and I didn't understand where the solution to the maximum independent set comes from so maybe I didn't understand the article... There are so many other gray areas in the article that reading it feels a bit like riding on the hype train.
petters 4y ago
> I think brute force on an NP problem is factorial(n) No, NP ⊆ EXPTIME, which means that exponential time should be enough.