How to convert QUBO (with non-zero diagonal elements) to Maxcut?

How to convert QUBO (with non-zero diagonal elements) to Maxcut? Ask Question Asked 1 year, 11 months ago Modified today Viewed 839 times 1 I want to solve QUBO with non-zero diagonal elements in matrix Q using QAOA. But I want to solve for a large enough problem size (30+ variables) and hence want to divide my circuit into subcircuits. Circuit cutting didn't work out for me, because graph is dense, so I want to try divide-and-conquer approaches proposed here and here. However, both papers divide the Maxcut problem. Hence the question: How to convert QUBO (with non-zero diagonal elements) to Maxcut? In this paper it is stated and shown that QUBO and Maxcut are equivalent. However, I haven't fully understood the proof and my code based on this proof isn't working (optimal cut isn't an optimal solution). Here's the code: h, J, ising_offset = from_Q_to_Ising(Q, qubo_offset) G = nx.Graph() for ki, v in h.items(): if abs(v) > 1e-3: # add new node and connect it with other nodes where diagonal weight is non-zero # flip the weight sign G.add_edge(0, ki[0] + 1, weight = -v) for kij, vij in J.items(): if abs(vij) > 1e-3: # flip the weight sign G.add_edge(kij[0] + 1, kij[1] + 1, weight = -v) Would be thankful for any suggestions regarding conversion, or any other way to use these divide-and-conquer approaches or other ways to split the QAOA circuit. programmingquantum-circuitoptimizationqaoaqubo Share Improve this question Follow edited Apr 13, 2024 at 22:12 FDGod 3,0192 2 gold badges 7 7 silver badges 33 33 bronze badges asked Apr 13, 2024 at 17:09 Oleksii 214 4 bronze badges You confused several concepts. MaxCut is an optimization problem; as the name suggests, it finds the maximum cut in a graph. QUBO is the name of the framework for formulating optimization problems. You can convert many optimization problems into QUBO formulation. Asking to convert QUBO into MaxCut is a meaningless question. Besides, all non-linear QUBO problems have non-zero non-diagonal elements. MaxCut is already formulated as a QUBO problem (in many physics papers), which is why it is used as a canonical example for many quantum optimization tutorials. –  MonteNero Commented Apr 13, 2024 at 18:02 @MonteNero I have a problem to solve (RCPSP to be exact), that I formulated as QUBO. However, I don't understand how to use all the MaxCut research (more specifically divide-and-conquer) for my QUBO formulation, as it has a linear component. –  Oleksii Commented Apr 13, 2024 at 18:29 I think I understand what you want to do. I suggest formulating a concrete, specific question. Currently, you posted a code unrelated to optimization and asked several vague general questions. This will improve your chances of getting an answer you are looking for. –  MonteNero Commented Apr 13, 2024 at 21:09 Add a comment 1 Answer Sorted by: Highest score (default) Date modified (newest first) Date created (oldest first) 1 It is well-known that any QUBO problem can be translated into an equivalent maximum cut problem (MaxCut), see ref 1. Given a weighted graph G=(V,E) 𝐺 = ( 𝑉 , 𝐸 ) with edge weights w ij 𝑤 𝑖 𝑗 , where (ij)∈E ( 𝑖 𝑗 ) ∈ 𝐸 , MaxCut asks for a partition of the vertices into two subsets such that the weight of connecting edges is maximized. More formally, for a vertex subset W⊂V 𝑊 ⊂ 𝑉 , we define the cut δ(W)={ij∈E∣i∈W,j∉W} 𝛿 ( 𝑊 ) = { 𝑖 𝑗 ∈ 𝐸 ∣ 𝑖 ∈ 𝑊 , 𝑗 ∉ 𝑊 } Furthermore, the weight of a cut δ(W) 𝛿 ( 𝑊 ) is defined as ∑ e∈δ(W) w e ∑ 𝑒 ∈ 𝛿 ( 𝑊 ) 𝑤 𝑒 MaxCut asks for a cut of maximum weight. The decision version of MaxCut is NP-complete [45]. A QUBO problem on n 𝑛 variables, defined by the coefficients q ij 𝑞 𝑖 𝑗 , j∈{1,…,n} 𝑗 ∈ { 1 , … , 𝑛 } , can be transformed into an equivalent MaxCut problem on (n+1) ( 𝑛 + 1 ) vertices. To this end, we consider the complete graph K n+1 𝐾 𝑛 + 1 with vertices V={0,1,…,n} 𝑉 = { 0 , 1 , … , 𝑛 } For an edge ij 𝑖 𝑗 with i,j>0 𝑖 , 𝑗 > 0 , we define its weight as w ij = q ij + q ji 𝑤 𝑖 𝑗 = 𝑞 𝑖 𝑗 + 𝑞 𝑗 𝑖 Moreover, for all edges of the form 0i 0 𝑖 with i>0 𝑖 > 0 , we set w 0i = ∑ j=1 n q ij + q ji 𝑤 0 𝑖 = ∑ 𝑗 = 1 𝑛 𝑞 𝑖 𝑗 + 𝑞 𝑗 𝑖 Deleting edges with zero weight finally yields a weighted MaxCut instance G=(V,E) 𝐺 = ( 𝑉 , 𝐸 ) . Given a cut δ(W) 𝛿 ( 𝑊 ) , we construct a solution Q 𝑄 as follows. For i∈{1,…,n} 𝑖 ∈ { 1 , … , 𝑛 } , we set x i =1 𝑥 𝑖 = 1 if i∉δ(W) 𝑖 ∉ 𝛿 ( 𝑊 ) , otherwise we set x i =0 𝑥 𝑖 = 0 . It is easily verified that if the cut has weight M 𝑀 , the QUBO solution has value Q=− M 2 +C 𝑄 = − 𝑀 2 + 𝐶 where C= 1 4 ( ∑ e∈E w e +2 ∑ i q ii + ∑ i<j q ij + q ji ) 𝐶 = 1 4 ( ∑ 𝑒 ∈ 𝐸 𝑤 𝑒 + 2 ∑ 𝑖 𝑞 𝑖 𝑖 + ∑ 𝑖 < 𝑗 𝑞 𝑖 𝑗 + 𝑞 𝑗 𝑖 ) ref 1: Experiments in 0-1 programming Share Improve this answer Follow edited 2 hours ago Adam 1031 1 bronze badge answered Jul 30, 2024 at 9:07 Yet another Random Guy 6094 4 silver badges 12 12 bronze badges 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 programmingquantum-circuitoptimizationqaoaqubo See similar questions with these tags. The Overflow Blog Domain expertise still wanted: the latest trends in AI-assisted knowledge for... Keeping the lights on for open source Featured on Meta Logo updates to Stack Overflow's visual identity Related 6 How to convert QUBO problem to Ising Hamiltonian? 2 How to solve QUBO problems in Q#? 1 Convert Hamiltonian to Ising Formulation or QUBO 0 qiskit: convert from ising result to qubo result? 1 Mapping a QUBO onto an observable for use with Qiskit QAOA 0 How to determine the penalty coefficients in QUBO objective functions 2 How to map QUBO to Ising and account for the sign change in non-diagonal elements? Hot Network Questions Cannot fit long table using longtblr Can company choose not to pay for my "retirement" account even though I worked all of 2025? Trying to find poem by POC quoting "Walk on the wild side" Which Elder Scrolls location is this? Arranging squares on a cube in isometric view Creating a Bar Graph using float values from a CSV file Can we respond to "way bigger" with "How way bigger?" Low DC gain on NPN transistor driving an LED Looking for info on a short story by Brian Mooney The Designation of 'Fundamental': Historical Origins of 'Fundamental Theorems' in Mathematics Air pressure on Noah's Ark Supplier demands more money to fulfil an order already paid for Would the federal government receiving money from brokering a business takeover be a breach of the Hatch Act? How many degrees is the sum of the marked angles? What game is this "Give me X, and my life is yours" meme from? Count valid programs in () The geometric intuition and principle of substitution for integrals "Out of malice"? PI on medical leave: ethics and etiquette Is any countably infinite set meager? Improving the resolution of raster layers displayed in 3D using Qgis2threejs in QGIS Can a contractor hired to do construction or renovations destroy the work if unpaid? 2026 International Congress of Mathematicians Bayesian dishonesty 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