6
$\begingroup$

After getting help here with XNOR & RCA gates I decided to dive into XOR Swaps & XOR linked lists. I was able to find this explanation for quantum XOR Swapping which seems sufficient for the time being. I am not able to find any information on quantum XOR linked lists however (Google returns "no results").

How would a quantum XOR linked list be expressed?

$\endgroup$
4
+50
$\begingroup$

Caveat. I can't be absolutely certain that no-one has contemplated a quantum XOR list before — but I can be pretty confident. On the theory side, the idea of data structures as granular as linked lists (of any description) is pretty low-level, and to my knowledge is not really the subject of research; and people working on architectures only dream of the day in which they might worry about how to store data structures in their machines. So it's likely that there is no pre-defined art on the subject.

Before we consider "quantum XOR linked lists", the main thing to consider is what a linked list does. It is just a data structure which is used to maintain a list of data items, where the 'links' encode memory addresses for the next or previous item in the list. This idea is pretty generic (that's a compliment, not an insult): it can be applied to any sort of data without modification. On the other hand, it is possible to contemplate ways to extend the addressing itself to the quantum regime: this is something which, at least in principle, you may want to do, for example if you are interested in superpositions of possible list values for some algorithm which relies on such a concept to work.

This motivates two concepts:

  • Classically linked lists of quantum data values, in which the data is quantum but the memory addresses are classical pointers to definite qubits or other quantum registers. This is the application of the notion of "linked list of [X]" to the case where 'X' happens to be quantum data. The data structure doesn't care that the data itself is quantum: the data structure is there to act as a box in which to order your data, and is completely agnostic as to what is to be done with that data.

    For this sort of linked list, the way to get an XOR linked list is simple: you do the same thing as for XOR Linked lists of classical data. The fact that the data is quantum doesn't make any difference to the data structure in this case, so you use the very same techniques.

  • Quantum-linked lists, in which the data is quantum, and so are the encodings of the memory addresses. This is what you would do if you wanted to consider superposition of possible lists, including arbitrary variations in list-length. If you're wondering how you could possibly retrieve data from a superposition of memory addresses, it seems to me that the answer is the same as you would do with any algorithm which queries a "quantum database" in superposition: you require access to a qRAM, as a means to perform coherent queries of a data bank. If the data stored at the address is also quantum, you cannot clone it of course; but perhaps you can move that data (in a particular branch of the superposition) from the qRAM to your active data qubits — your 'cache', if you will — in order to operate on it more quickly. After you have performed the operations you intend to perform on that cached data, you might then swap it back to the qRAM. In the meantime, the state of your working memory will be entangled with one or more registers of the qRAM, but there is nothing theoretically wrong with that, so long as you maintain the appropriate hygiene to keep from disrupting your data in ways that you do not intend. I have no specific suggestions for when you would actually want to do this, but as it is not an obviously ridiculous thing to want to do, I see no reason not to take this concept seriously.

    In such a list, one should generally expect the pointer values of elements later in the list, to be entangled with pointer values earlier in the list. You will have to be careful about how you store copies of memory addresses, as you compute them and (just as importantly!) uncompute them, to traverse the quantum linked list. The data structure might be represented almost as a decision tree, though there is likely some application of this data structure which would make the relative phases of the pointer values important, and which would distinguish it from a decision tree. (These are features which one should generally expect of a data structure built from quantum registers for memory addresses.)

    If there is any reason at all to consider superpositions of memory addresses, then as soon as it becomes reasonable at all to realise data structures such as linked lists on quantum computers, an XOR-linked list seems a very sensible idea for a data structure. The savings in resources for the links would be a significant benefit for the foreseeable future, with only modest overhead in the additional cached data required to compute the addresses for the forward and backward links. The way one would realise these are almost the same as for classical XOR-linked lists: the memory addresses are encoded as standard basis vectors, for which you may computer the XOR, and more generally you may take the superposition of the parities computed by XOR. The principle is essentially the same as for a more general quantum linked list; you just use a more elaborate encoding for the pointers. This may require a little bit more care to be taken to uncompute the links addresses as you traverse the list, but it seems likely that only a modest amount of additional work is required.

    The major constraint that I see for quantum-linked lists — whether singly-, doubly-, or XOR-linked — is the uncomputation of memory addresses as you traverse the list. Whether this ever poses a significant problem would probably depend on how and why you would want to traverse a quantum-linked list, which is to say, what you want to accomplish with it. However, it seems clear in principle that one can define such quantum-linked lists, and the way they would be implemented would be similar to a reversible implementation of classical linked lists, assuming that there is the appropriate architecture (such as qRAM in this case) to support the question of fetching data from addresses stored in superposition.

$\endgroup$

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.