Systems and methods for embedding graphs using systolic algorithms

Patent metadata

Field	Value
Publication number	US-12555022-B2
Application number	US-202217832327-A
Country	US
Kind code	B2
Filing date	Jun 3, 2022
Priority date	Jun 8, 2021
Publication date	Feb 17, 2026
Grant date	Feb 17, 2026

Abstract

An accelerated version of a node-weighted path distance algorithm is implemented on a microprocessor coupled to a digital processor. The algorithm calculates an embedding of a source graph into a target graph (e.g., hardware graph of a quantum processor). The digital processor causes the microprocessor to send seeds to logic blocks with a corresponding node in the target graph contained in a working embedding of a node, compute a minimum distance to neighboring logic blocks from each seeded logic block, set the distance to neighboring logic blocks as the minimum distance plus the weight of the seeded logic block, increment the accumulator value by the weight of the seeded logic block, increment the accumulator value by the distance, determine the minimum distance logic block by computing the minimum accumulated value, compute distances to the minimum distance logic block; and read distances from all logic blocks into local memory.

First claim

The invention claimed is:

1 . A method for embedding a source graph S into a target graph T, the source and target graph each having a respective plurality of nodes and weighted edges, the method executed by a digital processor communicatively coupled at least one microprocessor, the at least one microprocessor having one logic block per each node of the target graph, the logic blocks communicatively coupled according to the edges of the target graph, the method comprising, for each neighbor v of a node u of the source graph S, wherein v is mapped to the target graph T via a working embedding E(v) that is non-empty:
causing the microprocessor to send seeds to logic blocks with a corresponding node in the target graph contained in E(v); causing the microprocessor to compute a respective minimum distance N to neighboring logic blocks from each seeded logic block; causing the microprocessor to set, for each seeded logic block, a respective distance D to neighboring logic blocks as the respective minimum distance N plus a respective weight of the seeded logic block; causing the microprocessor to increment, for each seeded logic block, a respective accumulator value by a respective weight of the seeded logic block; causing the microprocessor to increment, for each seeded logic block, the respective accumulator value by the respective distance D; causing the microprocessor to determine a minimum distance logic block by computing a minimum accumulated value A′ over the respective accumulator values of the seeded logic blocks; causing the microprocessor to compute distances D min , for each logic block, to the minimum distance logic block; and causing the microprocessor to read distances D min from all logic blocks into local memory, wherein causing the microprocessor to compute distances D min includes causing the microprocessor to compute a respective minimum distance N to the minimum distance logic block from each logic block; and causing the microprocessor to set, for each logic block, a respective distance D min to the minimum distance logic block as the respective minimum distance N plus a respective weight of the logic block.

2 . The method of claim 1 , further comprising causing the microprocessor to perform at least one of: sending edge weights to the logic blocks, sending edge masks to the logic blocks, and sending tie-break values to the logic blocks, before causing the microprocessor to send seeds to logic blocks.

3 . The method of claim 2 , further comprising causing the microprocessor to set the respective accumulator value to zero for all logic blocks, after causing the microprocessor to perform at least one of: sending edge weights to the logic blocks, sending edge masks to the logic blocks, and sending tie-break values to the logic blocks.

4 . The method of claim 1 , wherein causing the microprocessor to send seeds to logic blocks with a corresponding node in the target graph contained in E(v), causing the microprocessor to compute a respective minimum distance N to neighboring logic blocks from each seeded logic block, causing the microprocessor to set, for each seeded logic block, a respective distance D to neighboring logic blocks as the respective minimum distance N plus a respective weight of the seeded logic block, causing the microprocessor to increment, for each seeded logic block, a respective accumulator value by a respective weight of the seeded logic block, causing the microprocessor to increment, for each seeded logic block, the respective accumulator value by the respective distance D, causing the microprocessor to determine a minimum distance logic block by computing a minimum accumulated value A′ over the respective accumulator values of the seeded logic blocks, causing the microprocessor to compute distances D min , for each logic block, to the minimum distance logic block, and causing the microprocessor to read distances D min from all logic blocks into local memory include causing a field-programmable gate arrays (FPGA) to send seeds to logic blocks with a corresponding node in the target graph contained in E(v), causing the FPGA to compute a respective minimum distance N to neighboring logic blocks from each seeded logic block, causing the FPGA to set, for each seeded logic block, a respective distance D to neighboring logic blocks as the respective minimum distance N plus a respective weight of the seeded logic block, causing the FPGA to increment, for each seeded logic block, a respective accumulator value by a respective weight of the seeded logic block, causing the FPGA to increment, for each seeded logic block, the respective accumulator value by the respective distance D, causing the FPGA to determine a minimum distance logic block by computing a minimum accumulated value A′ over the respective accumulator values of the seeded logic blocks, causing the FPGA to compute distances D min , for each logic block, to the minimum distance logic block, and causing the FPGA to read distances D min from all logic blocks into local memory.

5 . The method of claim 1 , wherein causing the microprocessor to send seeds to logic blocks with a corresponding node in the target graph contained in E(v), causing the microprocessor to compute a respective minimum distance N to neighboring logic blocks from each seeded logic block, causing the microprocessor to set, for each seeded logic block, a respective distance D to neighboring logic blocks as the respective minimum distance N plus a respective weight of the seeded logic block, causing the microprocessor to increment, for each seeded logic block, a respective accumulator value by a respective weight of the seeded logic block, causing the microprocessor to increment, for each seeded logic block, the respective accumulator value by the respective distance D, causing the microprocessor to determine a minimum distance logic block by computing a minimum accumulated value A′ over the respective accumulator values of the seeded logic blocks, causing the microprocessor to compute distances D min , for each logic block, to the minimum distance logic block, and causing the microprocessor to read distances D min from all logic blocks into local memory include causing an application-specific integrated circuit (ASIC) to send seeds to logic blocks with a corresponding node in the target graph contained in E(v), causing the ASIC to compute a respective minimum distance N to neighboring logic blocks from each seeded logic block, causing the ASIC to set, for each seeded logic block, a respective distance D to neighboring logic blocks as the respective minimum distance N plus a respective weight of the seeded logic block, causing the ASIC to increment, for each seeded logic block, a respective accumulator value by a respective weight of the seeded logic block, causing the ASIC to increment, for each seeded logic block, the respective accumulator value by the respective distance D, causing the ASIC to determine a minimum distance logic block by computing a minimum accumulated value A′ over the respective accumulator values of the seeded logic blocks, causing the ASIC to compute distances D min , for each logic block, to the minimum distance logic block, and causing the ASIC to read distances D min from all logic blocks into local memory.

6 . The method of claim 1 , wherein causing the microprocessor to send seeds to all logic blocks with a corresponding node in the target graph contained in E(v), and causing the microprocessor to compute a respective minimum distance N to neighboring logic blocks include causing the microprocessor to send seeds to all logic blocks with a corresponding node contained in E(v) in a hardware graph of a quantum processor; and causing the microprocessor to compute a respective minimum distance N to neighboring logic bl

Assignees

• D Wave Systems Inc

Inventors

• Boothby Kelly T R
• Spear Peter D
• Ranjbar Mani

Classifications

• G06N10/60 Primary

  Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms · CPC title

• G06N10/80 Primary

  Quantum programming, e.g. interfaces, languages or software-development kits for creating or handling programs capable of running on quantum computers; Platforms for simulating or accessing quantum computers, e.g. cloud-based quantum computing · CPC title