System for reversible circuit compilation with space constraint, method and program

Patent metadata

Field	Value
Publication number	US-10860759-B2
Application number	US-201615735102-A
Country	US
Kind code	B2
Filing date	Jun 7, 2016
Priority date	Jun 8, 2015
Publication date	Dec 8, 2020
Grant date	Dec 8, 2020

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.

First claim

The invention claimed is:

1. A reversible circuit compilation system, comprising:
a memory; and
a reversible circuit compiler, the reversible circuit compiler being configured to:
input, into the memory, a program describing a desired computation to be performed in a target reversible circuit architecture using bits,
transform the program into a reversible circuit description specifying one or more reversible gates that use the bits to achieve the desired computation, and
store, in the memory, the reversible circuit description,

the reversible circuit compiler being further configured to, as part of the transformation of the program into the reversible circuit description:
identify one or more bits of the target reversible circuit architecture that can be re-used by the target reversible circuit architecture during performance of the desired computation, and
modify the reversible circuit description such that the identified bits are reset to their original state prior to completion of the desired computation, thereby cleaning up the identified bits for re-use for other operations within the desired computation described by the program.

2. The reversible circuit compilation system of claim 1 , wherein the reversible circuit compiler is further configured to, as part of the transformation of the program into the reversible circuit description, generate a mutable data dependency graph having nodes and edges that describe control flow and data dependencies of the variables and expressions in the program, the mutable data dependency graph further including indicators that identify one or more mutable data paths, the mutable data dependency graph being stored as a data structure in the memory, and
wherein the reversible circuit compiler is configured to identify the one or more bits that can be reset from the mutable data dependency graph and from the indicators that identify the one or more of the mutable data paths.

3. The reversible circuit compilation system of claim 1 , wherein the reversible circuit compiler is further configured to identify one or more of the bits of the target reversible circuit architecture that can be reset to their original state prior to completion of the desired computation, the identifying being triggered by satisfaction of one or more criteria that are monitored during compilation.

4. The reversible circuit compilation system of claim 1 , wherein all possible bits of the target reversible circuit architecture that can be reset to their original state during performance of the desired computation are identified and cleaned up by the reversible circuit compiler.

5. The reversible circuit compilation system of claim 1 , further comprising a heap data structure stored in the memory, the heap data structure storing data identifying bits of the target reversible circuit architecture currently available to the reversible circuit compiler, and wherein the reversible circuit compiler is configured to return one or more bits for re-use to the heap data structure as the transformation of the program into the reversible circuit description performed by the reversible circuit compiler proceeds.

6. The reversible circuit compilation system of claim 1 , wherein the reversible circuit description specifies the one or more reversible gates as a sequence of one or more NOT gates, CNOT gates, Toffoli gates, Fredkin gates, Kerntopf gates, or multiply controlled gates.

7. The reversible circuit compilation system of claim 1 , further comprising a reversible circuit controller coupled to the target reversible circuit architecture and configured to implement the reversible circuit description in the target reversible circuit architecture.

8. The reversible circuit compilation system of claim 1 , wherein the target reversible circuit architecture is a target quantum computer, wherein the reversible circuit description is a quantum computer circuit description, wherein the bits are qubits, and wherein the modification of the reversible circuit description comprises modifying the quantum computer circuit description such that operations performed with the identified qubits are reversed prior to completion of the desired computation, thereby cleaning up the identified qubits for re-use for the other operations within the desired computation described by the program.

9. 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 comprising:
inputting a high-level description of a computational process to be performed in a target reversible circuit architecture, the computational process described by the high-level description comprising a sequence of operations that together perform the computational process;
performing a reversible circuit synthesis process to generate a reversible circuit description from the high-level description, the reversible circuit description specifying a sequence of reversible gates arranged to perform the sequence of operations using bits in the target reversible circuit architecture,
evaluating a total number of bits used by the reversible circuit description relative to total a number of bits available in the target reversible circuit architecture; and
outputting an indication of whether the total number of bits used by the reversible circuit description exceeds the total number of bits available in the target reversible circuit architecture.

10. 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 comprising:
inputting a program describing a desired computation to be performed in a target reversible circuit architecture using bits;
transforming the program into a reversible circuit description specifying one or more reversible gates that use the bits to achieve the desired computation; and
storing the reversible circuit description,
wherein the transforming further comprises:
identifying one or more bits of the target reversible circuit architecture that can be re-used by the target reversible circuit architecture during performance of the desired computation, and
modifying the reversible circuit description such that the identified bits are reset to their original state prior to completion of the desired computation, thereby cleaning up the identified bits for re-use for other operations within the desired computation described by the program.

11. The one or more tangible computer-readable memory or storage devices of claim 10 , wherein the space-aware reversible-circuit synthesis procedure further comprises:
generating a mutable data dependency graph having nodes and edges that describe control flow and data dependencies of the variables and expressions in the program, the mutable data dependency graph further including indicators that identify one or more mutable data paths, and
identifying the one or more bits that can be reset from the mutable data dependency graph and from the indicators that identify the one or more of the mutable data paths.

12. The one or more tangible computer-readable memory or storage devices of claim 10 , wherein the space-aware reversible-circuit synthesis procedure further comprises:
identifying one or more of the bits of the target reversible circuit architecture that can be reset to their original state prior to completion of the desired computation, the identifying being triggered by satisfaction of one or more criteria that are monitored during compilation.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Roetteler Martin
• Svore Krysta
• Parent Alex

Classifications

• G06F30/327 Primary

  Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist · CPC title

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• G09C1/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) · CPC title

• G06N10/00

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title