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 $\boldsymbol{v}=(v_{1},..,v_{N})$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>v</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>v</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>.</mml:mo> <mml:mo>.</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>v</mml:mi> <mml:mi>N</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:math> 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 $\mathcal{O}(M\log N)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>M</mml:mi> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:math> . The runtime, which depends on the data density ρ and on the parallelization paramater M , scales as $\mathcal{O}(\frac{1}{\sqrt{\rho}}\frac{N}{M}\log (M+1))$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:msqrt> <mml:mi>ρ</mml:mi> </mml:msqrt> </mml:mfrac> <mml:mfrac> <mml:mi>N</mml:mi> <mml:mi>M</mml:mi> </mml:mfrac> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>M</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:math> , which in the most parallel version ( $M=N$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>M</mml:mi> <mml:mo>=</mml:mo> <mml:mi>N</mml:mi> </mml:math> ) is always less or equal than $\mathcal{O}(\sqrt{N}\log N)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mi>N</mml:mi> </mml:msqrt> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:math> . By analysing the data density, we prove that the average runtime is $\mathcal{O}(\log ^{1.5} N)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>1.5</mml:mn> </mml:msup> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:math> 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.