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.
Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.