Qubit allocation for noisy intermediate-scale quantum computers

A system comprising:

• a computing node comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor of the computing node to cause the processor to perform a method comprising:
• receiving a description of a quantum circuit, the quantum circuit comprising a plurality of logical qubits;
• receiving a hardware specification, the hardware specification comprising a connectivity graph of a plurality of physical qubits;
• determining a directed acyclic allocation graph based on the plurality of logical qubits and the connectivity graph, wherein the directed acyclic allocation graph comprises
• a node for each possible allocation of the plurality of logical qubits to the plurality of physical qubits, each allocation having a fidelity, and
• a plurality of directed edges, each edge connecting to its corresponding first node from its corresponding second node, the first node corresponding to a first allocation, the second node corresponding to a sub-allocation of the first allocation;
• searching the directed acyclic allocation graph for a weighted shortest path from a root node of the directed acyclic allocation graph to a leaf node of the directed acyclic allocation graph;
• and
• outputting the allocation corresponding to the weighted shortest path.

A computer program product for quantum problem compilation, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:

• receiving a description of a quantum circuit, the quantum circuit comprising a plurality of logical qubits;
• receiving a hardware specification, the hardware specification comprising a connectivity graph of a plurality of physical qubits;
• determining a directed acyclic allocation graph based on the plurality of logical qubits and the connectivity graph, wherein the directed acyclic allocation graph comprises
• a node for each possible allocation of the plurality of logical qubits to the plurality of physical qubits, each allocation having a fidelity, and
• a plurality of directed edges, each edge connecting to its corresponding first node from its corresponding second node, the first node corresponding to a first allocation, the second node corresponding to a sub-allocation of the first allocation;
• searching the directed acyclic allocation graph for a weighted shortest path from a root node of the directed acyclic allocation graph to a leaf node of the directed acyclic allocation graph;
• and
• outputting the allocation corresponding to the weighted shortest path.