1
$\begingroup$

Basis is for this post ist the paper https://arxiv.org/pdf/1902.00445.pdf

I want to do something similar using graph data encoded in quantum states. The circuit structure should look like this (first Grover iteration incl. the oracle):

enter image description here

  • GDB stands for a "Graph-Database", meaning a QRAM so that the qubits $|Graph\rangle$ encode some kind of graph in m qubits. These states represent the adjacency matrix and the edge weights.
  • $|\psi_1\rangle$ (see the red vertical line) looks like (assuming n=2 so 4 different graphs): enter image description here
  • $GDB^\dagger$ uncomputes the Graph-Database and the gate Grover stands for the usual "inversion about average"
  • The big "marking"-gate in middle is my question mark! Let me skip that for now.
  • The entire algorithm involves more than one iteration to update the threshold used in the marking-gate accordingly (see the paper). Finally, the Index of the graph that satisfies some kind of maximum or minimum requirement among all graphs should be measured with high probability, as usual in the amplitude amplification algorithm (Grover).

Question

Now the actual question is a bit strange, I admit. Can anyone image a graph-related problem where such a circuit could be useful, that is, what exactly could I do in the marking-gate? Any suggestion is welcome. It may be far from a real usecase. The key point is really to use the graph-encoding.

Edit 1

There are, of course, a number of "workspace" qubits that are not shown in the circuit above.

$\endgroup$

1 Answer 1

0
$\begingroup$

There are numerous possibilities.

A straightforward and commonly utilized concept is the generation of Hamiltonian cycles on a complete graph where the vertices symbolize cities, and edges represent distances.

In such a scenario, an oracle calculates the total weight of edges for each generated Hamiltonian cycle and then marks the index of a cycle whose total weight falls below a predetermined threshold. In essence, this approach attempts to solve a Travelling Salesman Problem by examining numerous Hamiltonian cycles and marking the less "expensive" ones in a superposition.

Another widely recognized problem in this realm is MaxCut. In this case, the index register provides guidance to GDB on how to partition the vertices of a graph. Subsequently, the oracle highlights the graph whose cut size exceeds a certain threshold. For example, if the index is $|9\rangle = |1001\rangle$, then vertices $v_1,v_4$ would be in partition $A$, and $v_2, v_3$ would be in partition $B$. The oracle then calculates the edges between partitions $A$ and $B$ (the cut) and computes its size. If the size surpasses the threshold, it is marked.

These are just a couple of examples.

$\endgroup$
1
  • $\begingroup$ I probably didn't make myself clear enough. I know about the Hamiltonian cycle and MaxCut problem, but those are problems on one single graph. However, I am interested in a problem where multiple graphs are candidates for a solution (see again $|\psi_1\rangle$). Of course one could construct a two-step process like: 1. Solve a single-graph-problem like TSP for each graph. 2. Find the minimum value among those solutions. But is there also perhaps a problem that is more obvious that I'm not seeing right now? $\endgroup$
    – 17tmh
    Jun 30, 2023 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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