# US 12,602,606 B2 · Apparatuses, computer-implemented methods, and computer program products for improved global qubit positioning in a quantum computing environment > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,602,606 B2 - Document ID: US12602606B2 - Status: Granted - Kind: B2 - Application number: 17/358,891 - Filed: 2021-06-25 - Published: 2022-12-29 - Granted: 2026-04-14 - Earliest claimed: 2021-06-25 - Assignees: Quantinuum LLC - Applicants: Quantinuum LLC - Inventors: Alexander Chernoguzov; Stephen James Ragole; Megan Lynn Kohagen; David Hayes; Ian Mark Hoffman - Web page: https://patentgrep.com/patent/US12602606B2 ## CPC - G06N 10/20: Models of quantum computing, e.g. quantum circuits or universal quantum computers - G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms - G06N 10/40: Physical realisations or architectures of quantum processors or components for manipulating qubits, e.g. qubit coupling or qubit control - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract Embodiments of the present disclosure provide for efficient global qubit placement within a quantum computing environment for a quantum program. Some embodiments utilize a graph-based approach to represent positions in a quantum computing environment, and optimize the graph layout using a graph processing algorithm to rearrange layers of a graph and reduce edge crossings. A layered graph associated with minimum cost is selected and utilized as an efficient layered graph for purposes of global qubit placement at various time steps of execution. Embodiments provide satisfactory approximations that avoid the NP-hard nature of this task to significantly reduce compilation time to a solution for global qubit placement as opposed to optimal global qubit placement while additionally identifying solutions that significantly reduce overall execution time and computing resource usage. ## Claims ### Claim 1 An apparatus comprising at least one processor and at least one memory having computer-coded instructions stored thereon that, in execution with the at least one processor, configure the apparatus to: identify a qubit grouping set representing a quantum program associated with a qubit set; generate an initial layered graph comprising a node set and an edge set arranged into one or more layers representing one or more time slices, wherein each node of the node set represents a qubit group of the qubit grouping set, wherein each edge of the edge set connects a first node in a first layer of the one or more layers to a second node in a second layer of the one or more layers, the first node comprising at least one qubit index shared with the second node; generate an efficient layered graph by transforming the initial layered graph utilizing a graph processing algorithm, wherein the graph processing algorithm reduces a number of edge crossings in the initial layered graph; determine a qubit position arrangement for the qubit set based at least in part on the efficient layered graph; and reposition the qubit set within a quantum computing environment by executing a set of qubit manipulation instructions using the determined qubit position arrangement. ### Claim 2 (depends on 1) The apparatus according to claim 1, wherein the graph processing algorithm comprises a Sugiyama algorithm implementation. ### Claim 3 (depends on 1) The apparatus according to claim 1, wherein the graph processing algorithm utilizes a barycenter heuristic to rearrange a subset of nodes at each layer of the one or more layers. ### Claim 4 (depends on 1) The apparatus according to claim 1, wherein the graph processing algorithm utilizes a randomized component to rank each node. ### Claim 5 (depends on 1) The apparatus according to claim 1, wherein the graph processing algorithm implements a cost function that minimizes a number of required parallel swap time steps as a primary cost factor and the cost function minimizes a number of swap operations as a secondary cost factor. ### Claim 6 (depends on 1) The apparatus according to claim 1, wherein to generate the efficient layered graph, the apparatus is configured to: generate at least one additional initial layered graph, each additional initial layered graph comprising a randomly arranged first layer; generate an additional possible efficient layered graph for each additional initial layered graph by transforming each additional initial layered graph utilizing the graph processing algorithm; and select the efficient layered graph from each additional possible efficient layered graph. ### Claim 7 (depends on 1) The apparatus according to claim 1, the apparatus further configured to: determine a parallel swap command set from the efficient layered graph; and insert into the parallel swap command set at least one slide command based at least in part on a number of gate zones associated with a quantum computing environment and a number of qubits in the qubit set. ### Claim 8 (depends on 1) The apparatus according to claim 1, wherein the graph processing algorithm performs graph squeezing based at least in part on a qubit gating positions set. ### Claim 9 (depends on 1) The apparatus according to claim 1, wherein the initial layered graph comprises a two-dimensional layered graph representing a linear quantum computing environment. ### Claim 10 (depends on 1) The apparatus according to claim 1, wherein the initial layered graph comprises a three-dimensional layered graph representing a loop quantum computing environment. ### Claim 11 A computer-implemented method comprising: identifying a qubit grouping set representing a quantum program associated with a qubit set; generating an initial layered graph comprising a node set and an edge set arranged into one or more layers representing one or more time slices, wherein each node of the node set represents a qubit group of the qubit grouping set, wherein each edge of the edge set connects a first node in a first layer of the one or more layers to a second node in a second layer of the one or more layers, the first node comprising at least one qubit index shared with the second node; generating an efficient layered graph by transforming the initial layered graph utilizing a graph processing algorithm, wherein the graph processing algorithm reduces a number of edge crossings in the initial layered graph; determining a qubit position arrangement for the qubit set based at least in part on the efficient layered graph; and repositioning the qubit set within a quantum computing environment by executing a set of qubit manipulation instructions using the determined qubit position arrangement. ### Claim 12 (depends on 11) The computer-implemented method according to claim 11, wherein the graph processing algorithm comprises a Sugiyama algorithm implementation. ### Claim 13 (depends on 11) The computer-implemented method according to claim 11, wherein the graph processing algorithm utilizes a barycenter heuristic to rearrange a subset of nodes at each layer of the one or more layers. ### Claim 14 (depends on 11) The computer-implemented method according to claim 11, wherein the graph processing algorithm utilizes a randomized component to rank each node. ### Claim 15 (depends on 11) The computer-implemented method according to claim 11, wherein the graph processing algorithm implements a cost function that minimizes a number of required parallel swap time steps as a primary cost factor and the cost function minimizes a number of swap operations as a secondary cost factor. ### Claim 16 (depends on 11) The computer-implemented method according to claim 11, wherein generating the efficient layered graph further comprises: generating at least one additional initial layered graph, each additional initial layered graph comprising a randomly arranged first layer; generating an additional possible efficient layered graph for each additional initial layered graph by transforming each additional initial layered graph utilizing the graph processing algorithm; and selecting the efficient layered graph from each additional possible efficient layered graph. ### Claim 17 (depends on 11) The computer-implemented method according to claim 11, the computer-implemented method further comprising: determining a parallel swap command set from the efficient layered graph; and inserting into the parallel swap command set at least one slide command based at least in part on a number of gate zones associated with a quantum computing environment and a number of qubits in the qubit set. ### Claim 18 A computer program product comprising at least one non transitory computer-readable storage medium having computer program code stored thereon that, in execution with at least one processor, is configured for: identifying a qubit grouping set representing a quantum program associated with a qubit set; generating an initial layered graph comprising a node set and an edge set arranged into one or more layers representing one or more time slices, wherein each node of the node set represents a qubit group of the qubit grouping set, wherein each edge of the edge set connects a first node in a first layer of the one or more layers to a second node in a second layer of the one or more layers, the first node comprising at least one qubit index shared with the second node; generating an efficient layered graph by transforming the initial layered graph utilizing a graph processing algorithm, wherein the graph processing algorithm reduces a number of edge crossings in the initial layered graph; determining a qubit position arrangement for the qubit set based at least in part on the efficient layered graph; and repositioning the qubit set within a quantum computing environment by executing a set of qubit manipulation instructions using the determined qubit position arrangement. ### Claim 19 (depends on 18) The computer program product according to claim 18, wherein generating the efficient layered graph comprises: generating at least one additional initial layered graph, each additional initial layered graph comprising a randomly arranged first layer; generating an additional possible efficient layered graph for each additional initial layered graph by transforming each additional initial layered graph utilizing the graph processing algorithm; and selecting the efficient layered graph from each additional possible efficient layered graph. ### Claim 20 (depends on 18) The computer program product according to claim 18, wherein at least one of: the graph processing algorithm comprises a Sugiyama algorithm implementation, the graph processing algorithm utilizes a barycenter heuristic to rearrange a subset of nodes at each layer of the one or more layers, the graph processing algorithm utilizes a randomized component to rank each node, or the graph processing algorithm implements a cost function that minimizes a number of required parallel swap time steps as a primary cost factor and the cost function minimizes a number of swap operations as a secondary cost factor.