Speaker
Description
Quantum computers in the NISQ era (noisy, intermediate-scale, quantum) still offer a relatively small amount of qubits. The largest quantum computers so far, dedicated to binary optimization, do not surpass a few thousands qubits. We nevertheless are willing and able to probe such computers in real-life tasks with their high demand in number of variables to optimize over.
We tackle a binary optimization problem and discuss the problems around its conversion to a QUBO (quadratic unconstrained binary optimization), which is the kind of problem treated by quantum annealers such as the D-Wave quantum computers. Among these problems are the use of penalties and, importantly, quadratization (reduction of higher-order polynomials to binary ones) that typically requires (scarcely available) extra variables. Different encodings of the same problem are discussed, and, surprisingly, encoding the original problem's variables as densely as possible into fewer binary variables becomes counterproductive after a certain degree in the context of QUBO optimization. We show how this result comes about in the context of different forms of quadratization and discuss their advantages and disadvantages for use in a quantum computer.