# US 2021/0173988 A1 · Quantum circuit embedding by simulated annealing

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

- Number: US 2021/0173988 A1
- Document ID: US20210173988A1
- Status: Published application
- Kind: A1
- Application number: 17/179,975
- Filed: 2021-02-19
- Published: 2021-06-10
- Earliest claimed: 2018-08-21
- Assignees: President and Fellows of Harvard College
- Applicants: President and Fellows of Harvard College
- Inventors: Yudong Cao
- Web page: https://patentgrep.com/patent/US20210173988A1

## CPC

- G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
- G06F 2111/06: Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Mapping of logical qubits to physical qubits is provided. In various embodiments, a first candidate subgraph is selected from a hardware graph. The hardware graph represents a physical quantum circuit. The hardware graph comprises a plurality of nodes corresponding to physical qubits and a plurality of edges corresponding to coupling among the plurality of qubits. An accepted subgraph is determined by: setting the accepted subgraph to be the first candidate subgraph; mapping a quantum circuit comprising a plurality of logical qubits to the accepted subgraph; generating a second candidate subgraph of the hardware graph based on the accepted subgraph; mapping the quantum circuit to the second candidate subgraph; comparing fidelities of the accepted subgraph and the second candidate subgraph for the quantum circuit; if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph; if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.

## Claims

### Claim 1

A method of mapping a quantum circuit to hardware, the method comprising:
selecting a first candidate subgraph of a hardware graph, the hardware graph representing a physical quantum circuit, the hardware graph comprising a plurality of nodes corresponding to physical qubits and a plurality of edges corresponding to coupling of the plurality of physical qubits;
determining an accepted subgraph by:
setting the accepted subgraph to be the first candidate subgraph;
mapping a quantum circuit comprising a plurality of logical qubits to the accepted subgraph;
generating a second candidate subgraph of the hardware graph based on the accepted subgraph;
mapping the quantum circuit to the second candidate subgraph;
comparing fidelities of the accepted subgraph and the second candidate subgraph for the quantum circuit;
if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph;
if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.

### Claim 2 (depends on 1)

The method of claim 1, wherein selecting the first candidate subgraph comprises selecting a random node of the hardware graph, and performing a depth-first search therefrom.

### Claim 3 (depends on 1)

The method of claim 1, wherein generating the second candidate subgraph from the accepted subgraph comprises selecting a random node of the first candidate subgraph, and performing a depth-first search on the hardware graph therefrom.

### Claim 4 (depends on 1)

The method of claim 1, wherein generating the second candidate subgraph from the accepted subgraph comprises reversing the placement of at least two of the logical qubits in the accepted subgraph.

### Claim 5 (depends on 1)

The method of claim 1, wherein generating the second candidate subgraph from the accepted subgraph comprises randomly performing one of: i) selecting a random node of the accepted subgraph, and performing a depth-first search on the hardware graph therefrom; or ii) reversing the placement of at least two nodes in the accepted subgraph.

### Claim 6 (depends on 1)

The method of claim 1, wherein the time-dependent probability is monotonically decreasing.

### Claim 7 (depends on 1)

The method of claim 1, wherein determining an accepted subgraph further comprises repeatedly:
generating an additional candidate subgraph of the hardware graph based on the accepted subgraph;
mapping the quantum circuit to the additional candidate subgraph;
comparing fidelities of the accepted subgraph and the additional candidate subgraph for the quantum circuit;
if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph;
if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.

### Claim 8 (depends on 7)

The method of claim 7, wherein generating the additional candidate subgraph based on the accepted subgraph comprises randomly performing one of: i) selecting a random node of the accepted subgraph, and performing a depth-first search on the hardware graph therefrom; or ii) reversing the placement of at least two nodes in the accepted subgraph.

### Claim 9 (depends on 7)

The method of claim 7, wherein determining an accepted subgraph further comprises:
ceasing said repetition after a predetermined number of cycles.

### Claim 10

A computer program product for mapping a quantum circuit to hardware, 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:
selecting a first candidate subgraph of a hardware graph, the hardware graph representing a physical quantum circuit, the hardware graph comprising a plurality of nodes corresponding to physical qubits and a plurality of edges corresponding to coupling of the plurality of physical qubits;
determining an accepted subgraph by:
setting the accepted subgraph to be the first candidate subgraph;
mapping a quantum circuit comprising a plurality of logical qubits to the accepted subgraph;
generating a second candidate subgraph of the hardware graph based on the accepted subgraph;
mapping the quantum circuit to the second candidate subgraph;
comparing fidelities of the accepted subgraph and the second candidate subgraph for the quantum circuit;
if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph;
if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.

### Claim 11 (depends on 10)

The computer program product of claim 10, wherein selecting the first candidate subgraph comprises selecting a random node of the hardware graph, and performing a depth-first search therefrom.

### Claim 12 (depends on 10)

The computer program product of claim 10, wherein generating the second candidate subgraph from the accepted subgraph comprises selecting a random node of the first candidate subgraph, and performing a depth-first search on the hardware graph therefrom.

### Claim 13 (depends on 10)

The computer program product of claim 10, wherein generating the second candidate subgraph from the accepted subgraph comprises reversing the placement of at least two of the logical qubits in the accepted subgraph.

### Claim 14 (depends on 10)

The computer program product of claim 10, wherein generating the second candidate subgraph from the accepted subgraph comprises randomly performing one of: i) selecting a random node of the accepted subgraph, and performing a depth-first search on the hardware graph therefrom; or ii) reversing the placement of at least two nodes in the accepted subgraph.

### Claim 15 (depends on 10)

The computer program product of claim 10, wherein the time-dependent probability is monotonically decreasing.

### Claim 16 (depends on 10)

The computer program product of claim 10, wherein determining an accepted subgraph further comprises repeatedly:
generating an additional candidate subgraph of the hardware graph based on the accepted subgraph;
mapping the quantum circuit to the additional candidate subgraph;
comparing fidelities of the accepted subgraph and the additional candidate subgraph for the quantum circuit;
if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph;
if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.

### Claim 17 (depends on 16)

The computer program product of claim 16, wherein generating the additional candidate subgraph based on the accepted subgraph comprises randomly performing one of: i) selecting a random node of the accepted subgraph, and performing a depth-first search on the hardware graph therefrom; or ii) reversing the placement of at least two nodes in the accepted subgraph.

### Claim 18 (depends on 16)

The computer program product of claim 16, wherein determining an accepted subgraph further comprises:
ceasing said repetition after a predetermined number of cycles.
