Disclaimer: I'm no expert in that field and everything that follows will be mere suppositions.
The very first question to be answered is: what a quantum database looks like? And to answer that, one must ask: why does one need quantum databases for? It is important to keep in mind that quantum computing is not to replace classical computing. Therefore, the classical need for databases doesn't translate necessarily well to the quantum world.
There are four ways to see a quantum database:
- Quantum data indexed via a quantum index.
- Classical data indexed via a quantum index.
- Quantum data indexed via a classical index.
- Classical data indexed via a classical index.
The question is: which of these make sense?
Quantum data indexed via a quantum index
Such a database acts in the following way:
$$\sum_x|x\rangle\to\sum_x|x\rangle\left|\psi_x\right\rangle$$
where $\psi_x$ is the $x$th item in the database. Such an oracle is usually called Quantum RAM. QRAM is a heavily discussed topic, mostly because on the one hand, a lot of Quantum Machine Learning algorithms achieve a quantum speedup only if they can initialize some state from a QRAM, but on the other hand there is no device that allows us to do that for now (as far as I know).
QRAM is, in my humble opinion, what comes the closest to what we can imagine by being a quantum database, and I would recommend to learn more about it if you're interested in this topic.
Classical data indexed via a quantum index
Such a database acts in the following way:
$$\sum_x|x\rangle\to\sum_x|x\rangle\left|\psi_x\right\rangle$$
where $\psi_x$ is the state corresponding to the $x$th bitstring in the database.
Contrarily to QRAM, such a database can only store bitstrings. This effectively means that while it acts like a QRAM, the number of "states" it can store is limited. One may well imagine such a bitstring to be composed of two parts: an indentifier for the basis to use, and an identifier for the state of this basis. For instance, the database which contains $00$, $01$, $10$ and $11$ could represent the states $|0\rangle$, $|1\rangle$, $\frac{|0\rangle+|1\rangle}{\sqrt{2}}$ and $\frac{|0\rangle-|1\rangle}{\sqrt{2}}$.
While less useful than QRAM since less general, it still has the advantage of being sometimes easily implemented. For instance, the aforementioned database can be represented using the following circuit:
In fact, this database is completely equivalent to the embedding oracle:
$$\sum_x|x\rangle\to\sum_x|x\rangle|f(x)\rangle$$
where $f$ is a classical function. It has numerous applications, for instance in Simon's algorithm and can provide a quantum advantage with less assumptions than the QRAM.
Quantum data indexed via a classical index
This is represented by a set of quantum states $\left|\psi_i\right\rangle$, which will take as input a classical index and return the associated quantum state. Because of the no-cloning theorem and without any extra assumption, the state that is returned comes from a previous computation and is deleted from the database once it has been queried.
It provides no quantum speedup.
Classical data indexed via a classical index
These are just classical databases.
What kind of quantum databases might we expect in the future?
Clearly, the most promising schemes are those using a quantim index, since we know that they may allow for an exponential quantum speedup in some cases.
What would a Quantum Query Language look like?
Now that we know that a quantum database would surely accept a quantum index, what would a QQL be like?
A quantum index is no different from a classical index in its structure. Let us assume that our database has three columns, namely name, age and town, and we would like to retrieve the quantum states such that the name column is equal to Potato and the age one is equal to 18. In SQL, such
a query would look like this:
SELECT * FROM table WHERE name="Potato" AND age <= 18
The very first thing to do is to convert the values we're looking for to binary strings, so that we can represent them with quantum states. For the age column, it's not too difficult, we simply take the binary representation of $18$: 10010. For the name one, we can use the ASCII representation: 101000011011111110100110000111101001101111. Thus, the corresponding index for our database is:
$$\sum_{\text{town}}|101000011011111110100110000111101001101111\rangle|10010\rangle|\text{town}\rangle$$
We can then query the database with this index and create our desired state. Note that every state must have a representation in the database.
Thus, the only point of a QQL would be to create the index state from a classical description as done above.
A bit of a digression here, but for complex queries, it may be required to use Amplitude Amplification as done in Grover's algorithm. Basically, the QQL would create an oracle $f$ such that $f(x)=1$ if and only if $x$ is a bitstring satisfying the query and then use Amplitude Amplification to only select interesting states. The former strategy may be very bad, since creating an index state with a single bitstring takes $\mathcal{O}(1)$ the "classical" way and $\mathcal{O}\left(2^{\frac n2}\right)$ the "Grover's" way.
That said, a QQL does not have to be different in its syntax from a classical QL. What's different is the way it selects database's elements.
Finally, note that one may think that for quantum data, the QQL would have to allow to query according to the values that are stored, which would result in stuff like "get the separable states where the associated age column is equal to 18". This is not possible, since there is no quantum gate that takes a state $|\psi\rangle$ and tells us whether it is separable. The best strategy in that case is to classically store this in a column, which boilds down to what I've described above.
The explanation was quite lengthy, please do no hesitate to point out anything you wouldn't have understood or anything I would have missed.
