It has previously been shown that probabilistic quantum logic operations can be performed using linear optical elements, additional photons (ancilla), and post-selection based on the output of single-photon detectors. Here we describe the operation of several new quantum logic operations of an elementary nature, including a quantum parity check and a quantum encoder, and we show how they can be combined to implement a controlled-NOT (CNOT) gate. All of these gates can be constructed using polarizing beam splitters that completely transmit one state of polarization and totally reflect the orthogonal state of polarization, which allows a simple explanation of each operation. We also describe a polarizing beam splitter implementation of a CNOT gate that is closely analogous to the quantum teleportation technique previously suggested by Gottesman and Chuang [Nature 402, p.390 (1999)]. Finally, our approach has the interesting feature that it makes practical use of a quantum-eraser technique.