Computational Complexity in Entanglement Transformations.
[摘要] In physics, systems having three parts are typically much more difficult to analyze than those having just two.Even in classical mechanics, predicting the motion of three interacting celestial bodies remains an insurmountable challenge while the analogous two-body problem has an elementary solution.It is as if just by adding a third party, a fundamental change occurs in the structure of the problem that renders it unsolvable.In this thesis, we demonstrate how such an effect is likewise present in the theory of quantum entanglement. In fact, the complexity differences between two-party and three-party entanglement become quite conspicuous when comparing the difficulty in deciding what state changes are possible for these systems when no additional entanglement is consumed in the transformation process.We examine this entanglement transformation question and its variants in the language of computational complexity theory, a powerful subject that formalizes the concept of problem difficulty. Since deciding feasibility of a specified bipartite transformation is relatively easy, this task belongs to the complexity class P.On the other hand, for tripartite systems, we find the problem to be NP-Hard, meaning that its solution is at least as hard as the solution to some of the most difficult problems humans have encountered.One can then rigorously defend the assertion that a fundamental complexity difference exists between bipartite and tripartite entanglement since unlike the former, the full range of forms realizable by the latter is incalculable (assuming P unequal to NP).However, similar to the three-body celestial problem, when one examines a special subclass of the problem - invertible transformations on systems having at least one qubit subsystem - we prove that the problem can be solved efficiently.As a hybrid of the two questions, we find that the question of tripartite to bipartite transformations can be solved by an efficient randomized algorithm.Our results are obtained by encoding well-studied computational problems such as polynomial identity testing and tensor rank into questions of entanglement transformation.In this way, entanglement theory provides a physical manifestation of some of the most puzzling and abstract classical computation questions.
[发布日期] [发布机构] University of Michigan
[效力级别] Computational Complexity [学科分类]
[关键词] Entanglement Theory;Computational Complexity;Quantum Information;Physics;Science;Physics [时效性]