I have a network problem that I believe would be represented as an adjacency-list on a quantum circuit. Typically, the list is up for traversing from various perspectives (e.g., shortest-path between two points).

Adjacency-list example:

x-> a, b, c
y-> a, d, e
x-> b, c, d

Any insight will be much appreciated!

  • 2
    $\begingroup$ Are you considering a representation where for each vertex you have its corresponding adjacency list, and you want them all in superposition? $\endgroup$ – cnada Nov 14 '18 at 12:52
  • 1
    $\begingroup$ Yes, indeed. Apologies if that wasn't clear from the example I demonstrated above. They all have to be in superposition initially to cut down the traversal time complexity. $\endgroup$ – DrHamed Nov 14 '18 at 16:24
  • 1
    $\begingroup$ I recommend not using an adjacency list because it requires pointer dereferences. You'd need to implement QRAM circuits, and that would mean you have two problems instead of one. An adjacency matrix will almost certainly be a) easier to use and b) more efficient. $\endgroup$ – Craig Gidney Nov 15 '18 at 2:01
  • $\begingroup$ @Craig can you elaborate on your idea, please? $\endgroup$ – DrHamed Nov 15 '18 at 2:08
  • $\begingroup$ @DrHamed QRAM circuits have a cost that's linear in the size of memory, so reading an adjacency list of K items will have cost N * K, which is more expensive than a single pass through a column of an adjacency matrix. Also, if K isn't a compile time constant, you're in for some real trouble because you'll need an instruction pointer under superposition doing lookups into QRAM storing instructions. If you don't want to implement a complete CPU, I'd really recommend against it. $\endgroup$ – Craig Gidney Nov 15 '18 at 9:10

Say you have $m$ vertices and the longest list you can build is of size $n$.

The simplest way I could think of is an encoding in basis state like : $$ | \text{origin} \rangle | v_0 (\text{origin})\rangle |v_1 (\text{origin})\rangle... |v_{n-1}(\text{origin})\rangle $$

We basically would encode the origin vertex and its corresponding n-sized adjacency-list whose elements are noted by $ v_0...v_{n-1} $. Potentially, the list may be of size less than $n$ but you can encode an empty element as a bitstring of your choice ($000$ for instance). Each vertex would be represented by a bit string of approximately $ \log(m+1) $ (qu)bits if you take into account the empty element.

In your example, the elements would be represented as $$(\text{empty},000),(a,001), (b,010), (c,011), (x,111), \cdots$$

For $x \to a,b,c$ you would have : $$ | x \rangle | a\rangle |b\rangle|c\rangle = | 111 \rangle | 001\rangle |010\rangle|011\rangle = |111 001 010 011 \rangle$$

That means also you can have all pairs of $(\text{origin, list})$ in superposition, where at the end you retrieve one by measurement according to the corresponding amplitudes.

  • $\begingroup$ would you be able to provide the quantum circuit for the x ->a,b,c nodes? Also, any references that back up your solution would be most appreciated! $\endgroup$ – DrHamed Nov 14 '18 at 22:07
  • 1
    $\begingroup$ Well if it is just one list, you would use NOT gates where you need 1s. And I came up with the idea without a reference in mind actually. $\endgroup$ – cnada Nov 14 '18 at 22:26
  • $\begingroup$ well, it is a simplified network, right? but ok. How about the circuit? Is this something you can provide? $\endgroup$ – DrHamed Nov 14 '18 at 23:32
  • $\begingroup$ It depends on what kind of input state you want to create to be fair (like just a list represented by a bitstring that you can create using NOT gates from the all 0 state or a superposition of bitstrings). You asked in your question about the encoding only. $\endgroup$ – cnada Nov 15 '18 at 0:50
  • $\begingroup$ @DrHamed But if I understand your new question (that you can ask opening a new one), I guess you need a way to create a specific superposition of bitstrings, which is not done by the Hadamard transform which gives you all bitstrings in superposition. Am I right? $\endgroup$ – cnada Nov 15 '18 at 2:59

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.