In an earlier Article[1], Knill, Laflamme, and Milburn showed that non-deterministic quantum logic operations could be performed using linear optical elements, additional photons (ancilla), and post-selection based on the output of single-photon detectors. These devices succeed in producing the desired logical output with a probability that can approach unity and they may form the basis for a scalable approach to quantum computing. Here we report the experimental demonstration of two logic devices of this kind, a quantum parity check and a destructive controlled-NOT (CNOT) gate[2]. These devices have a very simple structure and they are relatively insensitive to errors due to phase drifts. The quantum parity check and destructive CNOT gates demonstrated here could be combined with a pair of entangled photons to implement a conventional (non-destructive) CNOT gate, the basic building-block for a quantum computer, that succeeds with a probability of 1/4.