Quantum Data Sketches

We are not aware of any prior work on designing classical sketches of quantum data, except for the paper [37] discussed in Section 4.2. There have been effort aiming to introduce quantum computing, quantum algorithms and quantum machine learning to the database community [13, 61, 44, 57, 9, 59]. We refer the readers to the recent tutorial [25] for an overview of these works. However, these initiatives either attempt to design and perform database operations directly on quantum data (i.e., assuming database elements are stored as quantum states) or focused on speeding up databases query optimization and transactions on classical data, setting them apart from the objectives pursued in this paper.

There are works [60, 38] focusing on applying classical data compression techniques (such as quantization) to the quantum state vector during quantum simulation. We note that our approach with sketches is quite different, as we aim to extract relevant information (often independent of the quantum states’ dimension) for various database operations.

In the context of quantum data, similar to classical database design, the efficiency of space and time is crucial during database initialization, indexing, and querying. Minimizing the number of quantum state copies used for constructing sketches is also important, as obtaining state copies can be costly and they cannot be fully recycled due to post-measurement disturbance. However, as we mentioned earlier, sample complexity is a secondary consideration in the data management setting, since the sketch-building/initialization is a one-time process.

A unit-time quantum operation comprises standard single-qubit gates like the Hadamard gate, Pauli gates, phase gate, and $T$ gate, as well as a two-qubit gate, such as the Controlled-NOT (CNOT) gate, that enables entangling operations.²²2We refer the readers to [46] for a detailed introduction of these gates. The combination of these gates is sufficient to approximate any unitary operation to arbitrary accuracy. We call these gates unit gates, and define the size of a circuit (for representing a unitary operation) to be the number of unit gates in the circuit.

As mentioned, a typical quantum measurement $\mathcal{M}$ on $n$ qubit systems consists of a unitary operator $U_{\mathcal{M}}$ followed by measurement in computational basis and classical post processing. Assuming that the classical post processing is polynomial, the overall time cost is typically dominated by the gate complexity of $U_{\mathcal{M}}$. It has been shown in [56] that a circuit depth of $\Theta(2^{n}/n)$ (i.e., $\Theta(d/\log d)$) is needed for constructing an arbitrary unitary operator $U$. To simplify matters, we assume that both executing an arbitrary $d$-dimensional quantum measurement and preparing an arbitrary $d$-dimensional state require $O(d)$ quantum time.

As quantum states are inherently high dimensional, even after effective sketching and summarization that we will illustrate in the subsequent sections, we will thus use Approximate Nearest Neighbor (ANN) via Locality Sensitive Hashing (LSH) to further speed up some database operations. This subsection will take a brief detour from our discussion of quantum data management.

Let us focus on the case that the distance function $dist(\cdot,\cdot)$ is $\ell_{1}$ or $\ell_{2}$. Indyk and Motwani [39] showed that $(r,\beta)$-ANN can be solved efficiently via LSH. The idea is that we first apply multiple hash functions to each vector in $X$; this part can be pre-computed and stored as an indexing. At the time of query, we apply the same set of hash functions to the query vector $q$. We then run over all vectors $p\in X$ such that $p$ and $q$ collide (i.e., fall into the same bin) on at least one hash function, and return the first vector $p$ if $dist(p,q)\leq\beta r$. If no such $p$ found after traversing a certain number of vectors in $X$, we return $\emptyset$.

We will use $\mathtt{ANN}(q,X,r,\beta)$ to denote the $(r,\beta)$-ANN search for a query vector $q$ in database $X$. The following is a summary of results on LSH-based ANN for $\ell_{1}/\ell_{2}$ distances.

In the classical data setting, the equality test on two data objects returns $1$ if $p=q$, and returns $0$ otherwise. In the quantum setting, since we cannot distinguish two quantum states using $o(d/\varepsilon^{2})$ copies of the states if their trace distance is at most $\varepsilon$, we need to introduce the approximation version of the equality test:

In words, we consider two quantum states the same if their trace distance is at most $\varepsilon$, and different if their trace distance is more than $\beta\varepsilon$. If the distance falls between the two values, then the decision can be arbitrary. The gap between yes and no is inevitable for quantum data.

Given two quantum states ${\phi}$ and ${\psi}$, which may be unknown, the standard method for estimating their trace distance is the swap test [8]. The algorithm uses a controlled-SWAP gate (can be implemented using $O(n)=O(\log d)$ unit gates) and two single-qubit Hadamard gates. The test outputs $1$ with probability $\frac{1+\absolutevalue{\phi^{\dagger}\psi}^{2}}{2}=1-\frac{D({\phi},{\psi})^{2}}{2}$, and $0$ otherwise. Therefore, using $O_{\beta}\left(\frac{1}{\varepsilon^{2}}\log{\frac{1}{\delta}}\right)$ such tests (the constant hidden in the big-$O$ depends on the constant $\beta$), we can differentiate the case $D({\phi},{\psi})>\beta\varepsilon$ from $D({\phi},{\psi})\leq\varepsilon$ with a probability $1-\delta$.

The main issue with this algorithm is that we have to consume fresh copies of database states for each equality test, which is unsustainable for a database system that is designed to answer an unlimited number of queries.

In the classical data setting, given a set of objects $X=\{p_{1},\ldots,p_{n}\}$ and a query object $q$, the search operation returns some $p_{i}\in X$ such that $p_{i}=q$ if such $p_{i}$ exists, and $\emptyset$ otherwise. In the quantum setting, again due to the difficulty of distinguishing two quantum states within a distance of $\epsilon$, we propose the following approximation version.

In other words, if there exists a state in the database which has a trace distance no more than $\varepsilon$ from the query state $\phi$, we return a state in $X$ whose distance is no more than $\beta\varepsilon$ from $\phi$ (similar to the ANN search). Else if all states in the database have distances larger than $\beta\varepsilon$ from the query state, we return $\emptyset$. In other cases, we either return a database state with distance no more than $\beta\varepsilon$ from the query state or return $\emptyset$.

The most straightforward way is to perform the $(\varepsilon,\beta)$-equality-test for each database state ${\psi}\in X$ with the query state ${\phi}$. By the above algorithm for equality test (setting $\delta=1/m^{2}$), we can determine with probability $(1-m\delta)=(1-o(1))$ whether there exists a state ${\psi}\in X$ such that the $(\varepsilon,\beta)$-equality-test on ${\phi}$ and ${\psi}$ returns $1$. The above procedure takes $O\left(m\log d\log m/\varepsilon^{2}\right)$ quantum time, which is linear in terms of the number of states in the database. Another significant limitation of this method is the necessity of using fresh copies of the database states for each search operation because of the equality test, making the database system unsustainable.

A closely related operation to search is join, which is one of the most important operations in relational database systems. We introduce the quantum version of natural join as follows.

In relational databases for classical data, selection is typically denoted by $\sigma_{\theta}(R)$, where $R$ is a relation and $\theta$ is a propositional formula that involves an attribute, a comparison operator in the set $\{<,>,\leq,\geq,=,\neq\}$, and a constant value for comparison (e.g., age $\geq 8$). However, in the quantum data setting, quantum states cannot be directly compared. We can only apply a measurement $\mathcal{M}$ on the state ${\phi}$ and get a random outcome according to the distribution $\mathcal{M}({\phi})$. As a classical analog, we would say a person’s age is $5$ with probability $0.6$ and $10$ with probability $0.4$.³³3This assembles probabilistic databases, but in the quantum data setting the probability distribution is not given explicitly, and the support size of the distribution is exponential in terms of the number of qubits of each quantum state. We thus look at the expectation value $\phi^{\dagger}M\phi$ for the observable $M$ corresponding to $\mathcal{M}$.

The quantity $\phi^{\dagger}M\phi$ holds significant importance in quantum mechanics (see, e.g., the textbook [51]). It can be used to provide an estimate of the system’s average energy in a particular state, describe the level of non-classical correlations between entangled particles, quantify quantum information such as entropy, coherence, and entanglement, etc.

We define the $\varepsilon$-approximate ‘$\geq$’ selection operation for quantum data as follows.

Note that the $\varepsilon$-approximate equality selection can be implemented by taking the difference between $(\eta-\varepsilon,\varepsilon)$-selection and $(\eta+2\varepsilon,\varepsilon)$-selection, which includes all ${\phi}$ with $\eta-\varepsilon\leq\phi^{\dagger}M\phi\leq\eta+\varepsilon$ and excludes all ${\phi}$ with $\phi^{\dagger}M\phi\leq\eta-2\varepsilon$ or $\phi^{\dagger}M\phi\geq\eta+2\varepsilon$. In the context of approximation, we can consider ‘$<$’ and ‘$>$’ the same as ‘$\leq$’ and ‘$\geq$’, respectively.

We also note that $(\varepsilon,\beta)$-search can also be handled by looking at $\phi^{\dagger}M\phi$ for a specific observable $M$, although this solution is not as efficient as that using the particular sketches that we shall design for the search operation. We have included a reduction from $(\epsilon,\beta)$-search to $(\eta,\epsilon)$-selection in Appendix D.

In the context of databases, we are particularly interested in the following type of observables.

$k$-local observables have been well studied in the literature (see [11, 42] and references therein). They are interesting because, in most practical scenarios, our goal is to identify specific properties of a quantum state (e.g., the energy, momentum, or spin of a photon) that rely on a small subset of qubits of the state. This is similar to the classical setting where most queries depend on a few attributes of a relational database table. For example, suppose we want to retrieve all records in a table containing patient information for individuals aged $80$ years or older with systolic blood pressure at least $140$, we only need to look at two attributes in the table: age and blood pressure. If we view each qubit of a quantum state as an attribute (e.g., spin, position, momentum, polarization, etc.), then a $k$-local observable performs selection on at most $k$ attributes of the quantum state.

A related problem of selection is sorting. As a motivation, we would like to sort a set of given quantum states according to their average energy with respect to an observable determined by a particular application. Note that there is no natural order between the quantum states themselves. Therefore, introducing an observable and computing the expectation value is somewhat necessary to establish a total order between the quantum states.

We define the sorting operation with respect to an observable $M$ as follows. Similar to the selection operation, we introduce an additive approximation $\varepsilon$ in the sorted order.

The concept of vector sketch is to represent a quantum state ${\phi}$ as a vector in $\mathbb{R}^{t}$ with $t\ll d$ instead of a vector in $\mathbb{C}^{d}$, while preserve certain distance properties. In this section, we design vector sketches for quantum states and then use them to conduct equality test, search, and join.

A natural way to construct the sketch is to take a number of random measurements on ${\phi}$, and write down the measurement outcomes as a vector. The following result is due to Sen [53], rewritten for pure quantum states.

Theorem 4.1 connects the trace distance of two quantum states to the $\ell_{1}$ distance of their measurement outcome distributions. We note that the distortion in (1), $D({\phi},{\psi})/(cD({\phi},{\psi}))=1/c$, is a big constant whose value left unspecified in [53].

Vectors $\mathcal{M}_{d}({\phi})$ and $\mathcal{M}_{d}({\psi})$ are discrete distributions with outcomes $\{1,2,\ldots,d\}$. It is well-known that for a discrete distribution $\mu$ over a domain of size $d$, using $\Theta\left({(d+\log(1/\delta))}/{\epsilon^{2}}\right)$ samples we can obtain an empirical distribution $\widetilde{\mu}$ such that $\norm{\mu-\widetilde{\mu}}_{1}\leq\epsilon$ with probability $1-\delta$ (see, e.g., [10]).

We can view $\widetilde{\mathcal{M}_{d}}({\phi})$ and $\widetilde{\mathcal{M}_{d}}({\psi})$ as two empirical probability vectors. However, since $d=2^{n}$ for a $n$-qubit state, it is both space-expensive to store $\widetilde{\mathcal{M}_{d}}({\phi})$ and time-expensive to use it for database operations.

In this section, we develop a classical data summarization that can be used to estimate the expectation value $\phi^{\dagger}M\phi$ for an arbitrary $k$-local observable $M$. We make use of the classical shadow tomography (CST), introduced in [37], to approximate $\phi^{\dagger}M\phi$ up to a small additive error. CST tries to extract minimal information about the quantum state, without performing complete tomography, to estimate certain properties of the state described by observables.

For completeness, let us briefly describe the CST procedure using Pauli measurements. For each of the $N$ copies of ${\phi}$, we select $n$ unitary operators, $U_{1},\ldots,U_{n}$, randomly and independently from the set $\{I,H,S^{\dagger}H\}$, where $H$ is the Hadamard gate and $S=\sqrt{Z}$ is the square root of the Pauli-$Z$ gate; see Appendix A.2 for their matrix representations. We then apply $U_{j}$ to the $j$-th qubit of ${\phi}$ and measure the state on the computational basis. The result is a binary string $b_{1},\ldots,b_{n}\in\{0,1\}$. The $n$ pairs $\{b_{j},\mathtt{index}(U_{j}))\}_{j=1}^{n}$ form a row vector, where $\mathtt{index}(U_{j})$ is the index of $U_{j}$ in the set $\{I,H,S^{\dagger}H\}$. We then repeat this process for $N$ times, getting $N$ rows, forming the seed matrix $A({\phi})=\{b_{i,j},\mathtt{index}(U_{i,j})\}_{i\in[N],j\in[n]}$. We call $A({\phi})$ the shadow seeds. Clearly, $A({\phi})$ can be stored using $O(nN)$ classical bits, since each entry of $A({\phi})$ belongs to $\{0,1\}\times\{0,1,2\}$.

At the time of query, given a $k$-local observable $M$, we first construct $k$-local classical shadows ${\tilde{\phi}_{i}}$ of the database state ${\phi}$ from each row $i\in[N]$ of its seed matrix $A({\phi})$ with respect to the $k$-local observable $M$. Suppose $M$ depends non-trivially on the $k$ qubits indexed by $Q\triangleq\{q_{1},\ldots,q_{k}\}$. Let $e_{0}=(0,1)^{T},e_{1}=(1,0)^{T}$ be the standard basis vectors in the two dimensional plane. For each row $i\in[N]$ and column $j\in Q$, we first construct a vector ${v_{i,j}}=U_{i,j}e_{b_{i,j}}$. Next, we construct the $i$-th shadow as a $2^{k}\times 2^{k}$ matrix $\hat{\rho}_{i}=\bigotimes_{j\in Q}\quantity(3v_{i,j}v^{\dagger}_{i,j}-I),$ where $I$ is the $2\times 2$ identity matrix. Finally, the estimator for $\phi^{\dagger}M\phi$ is given by $T=\frac{1}{N}\sum_{i\in[N]}\tr{M\hat{\rho}_{i}}$. The following theorem states that $T$ is a good approximation of the expectation value $\phi^{\dagger}M\phi$.

Note that the space cost and query time are both independent of the state dimension $d$.

Typically, the $k$-local observable $M$ can be expressed as a quantum circuit with $\text{poly}(k)$ gate complexity. In this case, we propose a new estimation algorithm to further improve the total query time from $O(16^{k})$ to $O(9^{k})$ (omitting other less critical factors) by an approach we call QCQC (quantum$\to$classical$\to$quantum$\to$classical). We have the following theorem, whose proof can be found in Appendix B.3.