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 Order finding and Shor's factoring algorithm
Problem
Order finding is to be run for N=35 with a=3.
((a)) Find the order r of 3 modulo 35 by repeated multiplication, and state L=⌈log2N⌉.
((b)) Using the phase-estimation register-size rule t=m+⌈log2(2+1/2ϵ)⌉, with the m=2L+1 significant bits that order finding needs and a target failure probability ϵ=0.05, find the number of control qubits t.
((c)) Each run then gives, with probability at least 1−ϵ, a phase estimate within 1/2r2 of s/r, for an s drawn uniformly from 0 to r−1. Find the smallest number of independent runs needed for the probability of at least one such estimate to reach 99%.
((d)) Continued fractions return r itself from such an estimate only when gcd(s,r)=1. Find the fraction of the r values of s for which this holds, and hence the smallest number of independent runs needed for the probability that at least one run returns r directly to reach 99%.
((e)) Each controlled modular multiplication in the exponentiation part of the circuit is built from about 10L2 Toffoli gates (schoolbook arithmetic), and there is one such multiplication per control qubit. Using the standard decomposition of a Toffoli gate into 6 two-qubit CNOT gates, estimate the total number of CNOT gates in the exponentiation part of the circuit.