<jupyter_start><jupyter_text>Polynomial Unconstrained Boolean Optimization Problem in MBQC Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved.  In the tutorial [Measurement-based Quantum Approximate Optimization Algorithm](QAOA_EN.ipynb), we give a brief introduction to the **polynomial unconstrained boolean optimization (PUBO) problem** and propose the **measurement-based quantum approximate optimization algorithm (MB-QAOA)** to solve it. For interested readers, please refer to the previous tutorial for more information. In this tutorial, we will showcase two specific examples as practical demonstrations of MB-QAOA. The first one is a concrete PUBO problem, while the second one is a **maximum cut (MaxCut)** problem. Example: PUBO ProblemLet us first briefly review what a PUBO problem is. Consider a polynomial of $n$ variables $x = \{x_1,\cdots,x_n\}$, $$C(x) = \sum_{\lambda \in \Lambda } \alpha_{\lambda} \prod_{j \in \lambda} x_j,\tag{1}$$where $x_i \in \{0,1\}$ is a boolean variable, $\underset{j \in \lambda}{\prod} x_j$ is a monomial, $\lambda \subseteq [n]:= \{1, 2, ..., n\}$ is a set of indexes, $\Lambda$ is the set of index sets, $\alpha_\lambda$ is the real coefficient of monomial. In PUBO, $C(x)$ is called the objective polynomial. We hope to find an optimal solution $x^* = \{x_1^*, x_2^*, ..., x_n^*\} $ maximizing the value of objective polynomial. That is to find$$x^* = \underset{x}{\text{argmax}} \ C(x).\tag{2}$$For code implementation, we require that a standard polynomial is input as a list whose first item is the number of variables and the second item is a dictionary of all the monomials ('cons' stands for the constant item). In the dictionary, we make monomial variables split with ',' as keys and the corresponding coefficients as values. For example, suppose we want to input a polynomial $x_1 + x_2 - x_3 + x_1 x_2 - x_1 x_2 x_3 + 0.5$, we need to code as follows:<jupyter_code># Number of variables
var_num = 3
# Polynomial as a dictionary
poly_dict = {'x_1': 1, 'x_2': 1, 'x_3': -1, 'x_1,x_2': 1, 'x_1,x_2,x_3': -1, 'cons':0.5}
# Construct the list required
polynomial = [var_num, poly_dict]<jupyter_output><empty_output><jupyter_text>**Note:** As the variables are boolean, the power of variables in a monomial should be no greater than 1. That is, each variable should appear at most once in a key of the dictionary. For instance, it is not a valid to input something like {'x_1,x_1,x_2': 1}. Also, we set variable subscripts by consecutive numbers starting from '1' to be consistent with math conventions. A polynomial like $x_1 x_2 + x_6$ will raise an error automatically. A valid polynomial should be like $x_1x_2 + x_3$.   For convenience, we provide a function `is_poly_valid` in `pubo` to check the validity of the user's input. If the polynomial is valid, it will print a statement "The polynomial is valid.". Otherwise, an error will be raised.```pythonfrom paddle_quantum.mbqc.QAOA.pubo import is_poly_valid```We also provide a function `random_poly` to generate a random boolean polynomial with a given number of variables.```pythonfrom paddle_quantum.mbqc.QAOA.pubo import random_poly```**Note:** The randomly generated polynomial is not always valid and we still need to check the validity before calculation.  Code implementation to slove PUBO problem<jupyter_code># Import time module
from time import perf_counter
# Import sympy module for syntax calculation
from sympy import symbols
# Import paddle module
from paddle import seed, optimizer
# Import pubo module
from paddle_quantum.mbqc.QAOA.pubo import dict_to_symbol,is_poly_valid,brute_force_search
# Import qaoa module
from paddle_quantum.mbqc.QAOA.qaoa import MBQC_QAOA_Net, get_solution_string<jupyter_output><empty_output><jupyter_text>We define a function ``mbqc_pubo`` which takes in the objective polynomial and returns an optimal solution. **The core part of ``mbqc_pubo`` is the ``MBQC_QAOA_Net`` class**, which integrates MB-QAOA and the optimization net. Please refer to [Measurement-Based Quantum Approximate Optimization Algorithm](QAOA_EN.ipynb) for more details. Here we directly call the function.<jupyter_code># Define the PUBO main function
def mbqc_pubo(OBJ_POLY, DEPTH, SEED, LR, ITR, EPOCH, SHOTS=1024):
    
    # Symbolize the polynomial
    obj_poly = dict_to_symbol(OBJ_POLY)
    var_num, poly_symbol = obj_poly

    # Print the QAOA depth
    print("QAOA depth is:", DEPTH)

    #  Start timing
    start_time = perf_counter()

    # Instaniate a MB-QAOA traning net
    seed(SEED)
    mbqc_net = MBQC_QAOA_Net(DEPTH)
    
    # Choose Adams optimizer (or SGD optimizer)
    opt = optimizer.Adam(learning_rate=LR, parameters=mbqc_net.parameters())

    # Start training
    for epoch in range(EPOCH):
        # Update parameters for each iter
        for itr in range(1, ITR + 1):
            # Train with mbqc_net and return the loss
            loss, state_out = mbqc_net(poly=obj_poly)
            # Propagate loss backwards and optimize the parameters
            loss.backward()
            opt.minimize(loss)
            opt.clear_grad()
            if itr % 10 == 0:
                print("iter:", itr, "  loss_MBQC:", "%.4f" % loss.numpy())
                
    # Stop timing and print the running time
    end_time = perf_counter()
    print("MBQC running time is: ", end_time - start_time)

    # Print the optimization parameters
    print("Optimal parameter gamma: ", mbqc_net.gamma.numpy())
    print("Optimal parameter beta: ", mbqc_net.beta.numpy())

    # Decode the solution from the quantum state
    solution_str = get_solution_string(state_out, SHOTS)

    # Evaluate the corresponding value
    relation = {symbols('x_' + str(j + 1)): int(solution_str[j]) for j in range(var_num)}
    value = poly_symbol.evalf(subs=relation)
    
    # Return the solution and its corresponding value
    opt = [solution_str, value]

    return opt<jupyter_output><empty_output><jupyter_text>To check the correctness of the training result, we provide a `brute_force_search` function in `pubo` that finds a global optimal value by brute force search. We can compare the training result with the optimal one.```pythonfrom paddle_quantum.mbqc.QAOA.pubo import brute_force_search```  Main functionAfter defining the main function, let's input the parameters to run the code!<jupyter_code># Define the main function
def main():
    
    # Choose the example x_1 + x_2 - x_3 + x_1*x_2 -x_1*x_2*x_3 + 0.5
    var_num = 3  
    poly_dict = {'x_1': 1, 'x_2': 1, 'x_3': -1, 'x_1,x_2': 1, 'x_1,x_2,x_3': -1, 'cons':0.5}
    polynomial = [var_num, poly_dict]
    
    # Print the input polynomial
    print("The input polynomial is: ", polynomial)
    
    # We can also randomly generate an objective function
    # polynomial = random_poly(var_num)

    # Check the validity of the input polynomial
    is_poly_valid(polynomial)

    # Starting training and obtain the result
    mbqc_result = mbqc_pubo(
        OBJ_POLY=polynomial,  # Objective Function
        DEPTH=6,  # QAOA Depth
        SEED=1024,  # Plant Seed
        LR=0.1,  # Learning Rate
        ITR=120,  # Training Iters
        EPOCH=1  # Epoch Times
    )

    # Print the result from MBQC model
    print("Optimal solution by MBQC: ", mbqc_result[0])
    print("Optimal value by MBQC: ", mbqc_result[1])
    
    # Compute the optimal result by brute-force search and print the result
    brute_result = brute_force_search(polynomial)
    print("Optimal solution by brute force search: ", brute_result[0])
    print("Optimal value by brute force search: ", brute_result[1])
    
    # Compare the training result with the optimal one
    print("Difference between optimal values from MBQC and brute force search: ", mbqc_result[1] - brute_result[1])


if __name__ == '__main__':
    main()<jupyter_output><empty_output><jupyter_text>Example: MaxCut Graph and cutMaximum cut problem（MaxCut Problem）is a combinatorial optimization problem in graph theory, with plenty of applications in e.g. statistic physics and circuit design.In graph theory, a graph is represented by $G = (V, E)$, where $V$ is a set of vertices and $E$ is a set of edges. For example, a square can be characterized by the graph $G = (V,E)$ with $V = [1,2,3,4]$ and $E = [(1,2),(2,3),(3,4),(1,4)]$.For code implementation, we can use the `plot_graph` function in `maxcut` to plot a graph.<jupyter_code>from paddle_quantum.mbqc.QAOA.maxcut import plot_graph
V = [1,2,3,4]
E = [(1,2),(2,3),(3,4),(1,4)]
G = [V, E] 
plot_graph(G,"A square")<jupyter_output><empty_output><jupyter_text>A cut in the graph is a partition separating the vertices set $V$ into two complementary subsets $S_0$ and $S_1$. If two vertices of an edge in the graph are separated into different subsets, we score a goal. The size of a cut is defined by the total scores that we get. Then the MaxCut problem is to find a cut of graph with maximal size.  As for the above square $G$, one of the optimal solutions to the MaxCut problem is to put $1$ and $3$ into subset $S_0$ and put $2$ and $4$ into subset $S_1$.   Transformation to a PUBO problemA MaxCut problem can be transformed into a PUBO problem. Assume the graph to be cut $G = (V, E)$ has $n=|V|$ vertices and $m =|E|$ edges, we can transform the MaxCut problem into a PUBO problem of $n$ variables. Each variable $x_v$ corresponds to a vertex $v \in V$ in the graph $G$, with its domain $x_v \in \{0,1\}$ corresponding to its belonging to subset $S_0$ or subset $S_1$. So, each value of the string $x = \{x_1,\cdots,x_n\}$ corresponds to a cut. As a valid edge to score a goal is the one whose vertices $u$ and $v$ belong to different subsets, given a cut $x$, its size can be defined as:  $$C(x) = \sum_{(u,v) \in E} (x_u \oplus x_v),\tag{3}$$where $\oplus$ represents XOR operation. Then the MaxCut problem is equivalent to solve the optimization $\underset{x}{\max} \ C(x)$. Since $C(x)$ can be written as a polynomial: $$C(x) = \sum_{(u, v) \in E} (x_u + x_v - 2 x_u x_v).\tag{4}$$this optimization is essentially a quadratic PUBO problem of $n$ variables. We hope to find an optimal solution $x^{*}$ maximizing the value of objective polynomial, that is,$$x^* = \underset{x}{\text{argmax}} \left( \sum_{(u, v) \in E} (x_u + x_v - 2 x_u x_v) \right).\tag{5}$$We provide a function `graph_to_poly` in `maxcut` which takes in the graph to be cut and returns the equivalent objective polynomial in PUBO.<jupyter_code># Import maxcut module
from paddle_quantum.mbqc.QAOA.maxcut import graph_to_poly

# Input the vertices and edges
V = [1,2,3,4]
E = [(1,2),(2,3),(3,4),(1,4)]
# Construct the graph to be cut
G = [V, E] 

# Transform the graph to the equivalent polynomial
poly = graph_to_poly(G)
print("The equivalent objective polynomial is：\n", poly)<jupyter_output><empty_output><jupyter_text>Code implementation to solve MaxCut problemOnce obtaining the objective polynomial, we can follow the same process as the previous example and solve the MaxCut problem as a special case of PUBO. The complete code implementation is as follows:<jupyter_code># Import symbol calculaion module
from sympy import symbols
# Import paddle module
from paddle import seed, optimizer
# Import qaoa module
from paddle_quantum.mbqc.QAOA.qaoa import MBQC_QAOA_Net, get_solution_string
# Import maxcut module
from paddle_quantum.mbqc.QAOA.maxcut import plot_graph, graph_to_poly, plot_solution<jupyter_output><empty_output><jupyter_text>We define the main function for MaxCut that takes in the graph to be cut and returns the optimal training results.<jupyter_code># Define the MaxCut main function
def mbqc_maxcut(GRAPH, DEPTH, SEED, LR, ITR, EPOCH, SHOTS=1024):
    
    # Plot the graph to be cut
    plot_graph(graph=GRAPH, title="Graph to be cut")

    # Obtain the objective polynomial
    polynomial = graph_to_poly(GRAPH)
    print("Corresponding objective polynomial of the graph is:", polynomial[1])

    # Start timing
    start_time = perf_counter()
    
    # Instantiate a MB-QAOA training net
    seed(SEED)
    mbqc_net = MBQC_QAOA_Net(DEPTH)
    
    # Choose Adams optimizer (or SGD optimizer)
    opt = optimizer.Adam(learning_rate=LR, parameters=mbqc_net.parameters())

    # Start training
    for epoch in range(EPOCH):
        # Update parameters for each iter
        for itr in range(1, ITR + 1):
            # Train with mbqc_net and return the loss
            loss, state_out = mbqc_net(poly=polynomial)
            # Propagate loss backwards and optimize the parameters
            loss.backward()
            opt.minimize(loss)
            opt.clear_grad()
            if itr % 10 == 0:
                print("iter:", itr, "  loss_MBQC:", "%.4f" % loss.numpy())

    # Stop timing and print the running time
    end_time = perf_counter()
    print("MBQC running time: ", end_time - start_time)
    
    # Print the optimized parameters
    print("Optimal parameter gamma: ", mbqc_net.gamma.numpy())
    print("Optimal parameter beta: ", mbqc_net.beta.numpy())

    # Decode the MaxCut solution from the final state
    mbqc_solution = get_solution_string(state_out, SHOTS)
    # Plot the MaxCut solution
    plot_solution(GRAPH, mbqc_solution)

    # Evaluate the number of cuts
    var_num, poly_symbol = polynomial
    relation = {symbols('x_' + str(j + 1)): int(mbqc_solution[j]) for j in range(var_num)}
    
    mbqc_value = int(poly_symbol.evalf(subs=relation))
    mbqc_opt = [mbqc_solution, mbqc_value]

    return mbqc_opt<jupyter_output><empty_output><jupyter_text>Main functionAfter defining the main function, let's input the parameters to run the code!<jupyter_code>def main():
    #  A graph to be cut
    V = [1, 2, 3, 4]
    E = [(1, 2), (2, 3), (3, 4), (4, 1)]
    G = [V, E]
    
    # MaxCut under MBQC
    mbqc_result = mbqc_maxcut(
        GRAPH=G,  # Graph to be cut
        DEPTH=6,  # Depth
        SEED=1024,  # Plant Seed
        LR=0.1,  # Learning Rate
        ITR=120,  # Training Iters
        EPOCH=1,  # Epoch Times
        SHOTS=1024  # Shots for decoding the solution
    )

    # Print the result from MBQC model
    print("Optimal solution by MBQC: ", mbqc_result[0])
    print("Optimal value by MBQC: ", mbqc_result[1])

if __name__ == '__main__':
    main()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09678548917991456, 'fraction_numerical': 0.014006583094054205, 'mean_word_length': 3.86541737649063, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '590462', 'license': 'Apache-2.0', 'n_tokens_mistral': 4728, 'n_tokens_neox': 4374, 'n_words': 1713, 'path': 'tutorial/mbqc/PUBO_EN.ipynb', 'repo_name': 'imppresser/Quantum-1', 'size': '14279'}