Quantum parallelism of the controlled-NOT operation: an experimental criterion for the evaluation of device performance

It is shown that a quantum controlled-NOT gate simultaneously performs the logical functions of three distinct conditional local operations. Each of these local operations can be verified by measuring a corresponding truth table of four local inputs and four local outputs. The quantum parallelism of the gate can then be observed directly in a set of three simple experimental tests, each of which has a clear intuitive interpretation in terms of classical logical operations. Specifically, quantum parallelism is achieved if the average fidelity of the three classical operations exceeds 2/3. It is thus possible to evaluate the essential quantum parallelism of an experimental controlled-NOT gate by testing only three characteristic classical operations performed by the gate.