Appendix B — Measured Quantum Walk is Markov

Let \(X_i\) be the \(i\)th readout in the measured quantum walk protocol. This implies that immediately after the \(i\)th measurement, the state of the walker is \(|X_i\rangle\). After \(\tau\) steps, the walker is in state \(E^{\tau}|X_i\rangle\). The probability of measuring the walker in \(X_{i+1}\) is given by \(|\langle X_{i+1}| E^{\tau}X_i\rangle|^2\). Thus, \(P(X_{i+1} = X_{i+1} | X_i, \dots, X_0) = P(X_{i+1} = X_{i+1} | X_i)\), which implies that the readouts in the measured quantum walk protocol is a Markov process.