|
Theoretical foundations of computer science
Synthesis of quantum circuits based on incompletely specified functions and if-decision diagrams
A. A. Prihozhy Belarusian National Technical University, 65 Niezaliežnasci Avenue, Minsk 220013, Belarus
Abstract:
The problem of synthesis and optimisation of logical reversible and quantum circuits from functional descriptions
represented as decision diagrams is considered. It is one of the key problems being solved with the aim of creating quantum computing technology and quantum computers. A new method of stepwise transformation of the initial functiona specification to a quantum circuit is proposed, which provides for the following project states: reduced ordered binary decision diagram, if-decision diagram, functional if-decision diagram, reversible circuit and quantum circuit. The novelty of the method consists in extending the Shannon and Davio expansions of a Boolean function on a single variable to the expansions of the same Boolean function on another function with obtaining decomposition products that are represented
by incompletely defined Boolean functions. Uncertainty in the decomposition products gives remarkable opportunities for
minimising the graph representation of the specified function. Instead of two outgoing branches of the binary diagram vertex, three outgoing branches of the if-diagram vertex are generated, which increase the level of parallelism in reversible and quantum circuits. For each transformation step, appropriate mapping rules are proposed that reduce the number of lines, gates and the depth of the reversible and quantum circuit. The comparison of new results with the results given by the known method of mapping the vertices of binary decision diagram into cascades of reversible and quantum gates shows a significant improvement in the quality of quantum circuits that are synthesised by the proposed method.
Keywords:
reversible computation; quantum logic circuit; synthesis; incompletely specified function; expansion of function; decision diagram; circuit size; circuit depth; minimisation.
Received: 19.10.2021 Revised: 21.10.2021 Accepted: 29.10.2021
Citation:
A. A. Prihozhy, “Synthesis of quantum circuits based on incompletely specified functions and if-decision diagrams”, Journal of the Belarusian State University. Mathematics and Informatics, 3 (2021), 84–97
Linking options:
https://www.mathnet.ru/eng/bgumi19 https://www.mathnet.ru/eng/bgumi/v3/p84
|
|