3
$\begingroup$

Recently, I asked a question about programming languages that can be compatible with quantum computers.

Link to the question here: Will standard programming languages be applicable for quantum computing?

Recently, I have been trying to read and watch materials about new generation databases (I know it sounds quite fancy), but I am thinking about databases for quantum computing.... how should such databases look like? Does anyone of you have experience in designing such databases and would like to share their knowledge or indicate the source so that I can understand the topic myself?

I found Guy Harrison's book: Next Generation Databases: NoSQLand Big Data, link to the author's website: https://guyaharrison.squarespace.com/books

He points out that we need a database (for quantum computers) that will use qubit logic, i.e. we need a new language - QQL - Quantum Query Language.

Any links /books or your knowledge will be appreciated!

$\endgroup$
2
  • $\begingroup$ Have a look at Grover algorithm. It's main purpose is to search in an unordered database. $\endgroup$ Mar 20 at 12:49
  • $\begingroup$ Thanks for that. I'll at research papers. $\endgroup$
    – Mikolaj
    Mar 21 at 7:20

1 Answer 1

2
$\begingroup$

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:

  1. Quantum data indexed via a quantum index.
  2. Classical data indexed via a quantum index.
  3. Quantum data indexed via a classical index.
  4. 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: Circuit description of the previous database

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.

$\endgroup$
4
  • 1
    $\begingroup$ Nice answer. Concerning the qRAM, there is a device which can serves as qRAM in quantum communication network repeaters. The device is manufactured by Qunnect, try to Google it. $\endgroup$ Mar 22 at 7:14
  • $\begingroup$ @MartinVesely Thanks, I did not know about that! I only find high-level articles when Googling, do you know if there's a technical reference on what this qRAM is able to do and how did they do it? $\endgroup$ Mar 22 at 11:59
  • $\begingroup$ Thanks for such an answer! :) I have a lot to read now! I'll try to find some technical papers and if I found something I'll paste the link here. $\endgroup$
    – Mikolaj
    Mar 22 at 19:28
  • 1
    $\begingroup$ @TristanNemoz: Unfortunately I also find more or less news articles. Maybe this a little bit helps concerning techical realization: prnewswire.com/news-releases/…. $\endgroup$ Mar 23 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.