[Intel] Revision of QUBO benchmark

[jasonlyik]

@phstratmann Thanks! I have made small modifications to the text to render the math correctly.

[jasonlyik]

I noticed that the term "cost" or "solver cost" is used often throughout the document but it isn't clearly formalized, could we add in a definition for this term?

[phstratmann]

I noticed that the term "cost" or "solver cost" is used often throughout the document but it isn't clearly formalized, could we add in a definition for this term?

Alessandro and I just added a description of the QUBO workload and the definition of cost. Thanks for noticing the issue.

[jasonlyik]

Thanks Philipp, I have a couple further questions:

• In the formula [ $\min_{\mathbf{x}\in{0,1}^n} \mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{c}^T\mathbf{x}$ ], what is the definition of the term $\mathbf{c}^T$ ? Is this the correct formula for QUBO?
• How should we determine the penalty factor $\lambda$ for the matrix $\mathbf{Q}$? To keep the benchmark simple, can it be constant across all workloads, or can it scale simply with workload size?

[phstratmann]

The equation was incorrect, I apologize. Also added more information on lambda. It will be constant across workloads. We will provide it.

[jasonlyik]

TODO: The current spec says completely solve/brute-force will be used to solve all graphs under size 1000, but I doubt the possibility to even brute-force for graphs of size 50. 2^50 operations are needed, and a GPU launches 2^10 threads in parallel, meaning it would need 2^40 kernel invocations. I have successfully brute-forced to size 25, which is easy.

A less brute-force way to find a complete solution is to iteratively search over increasing subset sizes, stopping early when an independent set is found and starting the search over subsets of one larger.