  Reversible algorithms play a crucial role both in classical and quantum
computation. While for a classical bit the only nontrivial reversible operation
is the bit-flip, nature is far more versatile in what it allows to do to a
quantum bit. The reversible operations that a quantum computer can perform on a
qubit are group of linear unitary transformations. However, laws of quantum
mechanics prohibit implementation of anti-linear anti-unitary gates, even
though they are perfectly reversible. Here we show that such a restriction on
possible set of reversible operations is, remarkably, a fundamental constraint
of spacetime structure. In particular, it will be shown that construction of
any anti-linear anti-unitary gate will lead to violation of a fundamental
causal primitive which, as we shall argue, is fundamentally different from the
principle of relativistic causality.
