Read on Twitter
1/n - Here's a thread about NP-Hardness, Soap Bubbles & Entanglement!
---------------------------------------------------------------------------------------
This past week I've been thinking about the physical reality of NP-Hardness and what that has to say about entanglement.
---------------------------------------------------------------------------------------
This past week I've been thinking about the physical reality of NP-Hardness and what that has to say about entanglement.
2/n - When a problem is NP, that means that given a solution it would take a classical computer polynomial time to check if its correct. An NP-Hard problem is one which is worse. It's one which might not have a solution, or one which might take more than polynomial time to verify
3/n - For a set of points, finding their accompanying Steiner Tree is NP-Hard.
That is, finding the collection of line
segments of minimum total length connecting the points, where the lines can meet at vertices
(called Steiner vertices) other than the points themselves.
That is, finding the collection of line
segments of minimum total length connecting the points, where the lines can meet at vertices
(called Steiner vertices) other than the points themselves.
4/n - Despite its NP-Hardness, Soap Bubbles naturally solve the Steiner Tree problem. At least for small N.
This is an interesting thought because it might lead one to think that nature is just better at things than computers. Maybe even that P=NP...
Image - Dutta et al
This is an interesting thought because it might lead one to think that nature is just better at things than computers. Maybe even that P=NP...
Image - Dutta et al
5/n - Scott Aaronson takes this to task in his paper "NP-complete Problems and Physical Reality" where he himself struggles to create a soapy Steiner Tree for 7 vertices.
The implication perhaps being that nature itself respects NP-Hardness!
The implication perhaps being that nature itself respects NP-Hardness!
6/n - In Quantum Mechanics, entangled states are those that cannot be reduced to a tensor product state of states which lie in the constituent Hilbert spaces. They're states which cannot be separated. They're a kind of purple that can't be reduced to red and blue.
7/n - Well it turns out that figuring out whether a state is entangled or not is NP-Hard!
This is truly shocking to me, especially since so much work has gone into coming up with different kinds of entanglement measures.
This is truly shocking to me, especially since so much work has gone into coming up with different kinds of entanglement measures.
8/n - Extending our soapy thought exercise to entanglement's NP-Hardness, what does this say for emerging fields where quantifying entanglement is going to be crucial?
Like Quantum Gravity. Or the thermodynamics of Quantum Computation where I've been spending my time recently.
Like Quantum Gravity. Or the thermodynamics of Quantum Computation where I've been spending my time recently.
9/n - Scott gets into some of this in his paper.
An important point is that whilst seperability is NP-Hard not much is known about the complexity of finding some Entanglement Measures like negativity. So maybe there is hope yet....
An important point is that whilst seperability is NP-Hard not much is known about the complexity of finding some Entanglement Measures like negativity. So maybe there is hope yet....
10/10 - What do you think about the NP-Hardness of Quantum Entanglement?
Could it have some physical meaning?
Let me know!
Could it have some physical meaning?
Let me know!
* I am by no means someone who is well read on computational complexity so it's completely possible that I misrepresented an idea. *
Please feel free to clarify something or correct me :)
Please feel free to clarify something or correct me :)
