Timeline for How to you encode a network as an adjacency-list in the quantum-gate model?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 23, 2018 at 8:02 | history | edited | Sanchayan Dutta |
edited tags
|
|
| Nov 15, 2018 at 9:10 | comment | added | Craig Gidney | @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. | |
| Nov 15, 2018 at 2:08 | comment | added | DrHamed | @Craig can you elaborate on your idea, please? | |
| Nov 15, 2018 at 2:01 | comment | added | Craig Gidney | 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. | |
| Nov 14, 2018 at 17:02 | answer | added | cnada | timeline score: 2 | |
| Nov 14, 2018 at 16:24 | comment | added | DrHamed | 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. | |
| Nov 14, 2018 at 16:10 | review | Close votes | |||
| Nov 15, 2018 at 13:30 | |||||
| Nov 14, 2018 at 12:52 | comment | added | cnada | Are you considering a representation where for each vertex you have its corresponding adjacency list, and you want them all in superposition? | |
| Nov 14, 2018 at 11:47 | history | edited | Sanchayan Dutta | CC BY-SA 4.0 |
edited tags; fixed grammar
|
| Nov 14, 2018 at 11:43 | history | asked | DrHamed | CC BY-SA 4.0 |