Quadratic unconstrained binary optimization cutting
AssigneeDell Products L.P.
InventorsKenneth Durazzo, Brendan Burns Healy, Miguel Paredes Quiñones
Life of this patent
Estimating the term…
Abstract
Cutting matrix configurations in order to execute complex quantum jobs is disclosed. A combinatorial optimization problem may be received and converted into a matrix configuration that can be executed by a quantum computing system. The matrix configuration is cut into k smaller matrix configurations that can be executed on different quantum computing systems or on the same quantum computing system. The smaller matrix configurations are executed and the solutions of the smaller matrix configurations are combined to generate a solution to the original matrix configuration.
Claims20
A method comprising:
- generating an original Quadratic Unconstrained Binary Optimization (QUBO) matrix configuration of a problem received at an orchestration engine;
- cutting the original QUBO matrix configuration into smaller matrix configurations by executing, at a QUBO cutting engine, a polynomial k-cut algorithm that partitions variables of the QUBO into k subsets based on coefficients of the QUBO matrix and discards coefficients connecting variables belonging to different subsets to generate k smaller QUBO configurations;
- for each of the k smaller QUBO configurations, converting the smaller QUBO configuration to a graph and performing a minor embedding operation that maps the graph to qubit connectivity of a quantum annealer in accordance with hardware-specific qubit coupling constraints;
- executing each of the smaller embedded matrix configurations on at least one quantum computing system;
- and
- combining solutions of the smaller matrix configurations executions at the at least one quantum computing system to generate a solution to the original matrix configuration and of the problem.
A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
- generating an original Quadratic Unconstrained Binary Optimization (QUBO) matrix configuration of a problem received at an orchestration engine;
- cutting the original QUBO matrix configuration into smaller matrix configurations by executing, at a QUBO cutting engine, a polynomial k-cut algorithm that partitions variables of the QUBO into k subsets based on coefficients of the QUBO matrix and discards coefficients connecting variables belonging to different subsets to generate k smaller QUBO configurations;
- for each of the k smaller QUBO configurations, converting the smaller QUBO configuration to a graph and performing a minor embedding operation that maps the graph to qubit connectivity of a quantum annealer in accordance with hardware-specific qubit coupling constraints;
- executing each of the smaller embedded matrix configurations on at least one quantum computing system;
- and
- combining solutions of the smaller matrix configurations executions at the at least one quantum computing system to generate a solution to the original matrix configuration and of the problem.
Dependencies are inferred from the claim text.