Fast quantum amplitude encoding of typical classical data

Abstract We present an improved version of a quantum amplitude encoding scheme that encodes the N entries of a unit classical vector v= (v₁,. . , v₍) v = (v 1,. . , v N) 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 (M N) O (M log N). The runtime, which depends on the data density ρ and on the parallelization paramater M, scales as O (1NM (M+1) ) O (1 ρ N M log (M + 1) ), which in the most parallel version (M=N M = N) is always less or equal than O (N N) O (N log N). By analysing the data density, we prove that the average runtime is O (^1. 5 N) O (log 1. 5 N) for input vectors that are uniformly sampled on the N -sphere. 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.