Solving max/min problem for graphs based on Grover

Solving max/min problem for graphs based on Grover Ask Question Asked 2 years, 8 months ago Modified today Viewed 337 times 0 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): GDB stands for a "Graph-Database", meaning a QRAM so that the qubits |Graph⟩ | 𝐺 𝑟 𝑎 𝑝 ℎ ⟩ encode some kind of graph in m qubits. These states represent the adjacency matrix and the edge weights. | ψ 1 ⟩ | 𝜓 1 ⟩ (see the red vertical line) looks like (assuming n=2 so 4 different graphs): GD B † 𝐺 𝐷 𝐵 † 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. grovers-algorithmoptimizationoraclesgraph-states Share Improve this question Follow edited Jun 29, 2023 at 20:18 asked Jun 29, 2023 at 19:26 17tmh 93 3 bronze badges Add a comment 1 Answer Sorted by: Highest score (default) Date modified (newest first) Date created (oldest first) 0 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⟩=|1001⟩ | 9 ⟩ = | 1001 ⟩ , then vertices v 1 , v 4 𝑣 1 , 𝑣 4 would be in partition A 𝐴 , and v 2 , v 3 𝑣 2 , 𝑣 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. Share Improve this answer Follow answered Jun 30, 2023 at 3:58 MonteNero 3,4228 8 silver badges 27 27 bronze badges 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 | ψ 1 ⟩ | 𝜓 1 ⟩ ). 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? –  17tmh Commented Jun 30, 2023 at 15:20 Add a comment Your Answer Sign up or log in Sign up using Google Sign up using Email and Password Post as a guest Name Email Required, but never shown Post Your Answer By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy. Start asking to get answers Find the answer to your question by asking. Ask question Explore related questions grovers-algorithmoptimizationoraclesgraph-states See similar questions with these tags. The Overflow Blog Open source for awkward robots Domain expertise still wanted: the latest trends in AI-assisted knowledge for... Featured on Meta Logo updates to Stack Overflow's visual identity Related 3 Using Quantum Bit String Comparision inside Grover's algorithm 1 How to implement *nested* Grover search (in Quirk)? 4 Solving Hamiltonian eigenvalue problem 1 Solving a linear optimization problem with inequality constraints in qiskit? is it possible? Hot Network Questions Accounts for changing Kinetic energy of electrons in a circuit DocumentMetadata impeding the processing of otherwise normal file Pascal's Triangle ! In 1 Corinthians 7:8, does ἀγάμοις (agamois) refer to all unmarried people or specifically to widowers? How many degrees is the sum of the marked angles? About the Dwarapalakas of other deities Trimming causes compilation failure Boot manager that can load a kernel file on PC with a 8086 CPU The assumptions for causal inference seem obvious - why state them? My basic budget tracker Can a worker hired to do a job destroy the work if unpaid? About claims and evidence How do I unlock LUKS encrypted Ubuntu 24.04 (ext4) using a USB drive? In what sense is the Axiom of Multiple Choice weaker than the Axiom of Choice? How can I remove the handle from my faucet? What is the nuance of がわ as a suffix? Authorship in Mathematics AI overview in normal Firefox window but not in Private Window ATTiny816 - How are these two code fragments different? Protecting peonies from late freeze Regarding Transferred Manuscript Definition of n-huge cardinals in Harvey Friedman's works What TIME is it really referring to when Jesus said, "At the Renewal of All Things"? (Matthew 19:28) How do we know individual quarks don't carry all three color charges? Question feed By continuing to use this website, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. By exiting this window, default cookies will be accepted. To reject cookies, select an option from below. Customize settings Cookie Consent Preference Center When you visit any of our websites, it may store or retrieve information on your browser, mostly in the form of cookies. This information might be about you, your preferences, or your device and is mostly used to make the site work as you expect it to. The information does not usually directly identify you, but it can give you a more personalized experience. Because we respect your right to privacy, you can choose not to allow some types of cookies. Click on the different category headings to find out more and manage your preferences. Please note, blocking some types of cookies may impact your experience of the site and the services we are able to offer. Cookie Policy Accept all cookies Manage Consent Preferences Strictly Necessary Cookies Always Active These cookies are necessary for the website to function and cannot be switched off in our systems. They are usually only set in response to actions made by you which amount to a request for services, such as setting your privacy preferences, logging in or filling in forms. You can set your browser to block or alert you about these cookies, but some parts of the site will not then work. These cookies do not store any personally identifiable information. Targeting Cookies Targeting Cookies These cookies are used to make advertising messages more relevant to you and may be set through our site by us or by our advertising partners. They may be used to build a profile of your interests and show you relevant advertising on our site or on other sites. They do not store directly personal information, but are based on uniquely identifying your browser and internet device. Performance Cookies Performance Cookies These cookies allow us to count visits and traffic sources so we can measure and improve the performance of our site. They help us to know which pages are the most and least popular and see how visitors move around the site. All information these cookies collect is aggregated and therefore anonymous. If you do not allow these cookies we will not know when you have visited our site, and will not be able to monitor its performance. Functional Cookies Functional Cookies These cookies enable the website to provide enhanced functionality and personalisation. They may be set by us or by third party providers whose services we have added to our pages. If you do not allow these cookies then some or all of these services may not function properly. Cookie List Clear checkbox label label Apply Cancel Consent Leg.Interest checkbox label label checkbox label label checkbox label label Necessary cookies only Confirm My Choices