A seismometer records digitised samples of ground displacement

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 The quantum Fourier transform and phase estimation

Problem

A seismometer records N=222≈4.19×106N = 2^{22} \approx 4.19\times10^{6} digitised samples of ground displacement, and the goal is to read off the size of one particular frequency component, whose power is expected to be ∣yk∣2≈0.05|y_k|^2 \approx 0.05, to a relative precision η=0.2\eta = 0.2 (20 per cent). ((a)) Estimate the number of gates needed to load a generic 2222^{22}-amplitude quantum state (order 2n2^n gates, n=22n = 22), and compare it with the number of arithmetic operations the classical fast Fourier transform uses on the same NN samples (order n2nn2^n). ((b)) Using M=(1−p)/(pη2)M = (1-p)/(p\eta^2) for the number of independent runs needed to estimate a probability pp to relative precision η\eta, estimate the number of runs MM needed, remembering that each run destroys the loaded state and needs a fresh preparation. ((c)) Combine (a) and (b) to estimate the total number of gates used by the quantum route, and compare with the classical fast Fourier transform cost from (a).

Browse the problem library