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
RSA-1024 uses a 1024-bit modulus, so L=1024. Using the resource count derived for order finding (a register of about 2L+3 qubits, with one reused control qubit, and each controlled modular multiplication built from about 10L2 Toffoli gates by schoolbook arithmetic, with 2L such multiplications needed for the modular exponentiation), estimate:
((a)) the number of qubits in the order-finding register;
((b)) the total number of Toffoli gates needed for the modular-exponentiation part of the circuit.