Schoolbook multiplication of two -bit numbers costs bit operations
PHYSICS · Subjective · 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 The quantum circuit model
Problem
Schoolbook multiplication of two L-bit numbers costs O(L2) bit operations. Estimate the ratio of the number of bit operations needed to multiply two 2048-bit numbers compared with two 256-bit numbers, using this scaling.