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 n ) 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 period-finding algorithms.