How to Locate Untanglement | Quantum Colloquium

A classical problem in quantum information is that of detecting unentanglement, in which one is given a bipartite quantum state and asked to determine if it is (i) a product state or (ii) an entangled state; it is well-known that this task can be solved with the SWAP test. In this talk, we consider the related problem of locating unentanglement, in which two unentangled n-qubit states are scrambled up to produce a 2n-qubit state, and the goal is to locate the n qubits belonging to each state. There is a simple information theoretic algorithm for solving this problem based on the quantum union bound, but this algorithm runs in exponential time and is therefore inefficient. Our main result is an efficient, polynomial-time algorithm for this problem, which is inspired by the hidden subgroup problem. 

This is joint work with Adam Bouland and Tudor Giurgică-Tiron.