# Polynomial Constrained Boolean Optimization (PCBO) problems with qubovert

*qubovert* must be pip installed.

Import `boolean_var` from `qubovert`. This will create Polynomial Constrained Boolean Optimization (PCBO) objects.


```python
from qubovert import boolean_var
```

Let's try to encode the optimization problem of finding the minimum of $C$, where

$$C = x_0 x_1 - 2x_1 + x_1 x_2 x_3.$$


```python
# create the variables
x = [boolean_var("x%d" % i) for i in range(4)]

C = x[0] * x[1] - 2 * x[1] + x[1] * x[2] * x[3]

print(C)
```

    {('x1', 'x0'): 1, ('x1',): -2, ('x1', 'x3', 'x2'): 1}


And we subject $C$ to the constraints

$$x_0 \oplus x_1 = x_3, \quad 3x_0 + 2x_1 + 4x_3 < 7, \quad {\rm and} \quad x_0 x_1 = x_3 - x_2.$$

To enforce the constraints, we will pick a symbol $\lambda$ that we can tune as we like later.


```python
#!pip install sympy
from sympy import Symbol

lam = Symbol("lam", real=True, positive=True)

C.add_constraint_eq_XOR(
    x[3], x[0], x[1],
    lam=lam
).add_constraint_lt_zero(
    3 * x[0] + 2 * x[1] + 4 * x[3] - 7,
    lam=lam
).add_constraint_eq_zero(
    x[0] * x[1] - x[3] + x[2],
    lam=lam
)

print(C)
```

    {('x1', 'x0'): 11*lam + 1, ('x1',): -19*lam - 2, ('x1', 'x3', 'x2'): 1, ('x0',): -26*lam, ('x3', 'x0'): 22*lam, ('x1', 'x3', 'x0'): 2*lam, ('x1', 'x3'): 14*lam, ('x3',): -30*lam, ('__a0', 'x0'): 6*lam, ('__a1', 'x0'): 12*lam, ('__a2', 'x0'): 24*lam, ('x1', '__a0'): 4*lam, ('x1', '__a1'): 8*lam, ('x1', '__a2'): 16*lam, ('x3', '__a0'): 8*lam, ('x3', '__a1'): 16*lam, ('x3', '__a2'): 32*lam, (): 36*lam, ('__a0',): -11*lam, ('__a1',): -20*lam, ('__a2',): -32*lam, ('__a0', '__a1'): 4*lam, ('__a2', '__a0'): 8*lam, ('__a2', '__a1'): 16*lam, ('x1', 'x2', 'x0'): 2*lam, ('x3', 'x2'): -2*lam, ('x2',): lam}


Notice that the constraints are automatically added to the objective function, and in particular the inequality constraint introduced some ancilla bits (labeled `'_a0'`, `'_a1'`, and `'_a2'`). Let's look at the constraints.


```python
print(C.constraints)
```

    {'eq': [{('x0',): 1, ('x1', 'x0'): -2, ('x1',): 1, ('x3',): -1}, {('x1', 'x0'): 1, ('x3',): -1, ('x2',): 1}], 'lt': [{('x0',): 3, ('x1',): 2, ('x3',): 4, (): -7}]}


Notice there are two equality constraints and one inequality constraint. The first equality one comes from enforcing the XOR constraint, and the second comes from enforcing the other equality constraint. The `'eq'` key of the constraints dictionary indicates that the quantity equals zero, and the `'lt'` key of the constraints dictionary indicates that the quantity is less than zero. Other possible keys are `'le'`, `'gt'`, `'ge'`, and `'ne'`. See the docstrings for `PCBO.add_constraint_eq_zero`, `PCBO.add_constraint_lt_zero`, `PCBO.add_constraint_le_zero`, `PCBO.add_constraint_gt_zero`, `PCBO.add_constraint_ge_zero`, and `PCBO.add_constraint_ne_zero` for info.

For testing purposes, let's solve this bruteforce to make sure everything is working.


```python
solutions = C.solve_bruteforce(all_solutions=True)
print(solutions)
```

    [{'x1': 1, 'x0': 0, 'x3': 1, 'x2': 1, '__a0': 0, '__a1': 0, '__a2': 0}]


Notice that there is one unique solution that minimizes the objective function and obeys all the constraints. We can get rid of the ancilla information with ``C.remove_ancilla_from_solution``.


```python
solution = solutions[0]
C.remove_ancilla_from_solution(solution)
```




    {'x1': 1, 'x0': 0, 'x3': 1, 'x2': 1}



Now let's solve this problem with a generic QUBO solver. Notice that the degree of problem is more than two, making `C` not a natural Quadratic Unconstrained Boolean Optimization Problem (QUBO).


```python
C.degree
```




    3



We can convert it to a QUBO (note that there are some options for the reduction from PUBO to QUBO, see the `C.to_qubo` method for details). Ancilla bits will need to be added, and bit labels are mapped to integers.


```python
Q = C.to_qubo()
print("num PUBO variables", C.num_binary_variables)
print("num QUBO variables", Q.num_binary_variables)
print()
print(Q)
```

    num PUBO variables 7
    num QUBO variables 9
    
    {(0, 1): 13*lam + 2, (0,): -19*lam - 2, (7,): 6*lam + 9, (0, 2): 16*lam + 3, (0, 7): -4*lam - 6, (2, 7): -4*lam - 6, (3, 7): 1, (1,): -26*lam, (1, 2): 22*lam, (1, 7): 2*lam, (2,): -30*lam, (1, 4): 6*lam, (1, 5): 12*lam, (1, 6): 24*lam, (0, 4): 4*lam, (0, 5): 8*lam, (0, 6): 16*lam, (2, 4): 8*lam, (2, 5): 16*lam, (2, 6): 32*lam, (4,): -11*lam, (5,): -20*lam, (6,): -32*lam, (4, 5): 4*lam, (4, 6): 8*lam, (5, 6): 16*lam, (8,): 6*lam + 3, (0, 8): -4*lam - 2, (1, 8): -4*lam - 2, (3, 8): 2*lam, (2, 3): -2*lam, (3,): lam, (): 36*lam}


For testing purposes, let's solve this with bruteforce to see what the proper value of $\lambda$ should be to enforce the constraints. Notice how we remap the QUBO solution to the PCBO solution with `C.convert_solution(x)`.


```python
for l in (1, 2, 3):
    Q_temp = Q.subs({lam: l})
    solutions = Q_temp.solve_bruteforce(all_solutions=True)
    solutions = [C.convert_solution(x) for x in solutions]
    print('lam', l)
    for s in solutions:
        print("\t", s, "is", "valid" if C.is_solution_valid(s) else "invalid")
    print()
```

    lam 1
    	 {'x1': 1, 'x0': 0, 'x3': 0, 'x2': 0, '__a0': 0, '__a1': 0, '__a2': 1} is invalid
    	 {'x1': 1, 'x0': 0, 'x3': 1, 'x2': 0, '__a0': 0, '__a1': 0, '__a2': 0} is invalid
    	 {'x1': 1, 'x0': 0, 'x3': 1, 'x2': 1, '__a0': 0, '__a1': 0, '__a2': 0} is valid
    
    lam 2
    	 {'x1': 1, 'x0': 0, 'x3': 1, 'x2': 1, '__a0': 0, '__a1': 0, '__a2': 0} is valid
    
    lam 3
    	 {'x1': 1, 'x0': 0, 'x3': 1, 'x2': 1, '__a0': 0, '__a1': 0, '__a2': 0} is valid
    


We see that $\lambda = 2$ is sufficient to enforce the constraints. So let's update our QUBO.


```python
Q_good = Q.subs({lam: 2})
```

Now let's solve the QUBO with D'Wave's simulated annealer.


```python
#!pip install dwave-neal
from neal import SimulatedAnnealingSampler

sampler = SimulatedAnnealingSampler()
```

Note that their software package takes in a specific form for QUBOs, namely, the keys of the dictionary must be two element tuples. This form can be accessed from `Q` and `Q_good` with `Q.Q` or `Q_good.Q`.


```python
qubo_sample = sampler.sample_qubo(Q_good.Q, num_reads=100)
print("objective function:", qubo_sample.first.energy + Q_good.offset, "\n")

qubo_solution = qubo_sample.first.sample
print("qubo solution:", qubo_solution, "\n")

solution = C.convert_solution(qubo_solution)
print("pcbo solution:", solution)
print("objective function:", C.value(solution), "\n")

print("The solution is", "valid" if C.is_solution_valid(solution) else "invalid")
```

    objective function: -1.0 
    
    qubo solution: {0: 1, 1: 0, 2: 1, 3: 1, 4: 0, 5: 0, 6: 0, 7: 1, 8: 0} 
    
    pcbo solution: {'x1': 1, 'x0': 0, 'x3': 1, 'x2': 1, '__a0': 0, '__a1': 0, '__a2': 0}
    objective function: -1 
    
    The solution is valid


This matches the result of `C.solve_bruteforce()`. Now we'll solve an QUSO formulation of our problem. Again we'll take $\lambda = 2$.


```python
L = C.to_quso().subs({lam: 2})
# note that we cannot do C.subs({lam: 2}).to_quso()!! This is because C.subs({lam: 2})
# creates a new PCBO object, and it's mapping from variables labels to integers may be
# different than C's mapping. For example, try C.mapping == C.subs({lam: 2}).mapping a
# few times. They will often be different.
print("num PUBO variables", C.num_binary_variables)
print("num QUSO variables", L.num_binary_variables)
print()
print(L)
```

    num PUBO variables 7
    num QUSO variables 9
    
    {(0, 1): 7.0, (0,): -3.75, (1,): -11.5, (): 45.0, (7,): -4.75, (0, 2): 8.75, (2,): -13.25, (0, 7): -3.5, (2, 7): -3.5, (3, 7): 0.25, (3,): -1.25, (1, 2): 11.0, (1, 7): 1.0, (1, 4): 3.0, (1, 5): 6.0, (1, 6): 12.0, (6,): -16.0, (0, 4): 2.0, (0, 5): 4.0, (0, 6): 8.0, (2, 4): 4.0, (2, 5): 8.0, (2, 6): 16.0, (4, 5): 2.0, (4, 6): 4.0, (4,): -4.0, (5, 6): 8.0, (5,): -8.0, (8,): -3.5, (0, 8): -2.5, (1, 8): -2.5, (3, 8): 1.0, (2, 3): -1.0}


Similar to their QUBO solver, D'Wave's QUSO solver accepts a specific form for QUSO models, namely a linear term dictionary and a quadratic term dictionary. These can be accessed with `L.h` and `L.J`.


```python
quso_sample = sampler.sample_ising(L.h, L.J, num_reads=100)
print("objective function:", quso_sample.first.energy + L.offset, "\n")

quso_solution = quso_sample.first.sample
print("quso solution:", quso_solution, "\n")

solution = C.convert_solution(quso_solution)
print("pcbo solution:", solution)
print("objective function:", C.value(solution), "\n")

print("The solution is", "valid" if C.is_solution_valid(solution) else "invalid")
```

    objective function: -1.0 
    
    quso solution: {0: -1, 1: 1, 2: -1, 3: -1, 4: 1, 5: 1, 6: 1, 7: -1, 8: 1} 
    
    pcbo solution: {'x1': 1, 'x0': 0, 'x3': 1, 'x2': 1, '__a0': 0, '__a1': 0, '__a2': 0}
    objective function: -1 
    
    The solution is valid


Again this matches the result of `C.solve_bruteforce()`.

Much of the functionality from above can also be done with Polynomial Constrained Spin Optimization (PCSO). See ``help(qubovert.PCSO)`` and ``help(qubovert.spin_var)``.

e999124ada6487734a5cb3525b955e4f8e1f70d8
ipynb
Jupyter Notebook
notebook_examples/PCBO_example.ipynb
panaali/qubovert
d5ea46349d2a058954fb2cb06f559c0d3fb382c5
Apache-2.0
2020-07-10T20:46:50.000Z
2021-12-29T05:01:55.000Z
notebook_examples/PCBO_example.ipynb
panaali/qubovert
d5ea46349d2a058954fb2cb06f559c0d3fb382c5
Apache-2.0
2020-02-07T00:10:31.000Z
2020-04-05T22:58:55.000Z
notebook_examples/PCBO_example.ipynb
panaali/qubovert
d5ea46349d2a058954fb2cb06f559c0d3fb382c5
Apache-2.0
2020-05-13T06:02:38.000Z
2022-03-22T20:45:23.000Z
Qwen/Qwen-72B
1. YES
2. YES