Fast Quantum Amplitude Encoding of Typical Classical Data

We present an improved version of a quantum amplitude encoding scheme that encodes the N entries of a unit classical vector vecv=(v1,..,vN) into the amplitudes of a quantum state. Our approach has a quadratic speed-up with respect to the original one. We also describe several generalizations, including to complex entries of the input vector and a parameter M that determines the parallelization. The number of qubits required for the state preparation scales as O(Mlog N). The runtime, which depends on the data density ρ and on the parallelization paramater M, scales as O(frac1√ρfracNMlog (M+1)), which in the most parallel version (M=N) is always less than O(√Nlog N). By analysing the data density, we prove that the average runtime is O(log1.5 N) for uniformly random inputs. We present numerical evidence that this favourable runtime behaviour also holds for real-world data, such as radar satellite images. This is promising as it allows for an input-to-output advantage of the quantum Fourier transform.