Quantum Period-Finding using One-Qubit Reduced Density Matrices

The quantum period-finding (QPF) algorithm can compute the period of a function exponentially faster than the best-known classical algorithm. In standard QPF, the output state has a primary contribution from r high-probability bit strings, where r is the period. Measurement of this state, combined with continued fraction analysis, reveals the unknown period. Here, we explore a different approach to QPF, where the period is obtained from single-qubit quantities - specifically, the set of one-qubit reduced density matrices (1-RDMs) - rather than the output bit strings of the entire quantum circuit. Using state-vector simulations, we compute the 1-RDMs of the QPF circuit for a generic periodic function. Analysis of these 1-RDMs as a function of period reveals distinctive patterns, which allows us to obtain the unknown period from the 1-RDMs using a numerical root-finding approach. Our results show that the 1-RDMs - a set of O(n) one-qubit marginals - contain enough information to reconstruct the period, which is typically obtained by sampling the space of O\(2ⁿ\) bit strings. Conceptually, this can be viewed as a "compression" of the information in the QPF algorithm, which enables period-finding from n one-qubit marginals. Our results motivate the development of approximate simulations of reduced density matrices to design novel period-finding algorithms.