SYSTEMS AND METHODS FOR EMBEDDING GRAPHS USING SYSTOLIC ALGORITHMS

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.

FIELD

This disclosure generally relates to systems and method for embedding graphs.

BACKGROUND

Mapping Problems to Analog Processors

At least some analog processors (e.g., quantum processors) provide a plurality of analog computation devices (e.g., qubits) which are controllably coupled to each other by couplers. Analog processors may take many forms, such as quantum processors having a number of qubits and associated local bias devices, example embodiments of which are described in, for example, U.S. Pat. Nos. 7,533,068, 8,008,942, 8,195,596, 8,190,548, and 8,421,053. Such quantum processors may operate, for example, via quantum annealing and/or may operate adiabatically. For the sake of convenience, the following disclosure refers generally to “qubits” and “quantum processors”, although those skilled in the art will appreciate that this disclose may be implemented in systems comprising other analog processors.

The types of problems that may be solved by any particular embodiment of a quantum processor, as well as the relative size and complexity of such problems, typically depend on many factors. Two such factors may include the number of qubits in the quantum processor and the connectivity (i.e., the availability of communicative couplings) between the qubits in the quantum processor. Throughout this specification, the term “connectivity” is used to describe the maximum number of possible communicative coupling paths that are physically available (e.g., whether active or not) to communicably couple between individual qubits in a quantum processor without the use of intervening qubits. For example, a qubit with a connectivity of three is capable of directly communicably coupling to up to three other qubits without any intervening qubits. In other words, there are direct communicative coupling paths available to three other qubits, although in any particular application all or less than all of those communicative coupling paths may be employed. In a quantum processor employing coupling devices between qubits, this would mean a qubit having a connectivity of three is selectively communicably coupleable to each of three other qubits via a respective one of three coupling devices or couplers. Typically, the number of qubits in a quantum processor limits the size of problems that may be solved and the connectivity between the qubits in a quantum processor limits the complexity of the problems that may be solved.

Many techniques for using adiabatic quantum computation and/or quantum annealing to solve computational problems involve finding ways to directly map a representation of a problem to the quantum processor itself. For example, in some approaches problems are solved by casting the problem in an intermediate formulation (e.g., as an Ising spin glass problem or as a quadratic unconstrained binary optimization (“QUBO”) problem) which accommodates the number of qubits and/or connectivity constraints in the particular quantum processor and may be mapped directly to the particular quantum processor being employed. Examples of some direct mapping approaches are discussed in greater detail in, for example, US Patent Publication 2008-0052055 and U.S. Pat. No. 8,073,808.

The approach of re-casting a problem in an intermediate formulation and directly mapping the intermediate formulation to the quantum processor can be impractical for some types of problems. For example, a quantum processor with pair-wise interactions between qubits may be well-suited to solving quadratic problems (e.g., QUBO problems), but if the quantum processor lacks higher-order (i.e., more than pairwise) interactions between qubits, then casting a generic computational problem as a QUBO problem may require casting the generic computational problem in a form having only pair-wise interactions between qubits. Higher-order interactions in the original problem may need to be broken down into pair-wise terms in order to be re-cast in QUBO form, which may require significant pre-processing. In some cases, the pre-processing required to re-cast a generic problem in QUBO form and directly map the corresponding QUBO problem to a pairwise-connected quantum processor can be of similar computational complexity to the original problem. Furthermore, breaking down higher-order interactions into pair-wise terms can force multiple qubits to be used to represent the same variable, meaning the scope of problems that can be solved by a particular processor may be reduced.

Such “direct mapping” techniques for interacting with quantum processors limit the type, size, and complexity of problems that can be solved. There is a need in the art for techniques of using quantum processors that are less dependent on the architecture (also referred to herein as the topology) of the processors themselves and enable a broader range of problems to be solved.

Hybrid Computing System Comprising a Quantum Processor

A hybrid computing system can include a digital computer communicatively coupled to an analog computer. In some implementations, the analog computer is a quantum computer and the digital computer is a classical computer.

The digital computer can include a digital processor that can be used to perform classical digital processing tasks described in the present systems and methods. The digital computer can include at least one system memory which can be used to store various sets of computer- or processor-readable instructions, application programs and/or data.

The quantum computer can include a quantum processor that includes programmable elements such as qubits, couplers, and other devices. The qubits can be read out via a readout system, and the results communicated to the digital computer. The qubits and the couplers can be controlled by a qubit control system and a coupler control system, respectively. In some implementations, the qubit and the coupler control systems can be used to implement quantum annealing on the analog computer.

BRIEF SUMMARY

A method for embedding a source graph S into a target graph T is described. The source and target graph each have a respective plurality of nodes and weighted edges. The method is executed by a digital processor communicatively coupled at least one microprocessor. The at least one microprocessor has one logic block per each node of the target graph. The logic blocks are communicatively coupled according to the edges of the target graph. The method comprises, 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 Dmin, for each logic block, to the minimum distance logic block; and causing the microprocessor to read distances Dminfrom all logic blocks into local memory.

The method may further comprise 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. The method may further comprise 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. The microprocessor may compute distances Dminby computing a respective minimum distance N to the minimum distance logic block from each logic block and setting, for each logic block, a respective distance Dminto the minimum distance logic block as the respective minimum distance N plus a respective weight of the logic block. The at least one microprocessor may be a field-programmable gate arrays (FPGA) or an application-specific integrated circuit (ASIC). The target graph may be the hardware graph of a quantum processor and the neighboring logic blocks are communicatively coupled according to the edges of the hardware graph of the quantum processor. The method may further comprise the digital processor using distances Dminto determine an embedding of the source graph to the hardware graph of the quantum processor; and programming the quantum processor to embed the source graph into the hardware graph. The microprocessor may use unique tie-break values of each seeded logic block to determine a minimum distance logic block, should more than one logic block have minimum accumulated value A′. The microprocessor may for each seeded logic block: broadcast a ithmost significant bit of the distance D to a first neighbor, wherein i is the most significant bit of D; determine whether all bits of D have been broadcasted; in response to determining that all bits of D have been broadcasted, until all bits of D have been broadcasted, store the ithmost significant bit of the distance D in an array Z; compute the minimum entry of Z; set a value of the minimum distance N to twice the value of the minimum distance N plus the minimum entry of Z; and broadcast a (i+1)thmost significant bit of the distance D to the first neighbor.

A hybrid computing system for embedding a source graph S into a target graph T is described. The source and target graph each have a respective plurality of nodes and weighted edges. The hybrid computing system comprises at least one digital processor, communicatively coupled at least one microprocessor. The at least one microprocessor has one logic block per each node of the target graph and logic blocks are communicatively coupled according to the edges of the target graph. The digital processor is operable to, 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: cause the microprocessor to send seeds to logic blocks with a corresponding node in the target graph contained in E(v); cause the microprocessor to compute a respective minimum distance N to neighboring logic blocks from each seeded logic block; cause 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; cause the microprocessor to increment, for each seeded logic block, a respective accumulator value by a respective weight of the seeded logic block; cause the microprocessor to increment, for each seeded logic block, the respective accumulator value by the respective distance D; cause 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; cause the microprocessor to compute distance Dmin, for each logic block, to the minimum distance logic block; and causing the microprocessor to read distances Dminfrom all logic blocks into local memory. The at least one digital processor may be communicatively coupled to a quantum processor, the quantum processor having a plurality of qubits communicatively coupled according to a hardware graph, wherein the target graph T corresponds to the hardware graph. Neighboring logic blocks may be communicatively coupled according to the edges of the hardware graph of the quantum processor. The at least one digital processor may be further operable to: use distances Dminto determine an embedding of the source graph to the hardware graph; and program the quantum processor to embed the source graph into the hardware graph. The at least one microprocessor is selected from a group consisting of: a programmable gate arrays (FPGA), and an application-specific integrated circuit (ASIC). The digital processor may be further operable to cause 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. The digital processor may be further operable to cause 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. The at least one digital processor may be operable to cause the microprocessor to compute a respective minimum distance N to the minimum distance logic block from each logic block, and cause the microprocessor to set, for each logic block, a respective distance Dminto the minimum distance logic block as the respective minimum distance N plus a respective weight of the seeded logic block. The digital processor may be operable to cause the microprocessor to use unique tie-break values of each seeded logic block to determine a minimum distance logic block, should more than one logic block have minimum accumulated value A′. The digital processor may be operable to, for each seeded logic block: broadcast a ithmost significant bit of the distance D to a first neighbor, wherein i is the most significant bit of D; determine whether all bits of D have been broadcasted; in response to determining that all bits of D have been broadcasted, until all bits of D have been broadcasted, store the ithmost significant bit of the distance D in an array Z; compute the minimum entry of Z; set a value of the minimum distance N to twice the value of the minimum distance N plus the minimum entry of Z; and broadcast an (i+1)thmost significant bit of the distance D to the first neighbor

DETAILED DESCRIPTION

FIG.1illustrates a hybrid computing system100including a classical computer102coupled to a quantum computer104. The example classical computer102includes a digital processor (CPU)106that may be used to perform classical digital processing tasks, and hence is denominated herein and in the claims as a classical processor.

Classical computer102may include at least one digital processor (such as central processor unit106with one or more cores), at least one system memory108, and at least one system bus110that couples various system components, including system memory108to central processor unit106. The digital processor may be any logic processing unit, such as one or more central processing units (“CPUs”), graphics processing units (“GPUs”). Central processor unit106may be communicatively coupled to one or more microprocessor107. Microprocessor107may be one or more digital signal processors (“DSPs”), application-specific integrated circuits (“ASICs”), programmable gate arrays (“FPGAs”), programmable logic controllers (PLCs), etc.

Classical computer102may include a user input/output subsystem112. In some implementations, the user input/output subsystem includes one or more user input/output components such as a display114, mouse116, and/or keyboard118.

System bus110can employ any known bus structures or architectures, including a memory bus with a memory controller, a peripheral bus, and a local bus. System memory108may include non-volatile memory, such as read-only memory (“ROM”), static random-access memory (“SRAM”), Flash NANO; and volatile memory such as random access memory (“RAM”) (not shown).

Classical computer102may also include other non-transitory computer or processor-readable storage media or non-volatile memory120. Non-volatile memory120may take a variety of forms, including: a hard disk drive for reading from and writing to a hard disk, an optical disk drive for reading from and writing to removable optical disks, and/or a magnetic disk drive for reading from and writing to magnetic disks. The optical disk can be a CD-ROM or DVD, while the magnetic disk can be a magnetic floppy disk or diskette. Non-volatile memory120may communicate with the digital processor via system bus110and may include appropriate interfaces or controllers122coupled to system bus110. Non-volatile memory120may serve as long-term storage for processor- or computer-readable instructions, data structures, or other data (sometimes called program modules) for classical computer102.

Although classical computer102has been described as employing hard disks, optical disks and/or magnetic disks, those skilled in the relevant art will appreciate that other types of non-volatile computer-readable media may be employed, such magnetic cassettes, flash memory cards, Flash, ROMs, smart cards, etc. Those skilled in the relevant art will appreciate that some computer architectures employ volatile memory and non-volatile memory. For example, data in volatile memory can be cached to non-volatile memory, or a solid-state disk that employs integrated circuits to provide non-volatile memory.

Various processor- or computer-readable instructions, data structures, or other data can be stored in system memory108. For example, system memory108may store instruction for communicating with remote clients and scheduling use of resources including resources on the classical computer102and quantum computer104. For example, the system memory108may store processor- or computer-readable instructions, data structures, or other data which, when executed by a processor or computer causes the processor(s) or computer(s) to execute one, more or all of the acts of methods400(FIG.4),500(FIG.5) and600(FIG.6).

In some implementations system memory108may store processor- or computer-readable calculation instructions to perform pre-processing, co-processing, and post-processing to quantum computer104. System memory108may store at set of quantum computer interface instructions to interact with quantum computer104.

Quantum computer104may include one or more quantum processors such as quantum processor124. Quantum computer104can be provided in an isolated environment, for example, in an isolated environment that shields the internal elements of the quantum computer from heat, magnetic field, and other external noise (not shown). Quantum processor124include programmable elements such as qubits, couplers and other devices. In accordance with the present disclosure, a quantum processor, such as quantum processor124, may be designed to perform quantum annealing and/or adiabatic quantum computation. Example of quantum processor are described in U.S. Pat. No. 7,533,068.

A quantum processor may comprise a topology including a plurality of qubits and coupling devices providing controllable communicative coupling between qubits (e.g., between respective pairs of qubits). The number of qubits and the connectivity (i.e., the number of available couplings each qubit has to other qubits) in a quantum processor's topology are typically fixed, thereby limiting the scope of problems which may be solved by the processor. As a result, there is a need for techniques that facilitate solving problems of different structures via a quantum processor and/or a hybrid computing system comprising a quantum processor. For example, solving a problem that has more variables than the fixed number of qubits in the quantum processor may entail using the problem decomposition techniques described in U.S. Pat. Nos. 7,870,087 and 8,032,474.

In at least some quantum processor topologies, the available connectivity may not provide couplings between all qubits representing variables and, accordingly, some problem formulations may include variable couplings that are not available in the quantum processor topology. The present systems and methods provide techniques for reformulating at least some problems to be solved via less-than-fully-connected quantum processor.

Throughout this specification, the term hardware graph and specific topology are generally used to refer to the specific fixed architecture or topology of a quantum processor (i.e., the fixed number of qubits and connectivity between qubits in the quantum processor topology). A topology may be represented in a graph where a fixed number of qubits corresponds to or is represented by the nodes of the graph and the fixed connectivity corresponds to or is represented by the edges between the nodes. Examples of quantum processor topologies are described in greater detail in International Patent Application WO2006066415, U.S. Pat. Nos. 9,170,278, 9,178,154 and International Patent Application WO2017214331A1.

A problem to be solved via a quantum computer can have one or more decision variables and one or more constraints that apply to the decision variables. The problem may be formulated in terms of a problem graph to be represented in the hardware graph of a quantum processor, where each decision variable is represented by a node or vertex in the problem graph and each constraint is represented by an edge between nodes or vertices. Throughout this specification and the appended claims the term ‘embedding’ refers to finding a representation of the problem graph in the hardware graph, the term ‘embedded problem’ refers to a representation of the problem graph in the hardware graph, and the term ‘mapping of the problem graph to the hardware graph’ refers to a transformation that assigns a specific node of the problem graph to one or more qubits in the hardware graph.

A person skilled in the art will recognize that the terms ‘node’ and ‘vertex’ can be used interchangeably in a graph. Therefore, for the purpose of this specification and the appended claims, the term ‘node’ can be substituted for ‘vertex’ and ‘vertex’ can be substituted for ‘node’.

When solving a problem, represented by a problem graph, with an analog computer, the limitations of the hardware graph (e.g., limited connectivity) may necessitate that embedding techniques be employed to map the problem graph to the hardware graph of the analog computer. When embedding problem graphs to hardware graphs, a lack of connectivity in the hardware graph may present a challenge in directly mapping each decision variable to a qubit and each constraint to a coupler between qubits. Generally, an embedding contains one or more set of connected qubits in the hardware graph that forms connected subgraphs of the hardware graph. Each set of such qubits is called a chain. As used herein, the term “chain” refers to connected subgraphs with any (connected) topology of qubits and couplers, and not to any particular subgraph topology. For example, a fully-connected subgraph with n qubits may be referred to as a chain for any integer n. Examples of embedding techniques are described in U.S. Pat. Nos. 7,984,012, 8,244,662, 9,501,474, 10,755,190 and https://arxiv.org/abs/1406.2741.

Heuristic tools have been developed for minor embedding, e.g., given a minor and target graph, a heuristic tool tries to find a mapping that embeds the minor into the target graph. Techniques for finding graph minor embeddings can be used to find minors in arbitrary graphs for a variety of applications. However, due to the constraints of fixed hardware graph architectures in quantum processors, there is a need for techniques for embedding Ising problems onto quantum processors, (e.g., quantum annealers).

An implementation of the algorithm described in https://arxiv.org/abs/1406.2741, here referred to as ‘minorminer’, uses a form of Dijkstra's algorithm (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) in the tearup-and-replace operation. The algorithm embeds a source graph S, which can, for example, represent the graph of a problem to be solved, into a target graph T, which can, for example, represent a hardware graph of an analog processor, as a graph minor. During the execution of the algorithm, a working embedding E maps nodes in the source graph S to connected set of nodes of the target graph T. A set of connected nodes is referred throughout this specification and the appended claims as a chain. In some instances, the target graph T may be a subgraph of a graph T′. In some implementations, T′ may represent the hardware graph of a quantum processor with all devices (e.g., qubit and couplers) available and calibrated. Graph T may have fewer qubits or couplers than T′.

The minorminer algorithm may be summarized by the following steps:

1) If the working embedding E contains a chain for u, where u is a node in S, the source graph, remove the chain.

2) Optionally, remove unused portions of chains E[v] for neighbors v of u. In this context, the “unused portion” is a collection of nodes which can be removed from E[u] without disconnecting it into multiple components, and without disconnecting it from neighbors of v, other than u.

3) For each neighbor v of u with E[v] nonempty, and for each node q of T, compute the minimum node-weighted distance from q to a nearest node in E[v].

4) For each node q of T, compute the sum of distances computed in (3).

5) Select a node q of T which minimizes the sum of distances computed in (4). If more than one node minimizes the sum of distances, select one at random.

6) For each neighbor v of u with E[v] nonempty, compute a shortest path from q to a nearest node in E[v].

7) Update E[u] to be the union of paths computed in (6).

A parallelized variant of an embedding heuristic may execute multiple copies of Dijkstra's algorithm in parallel, whence the total runtime takes at least as much time as a single full run of Dijkstra's algorithm on the target graph. Therefore, speed may become a bottleneck for larger or complex problems. The systems and methods of the present specification implement a network of finite state machines that can be used to accelerate Dijkstra's algorithm on fixed hardware graphs such hardware graphs of quantum processors. This system may be optimized for implementation in FPGA/ASIC settings.

An accelerated version of a node-weighted path distance algorithm may be implemented as a systolic algorithm suitable for FPGA, ASIC or similar technologies, to replace steps (3) through (6) of the heuristic embedding algorithm described above. Several variations of this algorithm may exist. The steps (1) through (7) above are chosen as representative for their analogy to the systolic algorithm presented below; however, a person skilled in the art may understand that a different number of steps can be chosen to implement the systolic algorithm.

A systolic algorithm has many systolic cells that can operate in parallel, and each of them is to be implemented by a logic block in a microprocessor with a systolic architecture, where the logic block is also called a node module.

FIG.2is a is a schematic diagram of an example logic block200a systolic architecture, for example implemented in a microprocessor (e.g., FPGAs or ASICs) such as microprocessor107ofFIG.1. Logic block200may represent a node in a target graph, for example a device in the architecture of a hardware graph.

Logic block200may have local registers201athrough201e(collectively,201). In some instances, registers201are implemented as unsigned fixed-point integer registers, and in other instances, some or all may be unsigned floating-point number registers. Those skilled in the art will recognize that some of registers201(e.g., registers201a,201b,201c, or201d) may be omitted as physical registers in favor of logical abstractions.

A person skilled in the art may understand that the list of registers201given below is provided for example purposes only and in another implementation logic block200may have a different number of registers201.

Logic block200may have the following registers:

Register201a(W) represents the weight of logic block200.

Register201b(D) represents the upper bound on the distance to this node the nearest seed of a distance algorithm.

Register201c(N) represents the minimum distance to neighboring nodes.

Register201d(L) represents the previous value of N.

Registers201b,201cand201d(D, N and L, respectively) have the same bit-length, specified as BIT_LENGTH.

Additionally, logic block200may have local flags202athrough202d(collectively,202). A person skilled in the art may understand that the list of flags202given below is provided for example purposes only and in another implementation logic block200may have a different number of flags202.

Logic block200may have the following local flags202:

Flag202a(K) is enabled if this node is a seed of the distance computation algorithm (i.e., the systolic algorithm).

Flag202b(F) is enabled when register201b(D) is decreased and disabled otherwise.

Flag202c(M) is an array of flags, one for each neighbor. Each M[i] is enabled when the distance to the corresponding neighbor is equal to N and I[i]=0, and disabled otherwise. There is an extra flag, M[0], corresponding to the local node.

Flag202d(I) is an array of flags, one for each neighbor. Each I[i] is enabled when the edge between this logic block the corresponding neighbor should be ignored. In one implementation where the target graph represents the hardware graph of a quantum processor, a qubit is disabled by masking off all of its edges, i.e., disabling all IN for that qubit.

Logic block200supports several operations or routines203athrough203e(collectively,203). Those skilled in the art will understand that operations203may be implemented as a higher-level abstraction over micro-operations, and that other operations may be required to support data I/O. Operations203may be performed simultaneously on all logic blocks in the systolic array. In some implementations, some operations203may be fully or partially serialized, provided all logic blocks finish their work before any logic block begins work on the next operation.

A person skilled in the art may understand that the list of operations203given below is provided for example purposes only and in another implementation logic block200may have a different number or type of operations203.

Logic block200may support the following operations203:

This operation increments the Accumulator register (register201e) of logic block200to the current value of the Accumulator plus the value of the of register201b(upper bound on the distance D from the nearest seed). If the incremented value of the Accumulator exceeds a threshold (e.g., the maximum value that can be stored in the register), the register is set to a maximum value (e.g., MAX_DISTANCE).set A=A+D, if the sum overflows,set A=MAX_DISTANCE.

This operation increments the Accumulator register (register201e) to the current value of the register plus the weight W (register201a) of logic block200, if logic block200is a seed of the distance computation algorithm (i.e., the local flag K (flag202a) is enabled).if K=1, set A=A+Wotherwise, do nothing.

This operation computes the minimum distance from logic block200to the neighboring nodes, then returns the value of the minimum distance plus the weight of node200. If the value of the distance exceeds a threshold (e.g., the maximum value that can be stored in the register), the register D (register201b) is set to a maximum value (e.g., MAX_DISTANCE).

Note, the ADVANCE_DISTANCE operation has the property that if all logic blocks have local flag F (flag202b) disabled after one iteration (indicating that the value of the distance register D (register201b) is not decreasing), then subsequent ADVANCE_DISTANCE operations will not change the F flags.set L=N;compute minimum distance N to neighboring nodes x which have I[x]=0;set M[i]=1 for each neighboring node with distance N;if N<L, set F=1, otherwise, set F=0;set D=N+W, if the sum overflows,set D=MAX_DISTANCE.

This operation reset to zero the value of the distance register D (register201b) and the minimum distance register L (register201d), and enables the local flag F (flag202b, indicating register D has been decreased), assuming logic block200is a seed of the distance computation algorithm (i.e., the local flag K (flag202a) is enabled). Otherwise, both the value of the distance register D and the minimum distance register L are set to a maximum value (e.g., MAX_DISTANCE) and the local flag F is disabled.if K=1, set D=0, F=1, and N=0;otherwise, set D=MAX_DISTANCE, F=0, and N=MAX_DISTANCE.

This operation resets to zero the value of the Accumulator register (register201e) in logic block200.set A=0.

FIG.3is a schematic diagram of an example microprocessor300comprising logic blocks200athrough200n(collectively,200).

One logic block200is created per each node of T′ in a systolic architecture of microprocessor300. T′ may represent the hardware graph of a quantum processor with all devices (e.g., qubit and couplers) available and calibrated. In at least one implementation, not all devices may be available and unavailable devices are masked off. Graph T may have fewer qubits or couplers than T′. The systolic architecture (e.g., FPGAs, or ASICs) can be programmed once for T′, then quickly reconfigured to support multiple quantum processor with hardware graphs T that are subsets of T′.

The created logic blocks200are connected according to the edges of T′, via edges301athrough301m(collectively301, only one shown inFIG.3to reduce visual clutter). In some instances, logic blocks200may have additional connections to nearby logic blocks in order to facilitate data input/output (I/O); or the data I/O may be facilitated through a global data bus; or a combination of the two strategies. Additionally, all logic blocks200are connected to a single clock source302and a global control bus303to provide Single Instruction/Multiple Data (SIMD) computation by the systolic array. Each logic block200is connected to at most m other logic blocks, where m is the maximum degree of connectivity (MAX_DEGREE) of the graph. Each logic block200can receive input signals and produce output signals through channels, and a plurality of logic blocks200are connected into a fixed graph which, in some implementations, may represent the hardware graph of a quantum computer.

Further, microprocessor300supports a plurality of operations304athrough304i(collectively,304). A person skilled in the art may understand that the list of operations given below is provided for example purposes only and in another implementation microprocessor300may have a different number or type of operations.

This operation sends the operation ZERO_ACCUMULATOR (operation203eofFIG.2) to all logic blocks200over global control bus303.

This operation sends the RESET_DISTANCE operation (operation203dofFIG.2) to all logic blocks200over global control bus303.

This operation sends the operation ADVANCE_DISTANCE (operation203cofFIG.2) over global control bus303, until all logic blocks200have disabled local flag202b(F=0). Note, the ADVANCE_DISTANCE operation has the property that if all logic blocks200have F=0 after one iteration, then subsequent ADVANCE_DISTANCE operations will not change the F flags, so the RUN operation will not terminate immediately upon this condition being met.

This operation retrieves edge weights from local memory or a host system and sends them to logic blocks200. The weights are then stored in the register201a(W) of each logic block200.

This operation retrieves edge masks from local memory or a host system and sends them to logic blocks200. Edge masks are then stored in the flag202d(flag array I) of each logic block200. A node, (e.g., a qubit in the case the target graph is the hardware graph of a quantum processor) is disabled by masking off all of its edges.

This operation retrieves tie-break values from local memory or a host system and sends them to logic blocks200. Tie-break values are unique to their corresponding node and are stored into register201f(register T).

This operation retrieves seeds from local memory or the host system and sends them to logic blocks200. For each seed, the corresponding flag202a(K=1) is enabled.

This operation reads distances D from logic blocks200into local memory, or to a host system.

This operation computes the minimum accumulated value A′ of all logic blocks200and enables the respective local flag202a(e.g., K=1) for each logic block200for which the Accumulator register value (stored in respective register201e) is A=A′, and disables the local flag202a(e.g., K=0) otherwise. The operation computes the minimum tie-break value T′ from the tie-break values stored in register201fof all logic blocks200with enabled local flag202a(K=1), and disables local flag202a(K=0) for each logic block200with T!=T′. This step ensures that there is a unique minimum node with enabled local flag K, provided that the tie-break values are unique.

FIG.4is a flow chart of an example method400for embedding graphs using a systolic algorithm. Method400may be implemented by a digital processor in a computing system, for example hybrid computing system100ofFIG.1, where the digital processor is communicatively coupled to at least one microprocessor, for example microprocessor300ofFIG.3. The microprocessor may have one logic block, for example logic block200ofFIG.2, per each node of the target graph and logic blocks may be communicatively coupled according to the edges of the target graph. Method400may be optimized for implementation in FPGA or ASIC settings, where logic blocks are connected into a fixed graph (the target graph). In some implementations, the fixed graph may represent the hardware graph of quantum processor124ofFIG.1.

Method400comprises acts401to411; however, a person skilled in the art will understand that the number of acts is an example, and, in some implementations, certain acts may be omitted, further acts may be added, and/or the order of the acts may be changed. Method400will be described with reference to logic blocks200and microprocessor300.

Method400starts at401, for example in response to a call from another routine.

At402, optionally, the digital processor sends calls to all logic blocks in the microprocessor to initialize parameter values. Parameters initialized at402may be, for example, the node weights, the edge masks and tie-break values. Tie-break values are unique to their corresponding node. In one implementation, the digital processor sends calls to run at least one of the operations304d,304e,304f(LOAD_WEIGHTS, LOAD_MASKS, and LOAD_TIEBREAKS, respectively) on all logic blocks. If omitted, stored values from a previous run of method400may be used.

At403, the digital processor sends calls to all logic blocks200to reset to the value of accumulator register201e. In at least one implementation, the digital processor sends calls to all logic blocks200to perform operation304a(ZERO_ACCUMULATORS). For all logic blocks200in the microprocessor300, set A=0.

At404, for each node neighbor v of node u with the embedding E[v] nonempty, the digital processor sends a call to mark v as seed of the distance computation algorithm. The digital processor uses each chain embedding as a seed of the algorithm. In at least one implementation, the digital processor sends a call to logic blocks200to perform operation304g(LOAD_SEEDS) so that a logic block200has enabled respective local flag202a(e.g., K=1) if and only if the corresponding node is contained in E[v].

At405, for each neighbor v of u with E[v] nonempty, the digital processor computes the minimum distance from a respective logic block200to the neighboring nodes, then returns the value of the distance D as the minimum distance plus the weight of logic block200. In at least one implementation, the digital processor sends a call to perform operation304c(operation RUN). Operation203c(ADVANCE_DISTANCE) is sent over global control bus303, until all logic blocks for neighbor v of u with E[v] nonempty have disabled local flag202b(F=0).

At406, for each neighbor v of u with E[v] nonempty, the digital processor increments register201e(the Accumulator register) to the current value of the register plus the weight W (stored in register201a) of logic block200. In at least one implementation, the digital processor sends a call to perform operation203b(operation ACCUMULATE_SEED_WEIGHTS).

At407, for each neighbor v of u with E[v] nonempty, the digital processor increments register201e(the Accumulator register) of logic block200to the current value of the Accumulator plus the distance D, calculated at405. In at least one implementation, the digital processor sends a call to perform operation203a(operation ACCUMULATE_DISTANCE).

At408, the digital processor computes minimum accumulated value of the respective registers201e(the Accumulator register) of all logic blocks200that are seed of the distance computation algorithm. The digital processor uses the unique tie-break value of each node to ensure there is a unique node with minimum value of the Accumulator register. In at least one implementation, the digital processor sends a call to logic blocks200to perform operation304i(operation FIND_MINIMUM).

At409, the digital processor computes distances to the minimum node found at408from all the logic blocks, then returns the value of the distance Dminas the minimum distance plus the weight of the logic block. In at least one implementation, the digital processor sends a call to all logic blocks200to perform operation304c(operation RUN). The minimum node found at408is unique because of the uniqueness of tie-break values and will have a stored distance value in register201bD=0. Those skilled in the art will understand that the actual paths may be efficiently computed by the digital processor from this distance computation.

At410, the digital processor reads distances computed at409from logic blocks200. In at least one implementation, the digital processor sends a call to all logic blocks200to perform operation304h(operation READ_DISTANCES). The digital processor may use method400for constructing embeddings for a quantum processor. In at least one implementation, digital processor106ofFIG.1programs quantum processor124according to the distances computed at act409and read at act410of method400. Programming quantum processor124may include determining a strength of qubit and couplers biases and applying the qubit and coupler biases to quantum processor124.

In some implementation of the systolic array, where there is a single direct electrical connection in each direction in logic blocks200, each logic block200may broadcast its current distance (saved in register201b) one bit at a time, for example during operation203c(the ADVANCE_DISTANCE operation). In this case, the bits are broadcasted in the order of most significant to least significant. The minimum distance N (saved in register201c) can be computed one bit at a time, for example using an adder circuit or a Digital Signal Processors (DSP) module. This routine requires time proportional to the length of the bit (BIT_LENGTH).

FIG.5is a flow chart showing an example method500of implementing a portion of the ADVANCE_DISTANCE operation (operation203cofFIG.2). Method500may be used at acts405and/or409of method400ofFIG.4. Method500may be implemented by a digital processor in a hybrid computing system, for example hybrid computing system100ofFIG.1, where the digital processor is communicatively coupled to at least one microprocessor, for example microprocessor300ofFIG.3. The microprocessor may have one logic block per each node of the target graph and logic blocks may be communicatively coupled according to the edges of the target graph.

Method500comprises acts501to511; however, a person skilled in the art will understand that the number of acts is an example, and, in some implementations, certain acts may be omitted, further acts may be added, and/or the order of the acts may be changed.

Method500starts at501, for example in response to a call from another routine, for example from method400ofFIG.4.

At502, the digital processor causes one of logic block200in the microprocessor to broadcast the most significant bit of the distance register201b(register D) to a first neighbor. The neighboring nodes of node200have in a fixed ordering; this ordering is coordinated between nodes such that every node will receive a distance from a single neighbor at a time. The digital processor also resets register201c(the register N, minimum distance to neighboring nodes) and register201d(the register L, the previous value of N) to zero, and enables the local flag202c(flag M). N=0,M=I, L=N.

At503, the digital processor checks whether all bits of the distance register D (register201b) have been broadcasted. In at least one implementation, a counter i=1 . . . BIT_LENGTH may be increased at each iteration of method500, so that at503the digital processor checks whether i has reached maximum value BIT_LENGTH. If all bits of D have been broadcasted control passes to510, otherwise to504.

At504, the digital processor causes logic block200to store the ithmost significant bit of the neighbor distances. In at least one implementation the ithmost significant bit is stored in an array Z, with Z[0] being the ithmost significant bit of D. The length is array Z is the number of neighbors of node200.

At505, the digital processor sets Z=Z|M for logic block200, where M is the local flag202c.

At506, the digital processor computes the minimum entry of Z (0 or 1) for logic block200. The minimum entry is named b. If all entries of Z are 1, then b=1. If there is at least one entry of Z that is 0, then b=0.

At507, the digital processor updates the value of register201c(the register N). The digital processor sets N=N+N+b for logic block200.

At508, the digital processor updates the value of the local flag202c(local flag M). The digital processor sets M=M|(M[i]!=b for each i) for logic block200.

At509, the digital processor causes logic block200to broadcast the (i+1)thmost significant bit of register201b(the distance register D). After509, control passes to503, where the digital processor checks whether all bits of register201bhave been broadcasted.

At510, the digital processor updates the value of the local flag202b(local flag F) according to the value of M[0], where M[0] represents the current node. The digital processor sets F=˜M[0] for logic block200; i.e., if M[0]=0, then F=1, and vice versa.

Those skilled in the art will see that the acts502through509of method500ofFIG.5may be modified to work with sets of k bits at a time. In this case, this routine requires time proportional to BIT_LENGTH/k. Note that k may be equal to BIT_LENGTH.

In some implementation of the systolic array, where there is an auxiliary semi-local I/O fabric that facilitates message-passing, logic block200may be connected to k in-ports and k out-ports, each having a width of BIT_LENGTH. In this case, the routine requires time proportional to MAX_DEGREE/k.FIG.6below will be described assuming k=1.

FIG.6is a flow chart showing an example method600of implementing a portion of the ADVANCE_DISTANCE operation (operation203cofFIG.2) in an implementation of the microprocessor where each logic block200is connected to k in-ports and k out-ports. Method600may be used at acts405and/or409of method400ofFIG.4. Method600may be implemented by a digital processor in a hybrid computing system, for example hybrid computing system100ofFIG.1, where the digital processor is communicatively coupled to at least one microprocessor, for example microprocessor300ofFIG.3. The microprocessor may have one logic block per each node of the target graph and logic blocks may be communicatively coupled according to the edges of the target graph.

Method600comprises acts601to608; however, a person skilled in the art will understand that the number of acts is an example and, in some implementations, certain acts may be omitted, further acts may be added, and/or the order of the acts may be changed.

Method600starts at601, for example in response to a call from another routine, for example method400ofFIG.4.

At602, the digital processor causes logic block200to broadcast the first k bits of the distance D to a first neighbor. In at least one implementation, logic block200broadcasts all bits of the distance D. The neighboring nodes of node200have in a fixed ordering; this ordering is coordinated between nodes such that every node will receive a distance from a single neighbor at a time. The digital processor also resets the register N (minimum distance to neighboring nodes) and L (the previous value of N) to zero, and enables the local flag M. N=0, M=I, L=N.

At603, the digital processor checks if all bits have been broadcasted. In at least one implementation, a counter i=1 . . . MAX_DEGREE may be increased at each iteration of method600, so that at603the digital processor checks whether i has reached maximum value MAX_DEGREE. If all bits of D have been broadcasted control passes to608, otherwise to604.

At604, the digital processor causes logic block200to store in register201c(register N) the neighbor distance D′ from the ithneighbor.

At605, the digital processor checks whether D′<L. If D′<L, control passes to606, otherwise to607.

At606, the digital processor causes logic block200to set F=1 and L=D′.

At607, hybrid computing system100causes the logic block to broadcast the distance D to the (i+1)thneighbor.

The above described method(s), process(es), or technique(s) could be implemented by a series of processor readable instructions stored on one or more nontransitory processor-readable media. Some examples of the above described method(s), process(es), or technique(s) method are performed in part by a specialized device such as an adiabatic quantum computer or a quantum annealer or a system to program or otherwise control operation of an adiabatic quantum computer or a quantum annealer, for instance a computer that includes at least one digital processor. The above described method(s), process(es), or technique(s) may include various acts, though those of skill in the art will appreciate that in alternative examples certain acts may be omitted and/or additional acts may be added. Those of skill in the art will appreciate that the illustrated order of the acts is shown for example purposes only and may change in alternative examples. Some of the example acts or operations of the above described method(s), process(es), or technique(s) are performed iteratively. Some acts of the above described method(s), process(es), or technique(s) can be performed during each iteration, after a plurality of iterations, or at the end of all the iterations.

The above description of illustrated implementations, including what is described in the Abstract, is not intended to be exhaustive or to limit the implementations to the precise forms disclosed. Although specific implementations of and examples are described herein for illustrative purposes, various equivalent modifications can be made without departing from the spirit and scope of the disclosure, as will be recognized by those skilled in the relevant art. The teachings provided herein of the various implementations can be applied to other methods of quantum computation, not necessarily the example methods for quantum computation generally described above.

The various implementations described above can be combined to provide further implementations. All of the commonly assigned US patent application publications, US patent applications, foreign patents, and foreign patent applications referred to in this specification and/or listed in the Application Data Sheet are incorporated herein by reference, in their entirety, including but not limited to: U.S. Provisional Application No. 63/208,122; U.S. Pat. Nos. 7,533,068; 7,870,087; 8,032,474; International Patent Application WO2006066415; U.S. Pat. Nos. 9,170,278; 9,178,154, 10,755,190 and International Patent Application WO2017214331A1.