  It is not a problem to complement a classical bit, i.e. to change the value
of a bit, a 0 to a 1 and vice versa. This is accomplished by a NOT gate.
Complementing a qubit in an unknown state, however, is another matter. We show
that this operation cannot be done perfectly. We define the Universal-NOT
(U-NOT) gate which out of N identically prepared pure input qubits generates M
output qubits in a state which is as close as possible to the perfect
complement. This gate can be realized by classical estimation and subsequent
re-preparation of complements of the estimated state. Its fidelity is therefore
equal to the fidelity F= (N+1)/(N+2) of optimal estimation, and does not depend
on the required number of outputs. We also show that when some additional a
priori information about the state of input qubit is available, than the
fidelity of the quantum NOT gate can be much better than the fidelity of
estimation.
