Nonlocal Properties of Two-Qubit Gates and Mixed States, and the Optimization of Quantum Computations

Entanglement of two parts of a quantum system is a nonlocal property unaffected by local manipulations of these parts. It can be described by quantities invariant under local unitary transformations. Here we present, for a system of two qubits, a set of invariants which provides a complete description of nonlocal properties. The set contains 18 real polynomials of the entries of the density matrix. We prove that one of two mixed states can be transformed into the other by single-qubit operations if and only if these states have equal values of all 18 invariants. Corresponding local operations can be found efficiently. Without any of these 18 invariants the set is incomplete. Similarly, nonlocal, entangling properties of two-qubit unitary gates are invariant under single-qubit operations. We present a complete set of 3 real polynomial invariants of unitary gates. Our results are useful for optimization of quantum computations since they provide an effective tool to verify if and how a given two-qubit operation can be performed using exactly one elementary two-qubit gate, implemented by a basic physical manipulation (and arbitrarily many single-qubit gates).