Back to search

University of Waterloo

On the Hardness of the Quantum Separability Problem and the Global Power of Locally Invariant Unitary Operations

Abstract

dc:description.abstract

Given a bipartite density matrix ρ of a quantum state, the Quantum Separability problem (QUSEP) asks — is ρ entangled, or separable? In this thesis, we first strengthen Gurvits’ 2003 NP-hardness result for QUSEP by showing that the Weak Membership problem over the set of separable bipartite quantum states is strongly NP-hard, meaning it is NP-hard even when the error margin is as large as inverse polynomial in the dimension, i.e. is “moderately large”. Previously, this NP-hardness was known only to hold in the case of inverse exponential error. We observe the immediate implication of NP-hardness of the Weak Membership problem over the set of entanglement-breaking maps, as well as lower bounds on the maximum (Euclidean) distance possible between a bound entangled state and the separable set of quantum states (assuming P ≠ NP). We next investigate the entanglement-detecting capabilities of locally invariant unitary operations, as proposed by Fu in 2006. Denoting the subsystems of ρ as A and B, such that ρ_B = Tr_A(ρ), a locally invariant unitary operation U^B is one with the property U^B ρ_B (U^B)^† = ρ_B. We investigate the maximum shift (in Euclidean distance) inducible in ρ by applying I⊗U^B, over all locally invariant choices of U^B. We derive closed formulae for this quantity for three cases of interest: (pseudo)pure quantum states of arbitrary dimension, Werner states of arbitrary dimension, and two-qubit states. Surprisingly, similar to recent anomalies detected for non-locality measures, the first of these formulae demonstrates the existence of non-maximally entangled states attaining shifts as large as maximally entangled ones. Using the latter of these formulae, we demonstrate for certain classes of two-qubit states an equivalence between the Fu criterion and the CHSH inequality. Among other results, we investigate the ability of locally invariant unitary operations to detect bound entanglement.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gharibian, Sevag

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/3991

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gharibian, Sevag. On the Hardness of the Quantum Separability Problem and the Global Power of Locally Invariant Unitary Operations. University of Waterloo, 2008. http://hdl.handle.net/10012/3991