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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"> <a:mi>r</a:mi> </a:math> high-probability bit strings, where <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"> <b:mi>r</b:mi> </b:math> 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 <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"> <c:mrow> <c:mi mathvariant="script">O</c:mi> <c:mo>(</c:mo> <c:mi>n</c:mi> <c:mo>)</c:mo> </c:mrow> </c:math> one-qubit marginals—contain enough information to reconstruct the period, which is typically obtained by sampling the space of <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"> <e:mrow> <e:mi mathvariant="script">O</e:mi> <e:mo>(</e:mo> <e:msup> <e:mn>2</e:mn> <e:mi>n</e:mi> </e:msup> <e:mo>)</e:mo> </e:mrow> </e:math> bit strings. Conceptually, this can be viewed as a “compression” of the information in the QPF algorithm, which enables period finding from <g:math xmlns:g="http://www.w3.org/1998/Math/MathML"> <g:mi>n</g:mi> </g:math> one-qubit marginals. Our results motivate the development of approximate simulations of reduced density matrices to design period-finding algorithms.