XOR parity constraint as a QUBO
Dear Community,
I just started learning about formulating problems for quantum annealing. I'm interested in realizing a parity constraint as a QUBO problem. A parity constraint requires the number of 1s in a set of variables to be either even or odd. For example, a XOR b = 1 (the set {a,b} must have an odd number of ones) or a XOR b XOR c = 0 (the set {a,b,c} must have an even number of ones).
In the Problem Solving Handbook, I came across the following table:
It was upsetting to see that an XOR operator requires an ancillary variable because the XOR parity constraints I am interested in are very long.
Just to be sure, I tried formulating a BQM for x_1 XOR x_2 = 1 by making a constraint satisfiability table. I got 1 - x_1 - x_2 + 2*x_1*x_2. I thought that maybe you don't need ancillary variables.
But then I tried finding a QUBO equation for x_1 XOR x_2 XOR x_3 = 1. I was unable to find the equation because a cubic term is required to create an equation that works for all input combinations. I hypothesize that for an n-variable parity constraint, you need n-2 ancillary variables, to compensate for the lack of cubic, quartic, and higher-order polynomial terms in QUBO. This might be why z <=> x_1 XOR x_2 required an ancillary bit (because there are three variables).
I'm wondering how to realize x_1 XOR x_2 XOR x_3 = 1 and ultimately, n-variable parity constraints, as a QUBO with ancillary variables. I don't really understand the how ancillary variables work conceptually (in a QUBO). Any resources are appreciated. I was also wondering if there are ways to reduce the number of ancillary variables as their number may get very high if my (n-2) hypothesis is correct. My end goal is to realize a system of parity constraints as a QUBO and optimize the number of 1s outputted as a solution using quantum annealing.
I am a total beginner so it is almost guaranteed that I am misunderstanding something really basic here. I would really appreciate any articles or tutorial suggestions about this stuff.
Many thanks!
Comments
Hello,
There are a few places in the documentation that you can learn about how ancillary variables are used.
Doing a quick search for "ancillary" in the following pages might be helpful:
Also, using the search bar at the top of the page in the Leap Community and Help Centre or this page will give you access to related resources within our documentation, community, and publications:
Often creating a truth table or penalty model for a smaller problem is the most effective way to understand what is possible within the constraints of a particular use case. The above reformulation handbook does a good job of demonstrating this.
Hopefully this was helpful. Please feel free to reach out with further questions.
Hello,
I also considered that problem of having a long OR (Similar to XOR). So a general learning from me was that whenever you dont need the variable is not complex and your using in a different variable (all contraints in the table are just z = ... , you try to reuse the variable of the first XOR in the next and so on) than you can direclty add the term with some coeffiencts to penalty. Therefore for XOR you can save the last variable definition and just use its formular directly in the penalty term (1 - x_1 - x_2 + 2*x_1*x_2)*c, where c is the coeffiencient of your problem.
But despite that looking in the reconfiguration pages from the last comment helps. For OR statements you can do 1 ancillary for 3 variables. and then build the whole OR statement by chain OR over three variables.
What I tried was reusing different OR, because I wanted to implement multiple long OR statements. For OR you have a very bad improvement, because of an entropy bound. For XOR I see much more potential. If you or anybody else is interested in reusibility of such contraints on the annealer, I am happy to collaborate.
Please sign in to leave a comment.