Interpolation between log and one-hot encodings
Encoding problems to be executed on quantum computing systems. A scaled log encoding is performed by dividing a variable of the problem into pieces. Each piece is log encoded and then submitted for execution. This reduces the coefficient size of the encodings compared to strict log encoding while increasing the number of variables.
1 . A method comprising:
receiving a problem from a client at an orchestration engine;
dividing a variable associated with the problem into a number of pieces; and
performing scaled encoding on each of the pieces to generate scaled encodings, wherein the scaled encodings comprise an interpolation between log encoding and unary encoding; and
combining the encoded pieces into a final encoding.
2 . The method of claim 1 , wherein the problem comprises a quadratic unconstrained binary optimization model.
3 . The method of claim 2 , wherein the variable comprises an integer variable having a range.
4 . The method of claim 2 , wherein scaled encoding comprises performing log encoding on each of the pieces.
5 . The method of claim 2 , further comprising determining whether to perform the scaled encoding based on a cutoff value.
6 . The method of claim 5 , wherein the scaled log encoding ensures that coefficients in the scaled log encodings are less than the cutoff value.
7 . The method of claim 6 , wherein the number of pieces is based on a range of the variable.
8 . The method of claim 5 , wherein the cutoff value is based on weights of constraints and/or coefficients of the constraints.
9 . The method of claim 1 , wherein the problem comprises an Ising model or a HOBO model.
10 . A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
receiving a problem from a client at an orchestration engine;
dividing a variable associated with the problem into a number of pieces; and
performing scaled encoding on each of the pieces to generate scaled encodings, wherein the scaled encodings comprise an interpolation between log encoding and unary encoding; and
combining the encoded pieces into a final encoding.
11 . The non-transitory storage medium of claim 10 , wherein the problem comprises an Ising model or a HOBO model.
12 . The non-transitory storage medium of claim 10 , wherein the problem comprises a quadratic unconstrained binary optimization model.
13 . The non-transitory storage medium of claim 12 , wherein the variable comprises an integer variable having a range.
14 . The non-transitory storage medium of claim 12 , wherein scaled encoding comprises performing log encoding on each of the pieces.
15 . The non-transitory storage medium of claim 12 , further comprising determining whether to perform the scaled encoding based on a cutoff value.
16 . The non-transitory storage medium of claim 15 , wherein the scaled log encoding ensures that coefficients in the scaled log encodings are less than the cutoff value.
17 . The non-transitory storage medium of claim 16 , wherein the number of pieces is based on a range of the variable.
18 . The non-transitory storage medium of claim 15 , wherein the cutoff value is based on weights of constraints and/or coefficients of the constraints.
19 . A method for encoding an integer variable in a quadratic unconstrained binary optimization (QUBO) problem, the method comprising:
receiving an integer variable having a predefined range;
determining a coefficient cutoff value for the QUBO;
decomposing the integer variable into a plurality of integer sub-variables, each sub-variable having a reduced range selected such that logarithmic encoding of the sub-variable produces coefficients that do not exceed the cutoff value;
encoding each sub-variable using logarithmic binary encoding; and
combining the encoded sub-variables to represent the integer variable in the QUBO, wherein the encoding of the integer variable uses more binary variables than a single logarithmic encoding of the integer variable and fewer binary variables than a unary encoding of the integer variable, wherein the encoding is an interpolation of logarithmic and unary encodings.