A method for detecting a two-qubit correlated dephasing error includes accessing a signal of a quantum system, where the quantum system includes a plurality of qubits. Every qubit has a nonzero rate of dephasing and some qubits have a nonzero rate of correlated dephasing. The signal further includes information about a matrix that includes diagonal elements and off-diagonal elements. The off-diagonal elements of the matrix are 2s-sparse. The method further includes performing randomized measurements of the off-diagonal elements of the matrix and recovering the matrix based on a direct measurement of the diagonal elements of the matrix.