Compression method for QUBOs and ISING models
An original problem, which may be represented as a string, for execution in a quantum computing system is classically compressed using classical computing systems. Unique variable names and unique coefficients stored in tables constructed from the original problem are associated with unique identifiers. The problem is then translated to a translated form, such as a translated string, using the tables. The translated string may also be generated after quantizing values in the at least one of the tables. The translated string, whether or not quantized, may be entropy encoded. The final result is a compressed version or string of the original string that can be transmitted and stored in a compressed form. The compressed problem may also be decompressed and submitted for execution in a quantum computing system.
1 . A method comprising:
constructing lookup tables for a problem received at an orchestration engine, wherein the lookup tables include a variable name table that associates each unique variable name with an index value and wherein the lookup tables include a coefficient table that associates each unique coefficient with an index value;
translating the problem to a translated string using identifiers stored in the lookup tables; and
compressing the translated string and the lookup tables into a result string.
2 . The method of claim 1 , wherein translating the problem instance comprises generating the translated string by replacing the variable names with their corresponding index values and replacing the coefficients with their corresponding index values.
3 . The method of claim 2 , further comprising compressing the translated string and the lookup tables into the result string with an entropy compressor.
4 . The method of claim 3 , wherein the result string comprises a binary string.
5 . The method of claim 1 , further comprising quantizing values in one or more of the lookup tables prior to generating the translated string.
6 . The method of claim 5 , further comprising determining an input range of coefficients from a coefficient table included in the lookup tables.
7 . The method of claim 6 , further comprising dividing the input range into non-overlapping bins of varied sizes.
8 . The method of claim 7 , wherein sizes of bins associated with higher magnitude coefficients are smaller than sizes of bins associated with lower magnitude coefficients.
9 . The method of claim 8 , further comprising generating a new coefficient table using a middle value of each bin and reconstructing the translated string by:
mapping index values in the coefficient table to new index values in the new coefficient table; and
joining lists of pairs with the new coefficient index values.
10 . A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
constructing lookup tables for a problem received at an orchestration engine, wherein the lookup tables include a variable name table that associates each unique variable name with an index value and wherein the lookup tables include a coefficient table that associates each unique coefficient with an index value;
translating the problem to a translated string using identifiers stored in the lookup tables; and
compressing the translated string and the lookup tables into a result string.
11 . The non-transitory storage medium of claim 10 , wherein translating the problem instance comprises generating the translated string by replacing the variable names with their corresponding index values and replacing the coefficients with their corresponding index values.
12 . The non-transitory storage medium of claim 11 , further comprising compressing the translated string and the lookup tables into the result string with an entropy compressor.
13 . The non-transitory storage medium of claim 12 , wherein the result string comprises a binary string.
14 . The non-transitory storage medium of claim 10 , further comprising quantizing the translated string.
15 . The non-transitory storage medium of claim 14 , further comprising determining an input range of coefficients from a coefficient table included in the lookup tables.
16 . The non-transitory storage medium of claim 15 , further comprising dividing the input range into non-overlapping bins of varied sizes.
17 . The non-transitory storage medium of claim 16 , wherein sizes of bins associated with higher magnitude coefficients are smaller than sizes of bins associated with lower magnitude coefficients.
18 . The non-transitory storage medium of claim 17 , further comprising generating a new coefficient table using a middle value of each bin and reconstructing the translated string by:
mapping index values in the coefficient table to new index values in the new coefficient table; and
joining lists of pairs with the new coefficient index values.