Khrushchev's formula is the cornerstone of the so-called Khrushchev theory, a body of results which has revolutionized the theory of orthogonal polynomials on the unit circle. This formula can be understood as a factorization of the Schur function for an orthogonal polynomial modification of a measure on the unit circle. No such formula is known in the case of matrix-valued measures. This constitutes the main obstacle to generalize Khrushchev theory to the matrix-valued setting, which we overcome in this paper. It was recently discovered that orthogonal polynomials on the unit circle and their matrix-valued versions play a significant role in the study of quantum walks, the quantum mechanical analogue of random walks. In particular, Schur functions turn out to be the mathematical tool which best codify the return properties of a discrete time quantum system, a topic in which Khrushchev's formula has profound and surprising implications. We will show that this connection between Schur functions and quantum walks is behind a simple proof of Khrushchev's formula via "quantum" diagrammatic techniques for CMV matrices. This does not merely give a quantum meaning to a known mathematical result, since the diagrammatic proof also works for matrix-valued measures. Actually, this path-counting approach is so fruitful that it provides different matrix generalizations of Khrushchev's formula, some of them new even in the case of scalar measures. Furthermore, the path-counting approach allows us to identify the properties of CMV matrices which are responsible for Khrushchev's formula. On the one hand, this helps to formalize and unify the diagrammatic proofs using simple operator theory tools. On the other hand, this is the origin of our main result which extends Khrushchev's formula beyond the CMV case, as a factorization rule for Schur functions related to general unitary operators.