# US 2025/0094523 A1 · Benchmarking qubo solvers using generated problems with known solutions

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0094523 A1
- Document ID: US20250094523A1
- Status: Published application
- Kind: A1
- Application number: 18/466,915
- Filed: 2023-09-14
- Published: 2025-03-20
- Earliest claimed: 2023-09-14
- Assignees: Dell Products L.P.
- Applicants: Dell Products L.P.
- Inventors: Miguel Paredes Quiñones; Brendan Burns Healy
- Web page: https://patentgrep.com/patent/US20250094523A1

## CPC

- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

One example method includes creating a random matrix Q that defines a quadratic unconstrained binary optimization problem (QUBO) that has a known, optimal, solution, transmitting the random matrix Q to each solver in a group that includes multiple solvers, obtaining, from each of the solvers, a respective solution to the QUBO problem, benchmarking the solvers by comparing each of the solutions to the known, optimal solution and, based on the comparing, identifying a best solver from among the solvers in the group.

## Claims

### Claim 1

A method, comprising:
creating a random matrix Q that defines a benchmark quadratic unconstrained binary optimization problem (QUBO) that has a known, optimal, solution;
transmitting the random matrix Q to each solver in a group that includes multiple solvers;
obtaining, from each of the solvers, a respective solution to the benchmark QUBO problem;
benchmarking the solvers by comparing each of the solutions to the known, optimal solution; and
based on the comparing, identifying a best solver from among the solvers in the group.

### Claim 2 (depends on 1)

The method as recited in claim 1, wherein one or more of the solvers comprises a respective annealer.

### Claim 3 (depends on 1)

The method as recited in claim 1, wherein the identified solver is used to solve another QUBO problem.

### Claim 4 (depends on 1)

The method as recited in claim 1, wherein the random matrix Q has a size N×N, and the known, optimal solution comprises a random binary vector x* of size N.

### Claim 5 (depends on 1)

The method as recited in claim 1, wherein a smallest eigenvalue of the matrix Q is equal to a global minima of the Rayleigh quotient.

### Claim 6 (depends on 1)

The method as recited in claim 1, wherein creating the random matrix Q comprises:
creating a random binary vector x{circumflex over ( )}* of size N as the known, optimal solution;
calculating a null space matrix P of the random binary vector x*;
randomly generating a vector λ of real values with size N in a defined interval, where the real values comprise respective eigenvalues, ordering the entries λ by size, and creating a diagonal matrix Λ=diag(λ);
creating a matrix D with vector x*/x*T x* in a first row of the matrix D, and other null space columns in the matrix D from the null space matrix P, where the matrix D has the form:
D
=
[
x
*
T
/
x
*
T
⁢
x
*
P
T
]
;
defining a final QUBO matrix Q=DTΛD/x*T x*, then using an equivalence of a minimization of the Rayleigh quotient to calculate emin as follows,
e
min
=
λ
1
/
x
*
T
⁢
x
*
=
min
x
⁢
x
T
⁢
Qx
;
wherein emin is calculated using known values λ1 and x*T to generate the known optimal solution, and the known optimal solution comprises a solution pair (emin, x*T).

### Claim 7 (depends on 6)

The method as recited in claim 6, wherein calculating the null space matrix P is performed using Gauss-Jordan elimination.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein the best solver is the solver whose solution is closest, relative to the respective solutions of the other solvers in the group, to the known, optimal, solution.

### Claim 9

A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
creating a random matrix Q that defines a benchmark quadratic unconstrained binary optimization problem (QUBO) that has a known, optimal, solution;
transmitting the random matrix Q to each solver in a group that includes multiple solvers;
obtaining, from each of the solvers, a respective solution to the benchmark QUBO problem;
benchmarking the solvers by comparing each of the solutions to the known, optimal solution; and
based on the comparing, identifying a best solver from among the solvers in the group.

### Claim 10 (depends on 9)

The non-transitory storage medium as recited in claim 9, wherein one or more of the solvers comprises a respective annealer.

### Claim 11 (depends on 9)

The non-transitory storage medium as recited in claim 9, wherein the identified solver is used to solve another QUBO problem.

### Claim 12 (depends on 9)

The non-transitory storage medium as recited in claim 9, wherein the random matrix Q has a size N×N, and the known, optimal solution comprises a random binary vector x* of size N.

### Claim 13 (depends on 9)

The non-transitory storage medium as recited in claim 9, wherein a smallest eigenvalue of the matrix Q is equal to a global minima of the Rayleigh quotient.

### Claim 14 (depends on 9)

The non-transitory storage medium as recited in claim 9, wherein creating the random matrix Q comprises:
creating a random binary vector x{circumflex over ( )}* of size N as the known, optimal solution;
calculating a null space matrix P of the random binary vector x*;
randomly generating a vector λ of real values with size N in a defined interval, where the real values comprise respective eigenvalues, ordering the entries λ by size, and creating a diagonal matrix Λ=diag(λ);
creating a matrix D with vector x*/x*T x* in a first row of the matrix D, and other null space columns in the matrix D from the null space matrix P, where the matrix D has the form:
D
=
[
x
*
T
/
x
*
T
⁢
x
*
P
T
]
;
defining a final QUBO matrix Q=DTΛD/x*T x*, then using an equivalence of a minimization of the Rayleigh quotient to calculate emin as follows,
e
min
=
λ
1
/
x
*
T
⁢
x
*
=
min
x
⁢
x
T
⁢
Qx
;
and
wherein emin is calculated using known values λ1 and x*T to generate the known optimal solution, and the known optimal solution comprises a solution pair (emin, x*T).

### Claim 15 (depends on 14)

The non-transitory storage medium as recited in claim 14, wherein calculating the null space matrix P is performed using Gauss-Jordan elimination.

### Claim 16 (depends on 9)

The non-transitory storage medium as recited in claim 9, wherein the best solver is the solver whose solution is closest, relative to the respective solutions of the other solvers in the group, to the known, optimal, solution.
