Solving max/min problem for graphs based on Grover

Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Stack Overflow for Teams is now called Stack Internal. Bring the best of human thought and AI automation together at your work. Bring the best of human thought and AI automation together at your work. Learn more Stack InternalKnowledge at workBring the best of human thought and AI automation together at your work.Basis is for this post ist the paper https://arxiv.org/pdf/1902.00445.pdfI 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):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.There are, of course, a number of "workspace" qubits that are not shown in the circuit above.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.Thanks for contributing an answer to Quantum Computing Stack Exchange!But avoid …Use MathJax to format equations. MathJax reference.To learn more, see our tips on writing great answers.Required, but never shown By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy. Start asking to get answersFind the answer to your question by asking.Explore related questionsSee similar questions with these tags.To subscribe to this RSS feed, copy and paste this URL into your RSS reader. Site design / logo © 2025 Stack Exchange Inc; user contributions licensed under CC BY-SA . rev 2025.11.24.37235