operator. The probabilities for the other POVM operators are computed similarly.

The implementation of a POVM with corresponding matrix $M$ is obtained by the orthogonal measurement in the computational basis after performing the unitary transformation ${\tilde M}^\dagger$ on the system with initial state ${\tilde \rho}$. This unitary operation maps the vector ${| {\tilde \Psi}_j\rangle} = {|\Psi_j\rangle} \oplus
{|\Phi_j\rangle}$ to the computational basis vector ${|j\rangle}$. Therefore, the measurement in the computational basis after applying ${\tilde M}^\dagger$ corresponds to the measurement in the basis defined by the vectors ${|{\tilde \Psi}_j\rangle}$.

In summary, we are interested in constructing and implementing the matrix ${\tilde M}^\dagger$ for a given POVM corresponding to the matrix $M$. In the following sections the construction of the matrices ${\tilde M}^\dagger$ is considered for symmetric POVMs besides the decomposition of ${\tilde M}^\dagger$ into elementary (one- and two-qubit) gates. The symmetry leads to simple constructions and implementations based on Fourier transforms.

Symmetric POVMs on a single qubit {#Section 2}
=================================

As described in the previous section, the basis of the orthogonal measurement of a POVM with corresponding matrix $M$ is the implementation of ${\tilde M}^\dagger$. ${\tilde M}$ is a unitary extension of $M$. We can apply the algorithm in Section 4.5.1 