# US 2021/0081589 A1 · System for reversible circuit compilation with space constraint, method and program

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

- Number: US 2021/0081589 A1
- Document ID: US20210081589A1
- Status: Published application
- Kind: A1
- Application number: 17/094,641
- Filed: 2020-11-10
- Published: 2021-03-18
- Earliest claimed: 2015-06-08
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Martin Roetteler; Krysta Svore; Alex Parent
- Web page: https://patentgrep.com/patent/US20210081589A1

## CPC

- G06F 30/327: Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
- G09C 1/00: Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00)
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The disclosed technology includes, among other innovations, a framework for resource efficient compilation of higher-level programs into lower-level reversible circuits. In particular embodiments, the disclosed technology reduces the memory footprint of a reversible network implemented in a quantum computer and generated from a higher-level program. Such a reduced-memory footprint is desirable in that it addresses the limited availability of qubits available in many target quantum computer architectures.

## Claims

### Claim at position 1

1-8. (canceled)

### Claim 9

A method, comprising:
by one or more specialized reversible circuit compilation tools adapted for use in a reversible circuit design and implementation process and implemented by one or more computing devices:
inputting a program describing a desired computation to be performed in a target reversible circuit architecture using bits;
generating a mutable data dependency graph from the program, the mutable data dependency graph describing nodes interconnected by edges, the nodes and the edges representing a flow of data along data paths as described by the program, the generating further comprising identifying and demarcating one or more of the data paths as being mutable data paths; and
storing the mutable data dependency graph.

### Claim 10 (depends on 9)

The method of claim 9, wherein the identifying and demarcating the one or more of the data paths as being mutable data paths is performed by (i) identifying a data path as being for a variable denoted in the program as being mutable, or (ii) recognizing a data path as being mutable based on a library of recognized operations.

### Claim 11 (depends on 9)

The method of claim 9, further comprising, based on the mutable data paths of the mutable data dependency graph, identifying one or more nodes that can be reset during the desired computation and cleaned-up without creating an adverse data dependency in any other node.

### Claim 12 (depends on 9)

The method of claim 9, further comprising generating a reversible circuit description from the mutable data dependency graph, the generating comprising adding circuit operations that reset and clean-up one or more bits corresponding respectively to the one or more nodes identified.

### Claim 13 (depends on 12)

The method of claim 12, wherein the generating is performed such that: (a) at least some of the circuit operations that reset and clean-up the one or more bits are performed prior to completion of all operations described by the program; (b) at least some of the circuit operations that reset and clean-up the one or more bits are performed after results from the computation are copied out and after completion of all operations described by the program; (c) at least some of the circuit operations that reset and clean-up the one or more bits are performed as soon as the one or more bits are no longer needed for their original operation; (d) the adding of the circuit operations that reset and clean-up the one or more bits is triggered by a determination that an available number of bits in a target reversible circuit architecture satisfies a threshold value; (e) at least some of the circuit operations that reset and clean-up the one or more bits are performed at function boundaries of the high-level description; or (f) at least some of the circuit operations that reset and clean-up the one or more bits are performed based on a space-time tradeoff analysis for the program as constrained by an available number of bits in a target reversible circuit.

### Claim 14 (depends on 9)

The method of claim 9, further comprising implementing the reversible circuit description in the target reversible circuit architecture.

### Claim 15

(canceled)

### Claim 16

One or more tangible computer-readable memory or storage devices storing computer-executable instructions which when executed by a computer cause the computer to perform a space-aware reversible-circuit synthesis procedure, the computer-executable instructions comprising:
instructions that cause the computer to input a program describing a desired computation to be performed in a target reversible circuit architecture using bits; and
instructions that cause the computer to generate a mutable data dependency graph from the program, the mutable data dependency graph describing nodes interconnected by edges, the nodes and the edges representing a flow of data along data paths as described by the program, the generation further comprising identifying and demarcating one or more of the data paths as being mutable data paths.

### Claim 17 (depends on 16)

The one or more tangible computer-readable memory or storage devices of claim 16, wherein the identifying and demarcating the one or more of the data paths as being mutable data paths is performed by (i) identifying a data path as being for a variable denoted in the program as being mutable, or (ii) recognizing a data path as being mutable based on a library of recognized operations.

### Claim 18 (depends on 16)

The one or more tangible computer-readable memory or storage devices of claim 16, further comprising computer-executable instructions that cause the computer to, based on the mutable data paths of the mutable data dependency graph, identify one or more nodes that can be reset during the desired computation and cleaned-up without creating an adverse data dependency in any other node.

### Claim 19 (depends on 16)

The one or more tangible computer-readable memory or storage devices of claim 16, further comprising computer-executable instructions that cause the computer to generate a reversible circuit description from the mutable data dependency graph, the generation comprising adding circuit operations that reset and clean-up one or more bits corresponding respectively to the one or more nodes identified.

### Claim 20 (depends on 19)

The one or more tangible computer-readable memory or storage devices of claim 19, wherein the generation is performed such that: (a) at least some of the circuit operations that reset and clean-up the one or more bits are performed prior to completion of all operations described by the program; (b) at least some of the circuit operations that reset and clean-up the one or more bits are performed after results from the computation are copied out and after completion of all operations described by the program; (c) at least some of the circuit operations that reset and clean-up the one or more bits are performed as soon as the one or more bits are no longer needed for their original operation; (d) the adding of the circuit operations that reset and clean-up the one or more bits is triggered by a determination that an available number of bits in a target reversible circuit architecture satisfies a threshold value; (e) at least some of the circuit operations that reset and clean-up the one or more bits are performed at function boundaries of the high-level description; or (f) at least some of the circuit operations that reset and clean-up the one or more bits are performed based on a space-time tradeoff analysis for the program as constrained by an available number of bits in a target reversible circuit.

### Claim 21 (depends on 16)

The one or more tangible computer-readable memory or storage devices of claim 16, further comprising computer-executable instructions that cause the computer to implement the reversible circuit description in the target reversible circuit architecture.

### Claim 22 (depends on 16)

A system comprising:
a classical computer comprising:
at least one classical processing unit adapted to execute the computer-executable instructions;
memory; and
the one or more tangible computer-readable memory or storage devices of claim 16.

### Claim 23 (depends on 22)

The system of claim 22, further comprising:
at least one quantum processing unit adapted to implement the target reversible circuit architecture, the quantum processing unit being further adapted to perform the desired computation.

### Claim 24

A method, comprising:
by one or more specialized reversible circuit compilation tools adapted for use in a reversible circuit design and implementation process and implemented by one or more computing devices:
inputting a program describing a desired computation to be performed in a target reversible circuit architecture using bits;
generating a mutable data dependency graph from the program, the mutable data dependency graph describing nodes interconnected by edges, the nodes and the edges representing a flow of data along data paths as described by the program, the generating further comprising identifying and demarcating one or more of the data paths as being mutable data paths; and
based on the mutual data dependency graph, generating a reversible circuit description.

### Claim 25 (depends on 24)

The method of claim 24, further comprising:
programming at least one quantum processing unit to implement the target reversible circuit architecture, the quantum processing unit being further adapted to perform the desired computation.

### Claim 26 (depends on 25)

The method of claim 25, wherein the at least one quantum processing unit is at least one of: (a) a superconducting quantum computer, (b) an ion trap quantum computer, or (c) a fault-tolerant architecture for quantum computing.

### Claim 27 (depends on 24)

The method of claim 24, further comprising optimizing the mutual data dependency graph to remove an unused code portion.

### Claim 28 (depends on 24)

The method of claim 24, further comprising storing the reversible circuit description in a computer-readable storage device or memory.
