Transforming a classical Boolean circuit to a quantum circuit. The three-bit majority function M3:{0,1}3{0,1} is defined for all x2,x1,x0{0,1} by M3(x2,x1,x0)={10ifx2+x1+x02ifx2+x1+x01 (a) Prepare a complete table of values the function M3. (b) Design a Boolean circuit that computes M3. More precisely, work with a bit register that you can assume initially contains the bits x2,x1,x0 in its three most significant bits, and all the other bits are set to zero. Present a sequence of gates (,,,) such that the value M3(x2,x1,x0) is stored in one of the bits of the final state. (c) Using reversible gates (NOT, CNOT, CCNOT), design a reversible Boolean circuit that computes M3. (d) Using at-most-three-qubit quantum gates, design a quantum circuit that computes M3. More precisely, design a q-qubit quantum circuit that represents a unitary matrix UM3C2q2q such that for all x2,x1,x0{0,1} we have UM3x2,x1,x0,0,0,,0=x2,x1,x0,M3(x2,x1,x0),W(x2,x1,x0) for some function W:{0,1}3{0,1}q4 with q4. Hints: It may be a good idea to use as few gates as possible in (b) to ease your work in what follows. The table you prepared in (a) may help you with this. For (c), introduce one new work bit to the register for each gate in (b), then use one or more reversible gates to simulate each gate in (b). For (d), you may want to use (c) and work with the gates X (the Pauli-X gate), CX, and CCX