Hardware accelerated minor embedding for quantum annealing

Inventors

DUDASH, Andrew • OLSHAN-CANTIN, Gabrielle • PANT, Sarad

Abstract

Methods for configuring a quantum annealer to solve a QUBO problem comprises receiving data representing an initial graph representing an embedding of a QUBO problem into a qubit architecture of the quantum annealer and causing one or more GPU thread blocks to create and store a best local current graph and update the best local current graph. Updating the best current local graph comprises copying the best local current graph, modifying the best local current graph copy to form a candidate local graph, computing an evaluation rating for the candidate local graph, and, in accordance with a determination that one or more replacement criteria are met, replacing the best local current graph with the candidate local graph. An updated best local current graph may be identified in a local results array as the best global graph. The quantum annealer may be configured based on the best local graph.

Core Innovation

A method configures a quantum annealer to solve a quadratic unconstrained binary optimization (QUBO) problem by receiving data representing an initial graph representing an embedding of the QUBO problem into a physical qubit architecture of the quantum annealer. The method initializes one or more graphical processing unit (GPU) thread blocks and, for each thread block, creates and stores a best local current graph whose initial version is based on the received initial graph.

The method updates the best local current graph by copying the best local current graph to form a best local current graph copy, modifying the copy to form a candidate local graph, computing an evaluation rating for the candidate local graph, and determining whether one or more replacement criteria are met based on the evaluation rating for the candidate local graph and an evaluation rating for the best local current graph. When the replacement criteria are met, the method replaces the best local current graph with the candidate local graph.

The method stores one or more updated best local current graphs associated respectively with each of the one or more GPU thread blocks in a local results array. It identifies an updated best local current graph from the local results array as a best global graph and configures the quantum annealer based on the best global graph.

Claims Coverage

The partial content includes three independent claims that collectively cover method, system, and non-transitory computer readable storage medium implementations. Across these claims, the inventive features are the same core sequence of receiving an initial embedding graph, using GPU thread blocks with a per-thread-block best local current graph, generating candidate local graphs via modification of a copy, evaluating candidate local graphs, applying replacement criteria, storing local results, selecting a best global graph, and configuring the quantum annealer based on that best global graph.

The independent claims consistently require GPU-parallel processing of an embedding represented by an initial graph, maintaining best local current graphs updated via candidate generation and evaluation rating, applying replacement criteria to update per-thread-block best graphs, then selecting a best global graph from stored local results to configure the quantum annealer.

Stated Advantages

Documented Applications

No documented applications found