As quantum computers are based on the laws of quantum mechanics, they are capable of solving certain problems faster than their classical counterparts. However, often algorithms which a theoretical speed-up assume that data can be loaded efficiently. In general, the runtime complexity of the loading routine depends on (i) the data encoding that defines how the data is represented and (ii) the data itself. In some cases, loading the data requires at least exponential time which destroys a potential speed-up. And especially for the first generation of devices that are currently available, the resources (qubits and operations) needed to encode the data are limited. Therefore, understanding the consequences of a particular data encoding is crucial. To capture knowledge about different encodings, we present two data encoding patterns that extend our previous collection of encoding patterns [1].
Abstract As quantum computers are based on the laws of quantum mechanics, they are capable of solving certain problems faster than their classical counterparts. However, quantum algorithms with a theoretical speed‐up often assume that data can be loaded efficiently. In general, the runtime complexity of the loading routine depends on (i) the data encoding that defines how the data is represented by the state of the quantum computer and (ii) the data itself. In some cases, loading the data requires at least exponential time that destroys a potential speed‐up. And especially for the first generation of devices that are currently available, the resources (qubits and operations) needed to encode the data are limited. In this work, we, therefore, present six patterns that describe how data is handled by quantum computers.
The use of quantum processing units (QPUs) promises speed-ups for solving computational problems, in particular for discrete optimisation. While a few groundbreaking algorithmic approaches are known that can provably outperform classical computers, we observe a scarcity of programming abstractions for constructing efficient quantum algorithms. A good fraction of the literature that addresses solving concrete problems related to database management concentrates on casting them as quadratic unconstrained binary optimisation problems (QUBOs), which can then, among others, be processed on gate-based machines (using the quantum approximate optimisation algorithm), or quantum annealers. A critical aspect that affects efficiency and scalability of either of these approaches is how classical data are loaded into qubits, respectively how problems are encoded into QUBO representation. The effectiveness of encodings is known to be of crucial importance for quantum computers, especially since the amount of available qubits is strongly limited in the era of noisy, intermediate-size quantum computers.
A crucial subroutine in quantum computing is to load the classical data of
N complex numbers into the amplitude of a superposed $n=\ensuremath{\lceil}{log}_{2}N\ensuremath{\rceil}$-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least
O(N) constant weight operations. However, the proof assumes that only
n qubits are used, whereas the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with
O(n2) circuit depth to encode any
N complex numbers using only single- and two-qubit gates, and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with
O(N2) ancillary qubits,
O(n2) circuit depth, and
O(n2) average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits, and at most
O(n) qubits are entangled. We also prove a fundamental lower bound $\mathrm{\ensuremath{\Omega}}(n)$ for the minimum circuit depth and runtime with an arbitrary number of ancillary qubits, aligning with our scheme with
O(n2). The algorithms are expected to have wide applications in both near-term and universal quantum computing.
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.
A crucial subroutine in quantum computing is to load the classical data of
N complex numbers into the amplitude of a superposed
n=⌈log2N⌉-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least
O(N) constant weight operations. However, the proof assumes that only
n qubits are used, whereas the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with
O(n2) circuit depth to encode any
N complex numbers using only single-, two-qubit gates and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with
O(N2) ancillary qubits,
O(n2) circuit depth, and
O(n2) average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits and at most
O(n) qubits are entangled. We also prove a fundamental lower bound $\mitΩ(n)$ for the minimum circuit depth and runtime with arbitrary number of ancillary qubits, aligning with our scheme with
O(n2). The algorithms are expected to have wide applications in both near-term and universal quantum computing.