Quantum Computing Method for Solving Combinatorial Optimization Problems

Simple SummaryContent extracted from patent full text and abstract with AI.

This invention provides a quantum computing method designed to solve combinatorial optimization problems that involve many discrete variables. The method represents the problem as a graph, splits the graph into smaller subgraphs, solves each subproblem using quantum algorithms (like QAOA), and then intelligently recombines the results to approximate the best overall solution. By breaking down the problem, it adapts current quantum computers with limited qubit numbers to handle much larger and more complex problems than previously possible.

Use CasesContent extracted from patent full text and abstract with AI.

• Optimizing logistics and supply chain networks (e.g., route planning, scheduling)
• Finding solutions to classic NP-hard problems, such as the traveling salesman or max-cut problems
• Industrial resource allocation and job scheduling in manufacturing plants
• Complex scheduling for airline crew and vehicle fleets
• Network design and partitioning in telecommunications and data centers
• Financial portfolio optimization involving large numbers of variables

BenefitsContent extracted from patent full text and abstract with AI.

• Allows large combinatorial optimization problems to be tackled by quantum computers with limited qubit counts
• Reduces hardware requirements, making commercial quantum optimization more viable sooner
• Leverages hybrid classical-quantum workflows for increased flexibility and compatibility with current quantum devices
• Enables industry-relevant problem sizes to be handled before fully error-corrected, large-scale quantum computers become available
• Improves solution accuracy by recombining results from subproblems in a sophisticated way, rather than treating them as fully independent
• Adapts well to problems naturally represented as graphs, tapping into established graph partitioning techniques

Technical Classifications (CPCs)

Inventors & Applicants

Patent Abstract

Provided is a quantum computing method for obtaining an optimal solution of a problem with multiple discrete variables, wherein the problem is represented by a cost function, the method comprising: - generating a graph structure from the cost function, - dividing the graph structure into at least two disjunct subgraph structures, wherein each subgraph structure comprises a subset of the multiple variables, - mapping each subgraph structure to a local cost function represented as local cost Hamiltonian, - determining, for each local cost Hamiltonian, all eigenstates corresponding to an energy below a predetermined cut off energy using a quantum processing device, wherein each variable of the subset of multiple variables is represented by a qubit of the quantum processing device, - recombining the determined eigenstates, and - approximating a ground state from the recombined eigenstates, wherein the ground state represents the optimal solution.