Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Nanotechnology (IEEE-NANO)

Progress towards constructing sequences of benchmarks for quantum Boolean circuits synthesis

Jerzy Jegier, Paweł Kerntopf

Published Aug 1, 2014• 3 citations
Publisher

Abstract

In this paper, a method for constructing sequences of reversible functions of large number of variables is presented. First, by using our database of all minimal reversible circuits for 3-variable reversible functions, and our tool for designing minimal circuits for 4-variable reversible functions, circuits with structural regularities are searched for. The aim is to find a pair, 3- and 4-variable functions, having similar permutation cycle structures, for which there exist minimal circuits with the same kind of structural regularity. After finding such a pair we are extrapolating the selected structural regularities to circuits of higher number of inputs. Then, cycle structure properties of the functions implemented by the extrapolated circuits are checked for similarity to the previously found pair. In this way, we have found many sequences of reversible functions having similar properties. The approach is promising for constructing benchmarks of large size for which minimal or nearly minimal circuits are known.

DOI
10.1109/nano.2014.6967983

Related papers

An approach to constructing reversible multi-qubit benchmarks with provably minimal implementations

Jerzy Jegier, Paweł Kerntopf, Marek Szyprowski

This paper reports on a method of the construction of new difficult benchmarks for reversible logic synthesis. It is shown how to extrapolate 3- and 4-variable reversible functions implemented by gate count minimal circuits having regular structure. In this way sequences of reversible functions of an arbitrary number of variables have been constructed for which we have built minimal circuits implementing them. For two example sequences of functions we applied the synthesis tool Revkit trying different synthesis algorithms. The outcome shows a large gap between the circuits synthesized by the tool and the ones proved minimal by construction.

IEEE International Conference on Nanotechnology (IEEE-NANO)•Aug 1, 2013•7 citations

Efficient reversible and quantum implementations of symmetric Boolean functions

D. Maslov

It is a well-known fact in logic design that synthesis of some special classes of Boolean functions is often easier than the synthesis of a general unrestricted specification. In reversible logic, well-scaled synthesis methods with a reasonably small cost of the associated implementation have been found for only a few classes of functions. This includes synthesis of multiple-output symmetric and reversible linear functions. The author presents an efficient reversible/quantum synthesis method for the class of multiple-output symmetric functions. The method is purely theoretical, therefore its scaling on functions with a large number of inputs/outputs requires minimal resources. The author calculates garbage, i.e. the number of outputs that are not required by the function specification, the number of reversible gates, and the quantum cost of the presented implementations. The proposed approach is then applied to the synthesis of benchmark functions. Comparison of the designs to the previously reported implementations is favourable.

IEE Proceedings - Circuits Devices and Systems•Jan 1, 2006•17 citations

Synthesis of reversible circuits with minimal lines for large functions

Mathias Soeken, Robert Wille, Christoph Hilken +2 more

Reversible circuits are an emerging technology where all computations are performed in an invertible manner. Motivated by their promising applications, e.g. in the domain of quantum computation or in the low-power design, the synthesis of such circuits has been intensely studied. However, how to automatically realize reversible circuits with the minimal number of lines for large functions is an open research problem. In this paper, we propose a new synthesis approach which relies on concepts that are complementary to existing ones. While “conventional” function representations have been applied for synthesis so far (such as truth tables, ESOPs, BDDs), we exploit Quantum Multiple-valued Decision Diagrams (QMDDs) for this purpose. An algorithm is presented that performs transformations on this data-structure eventually leading to the desired circuit. Experimental results show the novelty of the proposed approach through enabling automatic synthesis of large reversible functions with the minimal number of circuit lines. Furthermore, the quantum cost of the resulting circuits is reduced by 50% on average compared to an existing state-of-the-art synthesis method.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2012•104 citations

Synthesis of reversible logic circuits

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

arXiv:quant-ph/0207001•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 29, 2003•581 citations

Improving the mapping of reversible circuits to quantum circuits using multiple target lines

Robert Wille, Mathias Soeken, C. Otterstedt +1 more

The efficient synthesis of quantum circuits is an active research area. Since many of the known quantum algorithms include a large Boolean component (e.g. the database in the Grover search algorithm), quantum circuits are commonly synthesized in a two-stage approach. First, the desired function is realized as a reversible circuit making use of existing synthesis methods for this domain. Afterwards, each reversible gate is mapped to a functionally equivalent quantum gate cascade. In this paper, we propose an improved mapping of reversible circuits to quantum circuits which exploits a certain structure of many reversible circuits. In fact, it can be observed that reversible circuits are often composed of similar gates which only differ in the position of their target lines. We introduce an extension of reversible gates which allow multiple target lines in a single gate. This enables a significantly cheaper mapping to quantum circuits. Experiments show that considering multiple target lines leads to improvements of up to 85% in the resulting quantum cost.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2013•64 citations

Reversible logic circuit synthesis

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

International Conference on Computer Aided Design•Jun 25, 2003•69 citations
In this paper, a method for constructing sequences of reversible functions of large number of variables is presented. First, by using our database of all minimal reversible circuits for 3-variable reversible functions, and our tool for designing minimal circuits for 4-variable reversible functions, circuits with structural regularities are searched for. The aim is to find a pair, 3- and 4-variable functions, having similar permutation cycle structures, for which there exist minimal circuits with the same kind of structural regularity. After finding such a pair we are extrapolating the selected structural regularities to circuits of higher number of inputs. Then, cycle structure properties of the functions implemented by the extrapolated circuits are checked for similarity to the previously found pair. In this way, we have found many sequences of reversible functions having similar properties. The approach is promising for constructing benchmarks of large size for which minimal or nearly minimal circuits are known.
This paper reports on a method of the construction of new difficult benchmarks for reversible logic synthesis. It is shown how to extrapolate 3- and 4-variable reversible functions implemented by gate count minimal circuits having regular structure. In this way sequences of reversible functions of an arbitrary number of variables have been constructed for which we have built minimal circuits implementing them. For two example sequences of functions we applied the synthesis tool Revkit trying different synthesis algorithms. The outcome shows a large gap between the circuits synthesized by the tool and the ones proved minimal by construction.
It is a well-known fact in logic design that synthesis of some special classes of Boolean functions is often easier than the synthesis of a general unrestricted specification. In reversible logic, well-scaled synthesis methods with a reasonably small cost of the associated implementation have been found for only a few classes of functions. This includes synthesis of multiple-output symmetric and reversible linear functions. The author presents an efficient reversible/quantum synthesis method for the class of multiple-output symmetric functions. The method is purely theoretical, therefore its scaling on functions with a large number of inputs/outputs requires minimal resources. The author calculates garbage, i.e. the number of outputs that are not required by the function specification, the number of reversible gates, and the quantum cost of the presented implementations. The proposed approach is then applied to the synthesis of benchmark functions. Comparison of the designs to the previously reported implementations is favourable.
Reversible circuits are an emerging technology where all computations are performed in an invertible manner. Motivated by their promising applications, e.g. in the domain of quantum computation or in the low-power design, the synthesis of such circuits has been intensely studied. However, how to automatically realize reversible circuits with the minimal number of lines for large functions is an open research problem. In this paper, we propose a new synthesis approach which relies on concepts that are complementary to existing ones. While “conventional” function representations have been applied for synthesis so far (such as truth tables, ESOPs, BDDs), we exploit Quantum Multiple-valued Decision Diagrams (QMDDs) for this purpose. An algorithm is presented that performs transformations on this data-structure eventually leading to the desired circuit. Experimental results show the novelty of the proposed approach through enabling automatic synthesis of large reversible functions with the minimal number of circuit lines. Furthermore, the quantum cost of the resulting circuits is reduced by 50% on average compared to an existing state-of-the-art synthesis method.
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.
The efficient synthesis of quantum circuits is an active research area. Since many of the known quantum algorithms include a large Boolean component (e.g. the database in the Grover search algorithm), quantum circuits are commonly synthesized in a two-stage approach. First, the desired function is realized as a reversible circuit making use of existing synthesis methods for this domain. Afterwards, each reversible gate is mapped to a functionally equivalent quantum gate cascade. In this paper, we propose an improved mapping of reversible circuits to quantum circuits which exploits a certain structure of many reversible circuits. In fact, it can be observed that reversible circuits are often composed of similar gates which only differ in the position of their target lines. We introduce an extension of reversible gates which allow multiple target lines in a single gate. This enables a significantly cheaper mapping to quantum circuits. Experiments show that considering multiple target lines leads to improvements of up to 85% in the resulting quantum cost.
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.