Consider factoring by order finding with base

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch What quantum computers can compute efficiently

Problem

Consider factoring N=15N=15 by order finding with base a=2a=2, using quantum phase estimation with a t=9t=9 qubit phase register (so M=29=512M=2^9=512 possible measured outcomes). ((a)) Find the order rr of 22 modulo 1515 by direct computation of powers of 22 mod 1515. ((b)) Using rr, compute the candidate factors gcd⁡(2r/2−1,15)\gcd(2^{r/2}-1,15) and gcd⁡(2r/2+1,15)\gcd(2^{r/2}+1,15). ((c)) The ideal output distribution of phase estimation peaks at multiples of M/rM/r. List the peak locations. ((d)) A single run returns the measured value m=384m=384 out of M=512M=512. Use continued fractions on m/Mm/M to recover rr, and confirm it agrees with part (a).

Browse the problem library