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 $\vec{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 $\mathcal{O}(M\log N)$. The runtime, which depends on the data density $\rho$ and on the parallelization paramater $M$, scales as $\mathcal{O}(\frac{1}{\sqrt{\rho }}\frac{N}{M}\log (M+1))$, which in the most parallel version ($M=N$) is always less than $\mathcal{O}(\sqrt{N}\log N)$. By analysing the data density, we prove that the average runtime is $\mathcal{O}({\log }^{1.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.

8 pages, 15 figures

References in corpus (11)

• Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicator
• Single-step implementation of high fidelity $n$-bit Toffoli gate
• Use of global interactions in efficient quantum circuit constructions
• A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation
• Quantum Fourier Transform Revisited
• Constructing quantum circuits with global gates
• Quantum state preparation protocol for encoding classical data into the amplitudes of a quantum information processing register's wave function
• An efficient quantum algorithm for preparation of uniform quantum superposition states
• Quantum data encoding as a distinct abstraction layer in the design of quantum circuits
• Pure state tomography with parallel unentangled measurements
• Sublinear Classical-to-Quantum Data Encoding using $n$-Toffoli Gates