# US 2025/0094849 A1 · Qubit mapping method and apparatus, device, and storage medium

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0094849 A1
- Document ID: US20250094849A1
- Status: Published application
- Kind: A1
- Application number: 18/767,831
- Filed: 2024-07-09
- Published: 2025-03-20
- Earliest claimed: 2023-09-15
- Assignees: Tencent Technology (Shenzhen) Company Limited
- Applicants: Tencent Technology (Shenzhen) Company Limited
- Inventors: Pei YUAN; Shengyu ZHANG
- Web page: https://patentgrep.com/patent/US20250094849A1

## CPC

- G06N 10/20: Models of quantum computing, e.g. quantum circuits or universal quantum computers
- G06N 10/40: Physical realisations or architectures of quantum processors or components for manipulating qubits, e.g. qubit coupling or qubit control
- G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

A qubit mapping method is performed by a computer device. The method includes: obtaining a coupling graph corresponding to a quantum device, each vertex in the coupling graph representing one qubit in the quantum device, an edge between two vertexes representing that a two-qubit gate is allowed to directly act on qubits corresponding to the two vertexes; generating at least two connected subgraphs based on the coupling graph, a quantity of vertexes of each connected subgraph being greater than or equal to 2 and less than or equal to a routing number of the coupling graph, and a sum of quantities of vertexes of the at least two connected subgraphs being equal to a constant multiple of a quantity of vertexes of the coupling graph; and performing qubit mapping on a logic circuit based on the at least two connected subgraphs, to obtain a corresponding hardware compilable circuit.

## Claims

### Claim 1

A qubit mapping method performed by a computer device, the method comprising:
obtaining a coupling graph corresponding to a quantum device, each vertex in the coupling graph representing one qubit in the quantum device, an edge between two vertexes representing that a two-qubit gate is allowed to directly act on qubits corresponding to the two vertexes;
generating at least two connected subgraphs based on the coupling graph, a quantity of vertexes of each connected subgraph being greater than or equal to 2 and less than or equal to a routing number of the coupling graph, a sum of quantities of vertexes of the at least two connected subgraphs being equal to a constant multiple of a quantity of vertexes of the coupling graph, and the routing number of the coupling graph being a maximum quantity of permutation rounds of all permutations on the coupling graph; and
performing qubit mapping on a logic circuit based on the at least two connected subgraphs, to obtain a hardware compilable circuit equivalent to the logic circuit.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the generating at least two connected subgraphs based on the coupling graph comprises:
generating a first vertex set family and a second vertex set family based on the coupling graph, the first vertex set family comprising at least one vertex set, the second vertex set family comprising at least one vertex set, each vertex set comprising at least two vertexes in the coupling graph; and
generating a connected subgraph corresponding to each vertex set in the first vertex set family and the second vertex set family, to obtain the at least two connected subgraphs,
the first vertex set family and the second vertex set family meeting the following conditions:
a subgraph corresponding to each vertex set in the first vertex set family and the second vertex set family is a connected graph;
same vertexes do not exist in any two vertex sets in the first vertex set family, and same vertexes do not exist in any two vertex sets in the second vertex set family;
a quantity of vertexes in each vertex set in the first vertex set family and the second vertex set family is greater than or equal to 2 and less than or equal to the routing number of the coupling graph; and
a total quantity of vertexes in the first vertex set family and the second vertex set family is equal to a constant multiple of the quantity of vertexes of the coupling graph.

### Claim 3 (depends on 2)

The method according to claim 2, wherein the generating a first vertex set family and a second vertex set family based on the coupling graph comprises:
constructing maximum matching of the coupling graph, the maximum matching comprising at least one edge in the coupling graph;
generating the first vertex set family based on the maximum matching, each vertex set in the first vertex set family corresponding to two vertexes connected by an edge comprised in the maximum matching; and
generating the second vertex set family based on the first vertex set family.

### Claim 4 (depends on 3)

The method according to claim 3, wherein the generating the second vertex set family based on the first vertex set family comprises:
determining an initialized set Tp based on the first vertex set family, the initialized set Tp comprising vertexes that belong to the coupling graph and do not belong to the first vertex set family, p being a positive integer whose initial value is 1;
determining an initialized set Sp based on the initialized set Tp, the initialized set Sp comprising vertexes in the first vertex set family connected to the vertexes in the initialized set Tp;
determining that an initialized set Ni0 is an empty set and determining that an initialized set A0,p is an empty set, i being a positive integer whose initial value is 1;
placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p, \ representing a difference set between two sets, and the adjacent vertex of the ith vertex being a vertex connected to the ith vertex;
determining a union set of a set Nip-1 and the set Ai,p as a set Nip;
if i is less than k1, making i=i+1 and starting execution again from the operation of placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p, k1 being a quantity of vertexes in the set Sp;
if i is equal to k1, when |∪i∈[kp]Nip| is greater than or equal to |Tp|/2, generating the second vertex set family, a vertex set comprised in the second vertex set family being a union set of the set Nip and the ith vertex in the set Sp, |∪i∈[kp]Nip| representing a quantity of vertexes in ∪i∈[kp]Nip, and |Tp| representing a quantity of vertexes in the set Tp;
determining a set Tp\∪r∈[k1]Ar,p as set Tp+1;
determining a set Sp+1 based on the set Tp and a set kp;
determining |Sp+1| as kp+1, |Sp+1| representing a quantity of vertexes in the set Sp+1;
if p is less than |T1|, making p=p+1 and starting execution again from the operation of placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p; and
if p is equal to |T1|, ending the procedure to obtain the finally generated second vertex set family.

### Claim 5 (depends on 4)

The method according to claim 4, wherein the placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p comprises:
if the ith vertex in the set Sp has at most ┌|Tp|/kp┐ adjacent vertexes in the set Tp\∪r=0i-1Ar,p, selecting all adjacent vertexes of the ith vertex in the set Tp\∪r=0i-1Ar,p and placing all the adjacent vertexes into the set Ai,p; or
if the ith vertex in the set Sp has more than ┌|Tp|/kp┐ adjacent vertexes in the set Tp\∪r=0i-1Ar,p, selecting at most ┌|Tp|/kp┐ adjacent vertexes of the ith vertex in the set Tp\∪r=0i-1Ar,p and placing the at most ┌|Tp|/kp┐ adjacent vertexes into the set Ai,p,
┌|Tp|/kp┐ representing rounding up |Tp|/kp.

### Claim 6 (depends on 1)

The method according to claim 1, wherein the performing qubit mapping on a logic circuit based on the at least two connected subgraphs, to obtain a hardware compilable circuit equivalent to the logic circuit comprises:
permuting a first quantity of logic bit pairs in the logic circuit based on the at least two connected subgraphs, the first quantity being a quantity of edges comprised in the maximum matching of the coupling graph, and each logic bit pair corresponding to two qubits on which one two-qubit gate acts in the logic circuit;
generating a first portion of the hardware compilable circuit corresponding to the first quantity of logic bit pairs;
permuting remaining logic bit pairs in the logic circuit based on the at least two connected subgraphs;
generating a second portion of the hardware compilable circuit corresponding to the remaining logic bit pairs; and
obtaining the hardware compilable circuit equivalent to the logic circuit based on the first portion of the hardware compilable circuit and the second portion of the hardware compilable circuit.

### Claim 7 (depends on 6)

The method according to claim 6, wherein after the obtaining the hardware compilable circuit equivalent to the logic circuit based on the first portion of the hardware compilable circuit and the second portion of the hardware compilable circuit, the method further comprises:
permuting each logic bit in the logic circuit to an original position.

### Claim 8

A computer device, comprising a processor and a memory, the memory having a computer program stored therein that, when loaded and executed by the processor, causes the computer device to implement a qubit mapping method including:
obtaining a coupling graph corresponding to a quantum device, each vertex in the coupling graph representing one qubit in the quantum device, an edge between two vertexes representing that a two-qubit gate is allowed to directly act on qubits corresponding to the two vertexes;
generating at least two connected subgraphs based on the coupling graph, a quantity of vertexes of each connected subgraph being greater than or equal to 2 and less than or equal to a routing number of the coupling graph, a sum of quantities of vertexes of the at least two connected subgraphs being equal to a constant multiple of a quantity of vertexes of the coupling graph, and the routing number of the coupling graph being a maximum quantity of permutation rounds of all permutations on the coupling graph; and
performing qubit mapping on a logic circuit based on the at least two connected subgraphs, to obtain a hardware compilable circuit equivalent to the logic circuit.

### Claim 9 (depends on 8)

The computer device according to claim 8, wherein the generating at least two connected subgraphs based on the coupling graph comprises:
generating a first vertex set family and a second vertex set family based on the coupling graph, the first vertex set family comprising at least one vertex set, the second vertex set family comprising at least one vertex set, each vertex set comprising at least two vertexes in the coupling graph; and
generating a connected subgraph corresponding to each vertex set in the first vertex set family and the second vertex set family, to obtain the at least two connected subgraphs,
the first vertex set family and the second vertex set family meeting the following conditions:
a subgraph corresponding to each vertex set in the first vertex set family and the second vertex set family is a connected graph;
same vertexes do not exist in any two vertex sets in the first vertex set family, and same vertexes do not exist in any two vertex sets in the second vertex set family;
a quantity of vertexes in each vertex set in the first vertex set family and the second vertex set family is greater than or equal to 2 and less than or equal to the routing number of the coupling graph; and
a total quantity of vertexes in the first vertex set family and the second vertex set family is equal to a constant multiple of the quantity of vertexes of the coupling graph.

### Claim 10 (depends on 9)

The computer device according to claim 9, wherein the generating a first vertex set family and a second vertex set family based on the coupling graph comprises:
constructing maximum matching of the coupling graph, the maximum matching comprising at least one edge in the coupling graph;
generating the first vertex set family based on the maximum matching, each vertex set in the first vertex set family corresponding to two vertexes connected by an edge comprised in the maximum matching; and
generating the second vertex set family based on the first vertex set family.

### Claim 11 (depends on 10)

The computer device according to claim 10, wherein the generating the second vertex set family based on the first vertex set family comprises:
determining an initialized set Tp based on the first vertex set family, the initialized set Tp comprising vertexes that belong to the coupling graph and do not belong to the first vertex set family, p being a positive integer whose initial value is 1;
determining an initialized set Sp based on the initialized set Tp, the initialized set Sp comprising vertexes in the first vertex set family connected to the vertexes in the initialized set Tp;
determining that an initialized set Ni0 is an empty set and determining that an initialized set A0,p is an empty set, i being a positive integer whose initial value is 1;
placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p, \ representing a difference set between two sets, and the adjacent vertex of the ith vertex being a vertex connected to the ith vertex;
determining a union set of a set Nip-1 and the set Ai,p as a set Nip;
if i is less than k1, making i=i+1 and starting execution again from the operation of placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p, k1 being a quantity of vertexes in the set Sp;
if i is equal to k1, when |∪i∈[kp]Nip| is greater than or equal to |Tp|/2, generating the second vertex set family, a vertex set comprised in the second vertex set family being a union set of the set Nip and the ith vertex in the set Sp, |Ui∈[kp]Nip| representing a quantity of vertexes in ∪i∈[kp]Nip, and |Tp| representing a quantity of vertexes in the set Tp;
determining a set Tp\∪r∈[k1]Ar,p as set Tp+1;
determining a set Sp+1 based on the set Tp and a set kp;
determining |Sp+1| as kp+1, |Sp+1| representing a quantity of vertexes in the set Sp+1;
if p is less than |T1|, making p=p+1 and starting execution again from the operation of placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p; and
if p is equal to |T1|, ending the procedure to obtain the finally generated second vertex set family.

### Claim 12 (depends on 11)

The computer device according to claim 11, wherein the placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p comprises:
if the ith vertex in the set Sp has at most ┌|Tp|/kp┐ adjacent vertexes in the set Tp\∪r=0i-1Ar,p, selecting all adjacent vertexes of the ith vertex in the set Tp\∪r=0i-1Ar,p and placing all the adjacent vertexes into the set Ai,p; or
if the ith vertex in the set Sp has more than ┌|Tp|/kp┐ adjacent vertexes in the set Tp\∪r=0i-1Ar,p, selecting at most ┌|Tp|/kp┐ adjacent vertexes of the ith vertex in the set Tp\∪r=0i-1Ar,p and placing the at most ┌|Tp|/kp┐ adjacent vertexes into the set Ai,p,
┌|Tp|/kp┐ representing rounding up |Tp|/kp.

### Claim 13 (depends on 8)

The computer device according to claim 8, wherein the performing qubit mapping on a logic circuit based on the at least two connected subgraphs, to obtain a hardware compilable circuit equivalent to the logic circuit comprises:
permuting a first quantity of logic bit pairs in the logic circuit based on the at least two connected subgraphs, the first quantity being a quantity of edges comprised in the maximum matching of the coupling graph, and each logic bit pair corresponding to two qubits on which one two-qubit gate acts in the logic circuit;
generating a first portion of the hardware compilable circuit corresponding to the first quantity of logic bit pairs;
permuting remaining logic bit pairs in the logic circuit based on the at least two connected subgraphs;
generating a second portion of the hardware compilable circuit corresponding to the remaining logic bit pairs; and
obtaining the hardware compilable circuit equivalent to the logic circuit based on the first portion of the hardware compilable circuit and the second portion of the hardware compilable circuit.

### Claim 14 (depends on 13)

The computer device according to claim 13, wherein after the obtaining the hardware compilable circuit equivalent to the logic circuit based on the first portion of the hardware compilable circuit and the second portion of the hardware compilable circuit, the method further comprises:
permuting each logic bit in the logic circuit to an original position.

### Claim 15

A non-transitory computer-readable storage medium having a computer program stored therein that, when loaded and executed by a processor of a computer device, causes the computer device to implement a qubit mapping method including:
obtaining a coupling graph corresponding to a quantum device, each vertex in the coupling graph representing one qubit in the quantum device, an edge between two vertexes representing that a two-qubit gate is allowed to directly act on qubits corresponding to the two vertexes;
generating at least two connected subgraphs based on the coupling graph, a quantity of vertexes of each connected subgraph being greater than or equal to 2 and less than or equal to a routing number of the coupling graph, a sum of quantities of vertexes of the at least two connected subgraphs being equal to a constant multiple of a quantity of vertexes of the coupling graph, and the routing number of the coupling graph being a maximum quantity of permutation rounds of all permutations on the coupling graph; and
performing qubit mapping on a logic circuit based on the at least two connected subgraphs, to obtain a hardware compilable circuit equivalent to the logic circuit.

### Claim 16 (depends on 15)

The non-transitory computer-readable storage medium according to claim 15, wherein the generating at least two connected subgraphs based on the coupling graph comprises:
generating a first vertex set family and a second vertex set family based on the coupling graph, the first vertex set family comprising at least one vertex set, the second vertex set family comprising at least one vertex set, each vertex set comprising at least two vertexes in the coupling graph; and
generating a connected subgraph corresponding to each vertex set in the first vertex set family and the second vertex set family, to obtain the at least two connected subgraphs,
the first vertex set family and the second vertex set family meeting the following conditions:
a subgraph corresponding to each vertex set in the first vertex set family and the second vertex set family is a connected graph;
same vertexes do not exist in any two vertex sets in the first vertex set family, and same vertexes do not exist in any two vertex sets in the second vertex set family;
a quantity of vertexes in each vertex set in the first vertex set family and the second vertex set family is greater than or equal to 2 and less than or equal to the routing number of the coupling graph; and
a total quantity of vertexes in the first vertex set family and the second vertex set family is equal to a constant multiple of the quantity of vertexes of the coupling graph.

### Claim 17 (depends on 16)

The non-transitory computer-readable storage medium according to claim 16, wherein the generating a first vertex set family and a second vertex set family based on the coupling graph comprises:
constructing maximum matching of the coupling graph, the maximum matching comprising at least one edge in the coupling graph;
generating the first vertex set family based on the maximum matching, each vertex set in the first vertex set family corresponding to two vertexes connected by an edge comprised in the maximum matching; and
generating the second vertex set family based on the first vertex set family.

### Claim 18 (depends on 17)

The non-transitory computer-readable storage medium according to claim 17, wherein the generating the second vertex set family based on the first vertex set family comprises:
determining an initialized set Tp based on the first vertex set family, the initialized set Tp comprising vertexes that belong to the coupling graph and do not belong to the first vertex set family, p being a positive integer whose initial value is 1;
determining an initialized set Sp based on the initialized set Tp, the initialized set Sp comprising vertexes in the first vertex set family connected to the vertexes in the initialized set Tp;
determining that an initialized set Ni0 is an empty set and determining that an initialized set A0,p is an empty set, i being a positive integer whose initial value is 1;
placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p, \ representing a difference set between two sets, and the adjacent vertex of the ith vertex being a vertex connected to the ith vertex;
determining a union set of a set Nip-1 and the set Ai,p as a set Nip;
if i is less than k1, making i=i+1 and starting execution again from the operation of placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p, k1 being a quantity of vertexes in the set Sp;
if i is equal to k1, when |∪i∈[kp]Nip| is greater than or equal to |Tp|/2, generating the second vertex set family, a vertex set comprised in the second vertex set family being a union set of the set Nip and the ith vertex in the set Sp, |∪i∈[kp]Nip| representing a quantity of vertexes in ∪i∈[kp]Nip, and |Tp| representing a quantity of vertexes in the set Tp;
determining a set Tp\∪i∈[kp]Ar,p as a set Tp+1;
determining a set Sp+1 based on the set Tp and a set kp;
determining |Sp+1| as kp+1, |Sp+1| representing a quantity of vertexes in the set Sp+1;
if p is less than |T1|, making p=p+1 and starting execution again from the operation of placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p; and
if p is equal to |T1|, ending the procedure to obtain the finally generated second vertex set family.

### Claim 19 (depends on 18)

The non-transitory computer-readable storage medium according to claim 18, wherein the placing an adjacent vertex of an ith vertex in the set Sp in a set Tp\∪r=0i-1Ar,p into a set Ai,p comprises:
if the ith vertex in the set Sp has at most ┌|Tp|/kp┐ adjacent vertexes in the set Tp\∪r=0i-1Ar,p, selecting all adjacent vertexes of the ith vertex in the set Tp\∪r=0i-1Ar,p and placing all the adjacent vertexes into the set Ai,p; or
if the ith vertex in the set Sp has more than ┌|Tp|/kp┐ adjacent vertexes in the set Tp\∪r=0i-1Ar,p, selecting at most ┌|Tp|/kp┐ adjacent vertexes of the ith vertex in the set Tp\∪r=0i-1Ar,p and placing the at most ┌|Tp|/kp┐ adjacent vertexes into the set Ai,p,
┌|Tp|/kp┐ representing rounding up |Tp|/kp.

### Claim 20 (depends on 15)

The non-transitory computer-readable storage medium according to claim 15, wherein the performing qubit mapping on a logic circuit based on the at least two connected subgraphs, to obtain a hardware compilable circuit equivalent to the logic circuit comprises:
permuting a first quantity of logic bit pairs in the logic circuit based on the at least two connected subgraphs, the first quantity being a quantity of edges comprised in the maximum matching of the coupling graph, and each logic bit pair corresponding to two qubits on which one two-qubit gate acts in the logic circuit;
generating a first portion of the hardware compilable circuit corresponding to the first quantity of logic bit pairs;
permuting remaining logic bit pairs in the logic circuit based on the at least two connected subgraphs;
generating a second portion of the hardware compilable circuit corresponding to the remaining logic bit pairs; and
obtaining the hardware compilable circuit equivalent to the logic circuit based on the first portion of the hardware compilable circuit and the second portion of the hardware compilable circuit.