built-in function, with the first n qubits as input, returns a 1. The function-controlled NOT gate is an essential element of the Deutsch–Jozsa algorithm. Behaviour in the Hadamard transformed basis When viewed only in the computational basis , the behaviour of the CNOT appears to be like the equivalent classical gate. However, the simplicity of labelling one qubit the control and the other the target does not reflect the complexity of what happens for most input values of both qubits. Insight can be won by expressing the CNOT gate with respect to a Hadamard transformed basis . The Hadamard transformed basis of a one-qubit register is given by and the corresponding basis of a 2-qubit register is , etc. Viewing CNOT in this basis, the state of the second qubit remains unchanged, and the state of the first qubit is flipped, according to the state of the second bit. (For details see below.) "Thus, in this basis the sense of which bit is the control bit and which the target bit has reversed. But we have not changed the transformation at all, only the way we are thinking about it." The "computational" basis is the eigenbasis for the spin in the Z-direction, whereas the Hadamard basis is the eigenbasis for spin in the X-direction. Switching X and Z and qubits 1 and 2, then, recovers the original transformation." This expresses a fundamental symmetry of the CNOT gate. The observation that both qubits are (equally) affected in a CNOT interaction is of importance when considering information flow in entangled quantum systems. Details of the computation We now proceed to give the details of the computation. Working through each of the Hadamard basis states, the first qubit flips between and when the second qubit is : A quantum circuit that performs a Hadamard transform followed by CNOT then another Hadamard transform, can be described as performing the CNOT gate in the Hadamard basis (i.e. a change of basis): The single-qubit Hadamard transform, H1, is Hermitian and therefore its own inverse. The tensor product of two Hadamard transforms operating (independently) on two qubits is labelled H2. We can therefore write the matrices as: When multiplied out, this yields a matrix that swaps the and terms over, while leaving the and terms alone. This is equivalent to a CNOT gate where qubit 2 is the control qubit and qubit 1 is the target qubit: