and the Pauli-Z gate where . The phase shift gates are related to each other as follows: Note that the phase gate is not Hermitian (except for all ). These gates are different from their Hermitian conjugates: . The two adjoint (or conjugate transpose) gates and are sometimes included in instruction sets. Hadamard gate The Hadamard or Walsh-Hadamard gate, named after Jacques Hadamard () and Joseph L. Walsh, acts on a single qubit. It maps the basis states and (it creates an equal superposition state if given a computational basis state). The two states and are sometimes written and respectively. The Hadamard gate performs a rotation of about the axis at the Bloch sphere, and is therefore involutory. It is represented by the Hadamard matrix: If the Hermitian (so ) Hadamard gate is used to perform a change of basis, it flips and . For example, and Swap gate The swap gate swaps two qubits. With respect to the basis , , , , it is represented by the matrix: The swap gate can be decomposed into summation form: Toffoli (CCNOT) gate The Toffoli gate, named after Tommaso Toffoli and also called the CCNOT gate or Deutsch gate , is a 3-bit gate which is universal for classical computation but not for quantum computation. The quantum Toffoli gate is the same gate, defined for 3 qubits. If we limit ourselves to only accepting input qubits that are and then if the first two bits are in the state it applies a Pauli-X (or NOT) on the third bit, else it does nothing. It is an example of a CC-U (controlled-controlled Unitary) gate. Since it is the quantum analog of a classical gate, it is completely specified by its truth table. The Toffoli gate is universal when combined with the single qubit Hadamard gate. The Toffoli gate is related to the classical AND () and XOR () operations as it performs the mapping on states in the computational basis. The Toffoli gate can be expressed using Pauli matrices as Universal quantum gates A set of universal quantum gates is any set of gates to which any operation possible on a quantum computer can be reduced, that is, any other unitary operation can be expressed as a finite sequence of gates from the set. Technically, this is impossible with anything less than an uncountable set of gates since the number of possible