Looking for a QUBO (quadratic unconstrained binary optimization) problem with a known solution

Question

Some quantum computers such as D-Wave claim that a QUBO problem with thousands of variables can be solved. The trouble is that it is very difficult for me to use a classical computer to verify if the global minimum has actually been reached. I mean, the whole point of using a quantum computer is to solve those problems that are too difficult for a classical computer.

So, I am thinking of using a QUBO problem with a known theoretical solution to verify if a quantum computer really works.

The factoring problem can be formulated as $min(P - ab)^2$. For example, $min(15 - ab)^2$ has a solution $a=3,b=5$. When that is sent to the D-Wave quantum computer, it does produce the correct solution. Unfortunately, however, when P is a very large number, it does not work because the computer is not good at solving the problems whose coefficients have a wide range. $a=4x_2^2+2x_1+x_0, b=4x_5^2+2x_4+x_3$ If you expand the expression, you will get a simple polynomial with 6 variables. Image $a$ and $b$ are very large! The D-Wave computers cannot handle them.

Could you please let me know if there are any other very large QUBO problems that have known solutions?

Answer 1

Many of the standard combinatorial optimization problems can be formulated as constraint-satisfaction problems, and then translated into a QUBO. For example, if you have a graph that you want to colour with $c$ colours, you can have $0-1$ variables $x_{ik}$ which you interpret as $1$ if vertex $i$ has colour $k$, $0$ otherwise. The constraints are $\sum_{k=1}^c x_{ik} = 1$ for all $i$, and $x_{ik} + x_{jk} \leq 1$ if $\{i,j\}$ is an edge of the graph. It's easy to construct penalty functions for these constraints.

Now if you want a colouring problem that looks difficult but has a known solution, start by colouring your vertices randomly, and then randomly choose edges so that every edge joins vertices with different colours.

Answer 2

It may be a complete rubbish, but still. Main idea is to generate a random matrix $d \times d$ with a negative submatrix of a pre-defined size $k \times k$ with all other entries positive. Thus, optimal solution is a vector with the first $k$ ones and other zeros. Then, we shuffle rows and, subsequently, columns in the same order.

# d - matrix size
# k - size of the optimal solution
def generate_qubo_matrix(d, k):
    # Top left k-size submatrix is non-positive
    # Other submatrices are non-negative
    # Hence, optimal solution is to pick the first k rows/columns
    A11 = -np.random.rand(k, k)
    A12 = np.random.rand(k, d - k)
    A21 = np.random.rand(d - k, k)
    A22 = np.random.rand(d - k, d - k)
    
    A = np.vstack([
        np.hstack([A11, A12]),
        np.hstack([A21, A22]),
    ])
    x_opt = np.hstack([np.ones(k), np.zeros(d-k)])

    # Shuffle rows and columns in the same way
    inds = np.arange(d)
    np.random.shuffle(inds)
    A = A[:, inds][inds, :]
    x_opt = x_opt[inds]
    
    return A, x_opt

I checked it with a classical solver and it works. However, I am completely unsure about the complexity. Because you can definitely reverse-engineer it if you know that positive and negative entries are separated. Whether such structure gives an advantage to particular optimization algorithms is another question.