Quantum Computing, Quantum, Science, Science Communication, Nonfiction.
is exponentially long in the number of qubits — that’s 2n complex numbers for n qubits. The FFT approximates the DFT but would still require more than 2n steps to calculate it for this list of numbers. However, Shor and others showed that the DFT can be applied to the quantum data with a quantum