This survey summarizes several results about quantum computing related to (mostly static) data structures. First, we describe classical data structures for the set membership and the predecessor search problems: Perfect Hash tables for set membership by Fredman, Komlós and Szemerédi and a data structure by Beame and Fich for predecessor search. We also prove results about their space complexity (how many bits are required) and time complexity (how many bits have to be read to answer a query). After that, we turn our attention to classical data structures with quantum access. In the quantum access model, data is stored in classical bits, but they can be accessed in a quantum way: We may read several bits in superposition for unit cost. We give proofs for lower bounds in this setting that show that the classical data structures from the first section are, in some sense, asymptotically optimal - even in the quantum model. In fact, these proofs are simpler and give stronger results than previous proofs for the classical model of computation. The lower bound for set membership was proved by Radhakrishnan, Sen and Venkatesh and the result for the predecessor problem by Sen and Venkatesh. Finally, we examine fully quantum data structures. Instead of encoding the data in classical bits, we now encode it in qubits. We allow any unitary operation or measurement in order to answer queries. We describe one data structure by de Wolf for the set membership problem and also a general framework using fully quantum data structures in quantum walks by Jeffery, Kothari and Magniez.
This survey summarizes several results about quantum computing related to (mostly static) data structures. First, we describe classical data structures for the set membership and the predecessor search problems: Perfect Hash tables for set membership by Fredman, Komlós and Szemerédi and a data structure by Beame and Fich for predecessor search. We also prove results about their space complexity (how many bits are required) and time complexity (how many bits have to be read to answer a query). After that, we turn our attention to classical data structures with quantum access. In the quantum access model, data is stored in classical bits, but they can be accessed in a quantum way: We may read several bits in superposition for unit cost. We give proofs for lower bounds in this setting that show that the classical data structures from the first section are, in some sense, asymptotically optimal - even in the quantum model. In fact, these proofs are simpler and give stronger results than previous proofs for the classical model of computation. The lower bound for set membership was proved by Radhakrishnan, Sen and Venkatesh and the result for the predecessor problem by Sen and Venkatesh. Finally, we examine fully quantum data structures. Instead of encoding the data in classical bits, we now encode it in qubits. We allow any unitary operation or measurement in order to answer queries. We describe one data structure by de Wolf for the set membership problem and also a general framework using fully quantum data structures in quantum walks by Jeffery, Kothari and Magniez.
We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries of the form `Is x \in S?' can be answered. The goal is to use a small table and yet answer queries using few bitprobes. This problem was considered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where lower and upper bounds were shown for this problem in the classical deterministic and randomized models. In this paper, we formulate this problem in the "quantum bitprobe model" and show tradeoff results between space and time.In this model, the storage scheme is classical but the query scheme is quantum.We show, roughly speaking, that similar lower bounds hold in the quantum model as in the classical model, which imply that the classical upper bounds are more or less tight even in the quantum case. Our lower bounds are proved using linear algebraic techniques.
Studies the quantum complexity of the static set membership problem: given a subset S (|S|/spl les/n) of a universe of size m(/spl Gt/n), store it as a table, T:(0,1)/sup r//spl rarr/(0,1), of bits so that queries of the form 'is x in S?' can be answered. The goal is to use a small table and yet answer queries using a few bit probes. This problem was considered by H. Buhrman et al. (2000), who showed lower and upper bounds for this problem in the classical deterministic and randomised models. In this paper, we formulate this problem in the "quantum bit-probe model". We assume that access to the table T is provided by means of a black-box (oracle) unitary transform O/sub T/ that takes the basis state (y,b) to the basis state |y,b/spl oplus/T(y)>. The query algorithm is allowed to apply O/sub T/ on any superposition of basis states. We show tradeoff results between the space (defined as 2/sup r/) and the number of probes (oracle calls) in this model. Our results show that the lower bounds shown by Buhrman et al. for the classical model also hold (with minor differences) in the quantum bit-probe model. These bounds almost match the classical upper bounds. Our lower bounds are proved using linear algebraic arguments.
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.
Quantum computing is a popular topic in computer science, which has recently attracted many studies in various areas such as machine learning and network. However, the topic of quantum data structures seems neglected. There is an open problem in the database area: Can we improve existing data structures by quantum techniques? Consider a dataset of key-record pairs. Given an interval as a query range, a classical B+ tree can report all the records with keys within this interval, which is called a range query, in O(log N + k) time, where N is the total number of records and k is the output size. It is asymptotically optimal in a classical computer but not efficient enough in a quantum computer, because it is expected that the execution time and the output size are linear in a quantum computer. In this paper, we propose the quantum range query problem. Different from the classical range queries, a quantum range query returns the results in quantum bits, which has broad potential applications due to the foreseeable advance of quantum computers and quantum algorithms. To the best of our knowledge, we design the first tree-like quantum data structure called the quantum B+ tree. Based on this data structure, we propose a hybrid quantum-classical algorithm to do the range search. It answers a static quantum range query in O(log_B N) time, which is asymptotically optimal in quantum computers. Since the execution time does not depend on the output size (i.e., k, which could be as large as O(N)), it is significantly faster than the classical data structure. Moreover, we extend our quantum B+ tree to answer the dynamic and d-dimensional quantum range queries efficiently in O(log^2_B N) and O(log^d_B N) time, respectively. Our experimental results show that our proposed quantum data structures achieve up to 1000x improvement in the number of memory accesses compared to their classical competitors.
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited.
The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting.
We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an Ω(n4/3(loglogn)/(S1/3logn)) lower bound on the number of queries that a fully general quantum algorithm with at most S qubits of memory requires to sort n numbers from [n2]. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use.
We also use it to prove that, for any strongly universal (pairwise independent) hash function family H from n bits to m bits, almost all hash functions in H require any algorithm with at most S qubits of memory to make Ω(nm/S) quantum queries to input x in order to compute h(x), even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing h(x) with both h and x as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.
Quantum computing is currently gaining significant attention, not only from the academic community but also from industry, due to its potential applications across several fields for addressing complex problems. For any practical problem which may be tackled using quantum computing, it is imperative to represent the data used onto a quantum computing system. Depending on the application, many different types of data and data structures occur, including regular numbers, higher-dimensional data structures, e.g., n-dimensional images, up to graphs. This report aims to provide an overview of existing methods for representing these data types on gate-based quantum computers.