System for reversible circuit compilation with space constraint, method and program
AssigneeMicrosoft Technology Licensing, LLC
InventorsMartin Roetteler, Krysta Svore, Alex Parent
Life of this patent
Estimating the term…
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.
Claims21
1-8. (canceled)
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.
(canceled)
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.
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.
Dependencies are inferred from the claim text.