In order to use a quantum device to assess a classical dataset D, we need to representthe set D in a quantum state. Applying a quantum algorithm, that is a quantum state preparation algorithm, to convert classical data into quantum data would be the common method. Loading classical data into a quantum device is required in many current applications. Efficiently preparing a quantum state to be used as the initial state of a quantum algorithm is an essential step in developing efficient quantum algorithms, since many algorithms need to reload the initial state several times during their execution. The cost to initialize a quantum state can compromise the algorithm efficiency if the process of quantum states preparation is not efficient. The topic of quantum states preparation in quantum computing has been the focus of much attention. In this scope, preparing sparse quantum states is a more specific problem that remains open since many quantum algorithms also require sparse initialization. This dissertation presents the results of an investigation on sparse quantum states preparation with the development of three algorithms, with highlight to the preparation of sparse quantum states, the main contributionof this dissertation. From a classical input dataset with M patterns formed by pairs composed of a complex number and a binary pattern with n bits, this algorithm can prepare a quantum state with n qubits and continuous amplitudes. The cost of its steps is O(nM), classical cost of o(MlogM+nM)and requires a lower CNOT number than the main quantum state preparation algorithms currently known. The preparation of a quantumstate with 2 non-zero amplitudes reveals the need of fewer CNOT gates in n>>1 relation to the main known state preparation algorithms, with even more favorable results with s higher and less 1S in the binary string.
In order to use a quantum device to assess a classical dataset D, we need to representthe set D in a quantum state. Applying a quantum algorithm, that is a quantum state preparation algorithm, to convert classical data into quantum data would be the common method. Loading classical data into a quantum device is required in many current applications. Efficiently preparing a quantum state to be used as the initial state of a quantum algorithm is an essential step in developing efficient quantum algorithms, since many algorithms need to reload the initial state several times during their execution. The cost to initialize a quantum state can compromise the algorithm efficiency if the process of quantum states preparation is not efficient. The topic of quantum states preparation in quantum computing has been the focus of much attention. In this scope, preparing sparse quantum states is a more specific problem that remains open since many quantum algorithms also require sparse initialization. This dissertation presents the results of an investigation on sparse quantum states preparation with the development of three algorithms, with highlight to the preparation of sparse quantum states, the main contributionof this dissertation. From a classical input dataset with M patterns formed by pairs composed of a complex number and a binary pattern with n bits, this algorithm can prepare a quantum state with n qubits and continuous amplitudes. The cost of its steps is O(nM), classical cost of o(MlogM+nM)and requires a lower CNOT number than the main quantum state preparation algorithms currently known. The preparation of a quantumstate with 2 non-zero amplitudes reveals the need of fewer CNOT gates in n>>1 relation to the main known state preparation algorithms, with even more favorable results with s higher and less 1S in the binary string.
Quantum computers are gaining importance in various applications like quantum machine learning and quantum signal processing. These applications face significant challenges in loading classical datasets into quantum memory. With numerous algorithms available and multiple quality attributes to consider, comparing data loading methods is complex. Our objective is to compare (in a structured manner) various algorithms for loading classical datasets into quantum memory (by converting statevectors to circuits). We evaluate state preparation algorithms based on five key attributes: circuit depth, qubit count, classical runtime, statevector representation (dense or sparse), and circuit alterability. We use the Pareto set as a multi-objective optimization tool to identify algorithms with the best combination of properties. To improve comprehension and speed up comparisons, we also visually compare three metrics (namely, circuit depth, qubit count, and classical runtime). We compare seven algorithms for dense statevector conversion and six for sparse statevector conversion. Our analysis reduces the initial set of algorithms to two dense and two sparse groups, highlighting inherent trade-offs. This comparison methodology offers a structured approach for selecting algorithms based on specific needs. Researchers and practitioners can use it to help select data-loading algorithms for various quantum computing tasks.
A prerequisite for many quantum information processing tasks to truly surpass classical approaches is an efficient procedure to encode classical data in quantum superposition states. In this work, we present a circuit-based flip-flop quantum random access memory to construct a quantum database of classical information in a systematic and flexible way. For registering or updating classical data consisting of M entries, each represented by n bits, the method requires O(n) qubits and O(Mn) steps. With post-selection at an additional cost, our method can also store continuous data as probability amplitudes. As an example, we present a procedure to convert classical training data for a quantum supervised learning algorithm to a quantum state. Further improvements can be achieved by reducing the number of state preparation queries with the introduction of quantum forking.
We propose a hybrid quantum state preparation method based on the Walsh--Hadamard transform within the dense-to-sparse quantum state preparation framework. The method approximately prepares structured classical data in a quantum circuit through an indirect approach. Instead of directly preparing the dense amplitude-encoded state, the method first transforms the classical data into the Walsh domain and prepares only the largest-magnitude coefficients using a sparse state-preparation algorithm. The original state can then be approximately recovered through a parallel layer of Hadamard gates. Since this reconstruction requires no CNOT gates and has circuit depth 1, the proposed method introduces no additional CNOT or circuit-depth overhead, and its quantum preparation cost is determined by the underlying sparse state-preparation algorithm. Numerical results on representative benchmark signals demonstrate that the proposed method enables accurate state preparation for signals admitting sparse or approximately sparse representations in the Walsh domain.
Compared to general quantum states, the sparse states arise more frequently in the field of quantum computation. In this work we consider the preparation for n-qubit sparse quantum states with s nonzero amplitudes and propose two algorithms. The first algorithm uses O(ns/log2n+n) gates, improving upon previous methods by O(log2n). Moreover, the classical runtime of this algorithm is optimal. We further establish a matching lower bound for any algorithm that is not amplitude aware and employs at most poly(n) ancillary qubits. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path. An application is encoding the input data into a state with specified Hamming weight k in quantum machine learning, for which our algorithm constructs a circuit of size O((kn)log2n). This surpasses previous results by O(k/log2n) and is close to the lower bound O((kn)). The classical runtime is also nearly optimal. Both algorithms shrink the existing gap theoretically and provide increasing advantages numerically.
The preparation of quantum states is one of the most fundamental tasks in quantum computing, and a key primitive in many quantum algorithms. Of particular interest to areas such as quantum simulation and linear-system solvers are sparse quantum states, which contain only a small number s of non-zero computational basis states compared to a generic state. In this work, we present an approach that prepares s-sparse states on n qubits, reducing the number of Toffoli gates required compared to prior art. We work in the established framework of first preparing a dense state on a ⌈log(s)⌉-qubit sub-register, and then mapping this state to the target state via an isometry, with the latter step dominating the cost of the full algorithm. The speed-up is achieved by designing an efficient algorithm for finding and implementing the isometry. The worst-case Toffoli cost of our isometry circuit, which may be viewed as a batched version of an approach by Malvetti et al., is essentially 2s for sufficiently large values of n, yielding roughly a log(s)/2 improvement factor over the state-of-the-art. In numerical benchmarks on randomly chosen states, the cost is closer to s. With the improved isometry circuit, we examine the dense-state preparation step and present ways to optimize the joint cost of both steps, particularly in the case of target states with purely real coefficients, by outsourcing some sub-tasks from the dense-state preparation to the isometry.
Encoding classical data into quantum systems is a foundational step in the execution of nearly all quantum algorithms, and a critical bottleneck in realizing practical quantum advantage. This review provides a comprehensive account of the concepts, algorithms, and practical considerations associated with quantum data encoding. We trace the development from its early conceptual foundations to recent advances, considering commonly used access models, such as quantum state preparation, unitary synthesis, QRAM and block encoding. We survey the circuit size, depth, space-time tradeoffs, as well as non-Clifford resources required for fault-tolerant implementation. We also discuss the roles of different access models in quantum algorithms. Special attention is given to structured data, such as sparse data, Boolean functions and data represented by tensor networks. This review bridges theory and applications, serving both as a pedagogical guide for newcomers and as a reference for active researchers. We also highlight the pivotal role of quantum data encoding in quantum computing and provide insights into future directions that will enable quantum advantage.