# Efficient Synthesis of Linear Reversible Circuits

@article{Patel2003EfficientSO, title={Efficient Synthesis of Linear Reversible Circuits}, author={Ketan N. Patel and Igor L. Markov and John Patrick Hayes}, journal={arXiv: Quantum Physics}, year={2003} }

In this paper we consider circuit synthesis for n-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with O(n^2) gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as O(n^2/log n) gates.
We present an algorithm that is… Expand

#### 27 Citations

Scalable Simplification of Reversible Circuits

Reversible logic circuit synthesis has applications in various modern computational problems, low power design, and quantum circuit synthesis. Several algorithms for synthesis and simplification of… Expand

Efficient reversible and quantum implementations of symmetric Boolean functions

- Mathematics
- 2006

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,… Expand

Using Reed-Muller Expansions in the Synthesis and Optimization of Boolean Quantum Circuits

- Computer Science
- 2018

The chapter shows that there is a direct correspondence between Boolean quantum operations and the classical Reed-Muller expansions, which makes it possible for the problem of synthesis and optimization of Boolean quantum circuits to be tackled within the domain of Reed-muller logic under manufacturing constraints. Expand

Tight Bounds on the Synthesis of 3-Bit Reversible Circuits: Nffr Library

- Mathematics, Computer Science
- J. Circuits Syst. Comput.
- 2014

The reversible circuit synthesis problem can be reduced to permutation group. This allows Schreier–Sims algorithm for the strong generating set-finding problem to be used to find tight bounds on the… Expand

Analysis and Improvement of Transformation-Based Reversible Logic Synthesis

- Mathematics, Computer Science
- 2013 IEEE 43rd International Symposium on Multiple-Valued Logic
- 2013

Two novel techniques to the transformation-based synthesis flow for improving synthesis outcome are suggested, based on properties of Boolean functions and generalized Fredkin gates during synthesis flow. Expand

SAT-based {CNOT, T} Quantum Circuit Synthesis

- Computer Science
- RC
- 2018

This work has developed an exact SAT-based algorithm for quantum circuit rewriting that aims at reducing CNOT gates without increasing the number of T gates and finds the minimum {CNOT, T} circuit for a given phase polynomial description of a unitary transformation. Expand

Detection and Elimination of Non-Trivial Reversible Identities

- Physics, Mathematics
- 2012

AbstractNon-Trivial Reversible Identities (NTRIs) are reversible circuits that have equal inputs and outputs.NTRIs cannot be detected using optimization algorithms in the literature. Existence of… Expand

Resource optimization for fault-tolerant quantum computing

- Mathematics, Computer Science
- 2013

This thesis shows how to simplify universal encoded computation by using only transversal gates and standard error correction procedures, circumventing existing no-go theorems and finds that by using a special class of non-deterministic circuits, the cost of decomposition can be reduced by as much as a factor of four over state-of-the-art techniques, which typically use deterministic circuits. Expand

A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits

- Mathematics, Computer Science
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- 2013

We present an algorithm for computing depth-optimal decompositions of logical operations, leveraging a meet-in-the-middle technique to provide a significant speedup over simple brute force… Expand

An arbitrary twoqubit computation In 23 elementary gates or less

- Mathematics, Computer Science
- DAC
- 2003

This work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits, and constructively proves a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Expand

#### References

SHOWING 1-10 OF 11 REFERENCES

Reversible logic circuit synthesis

- Computer Science, Physics
- IWLS
- 2002

In an application important to quantum computing, oracle circuits for Grover's search algorithm are synthesized, and a significant improvement over a previously proposed synthesis algorithm is shown. Expand

A General Decomposition for Reversible Logic

- Mathematics
- 2001

Logic synthesis for reversible logic differs considerably from standard logic synthesis. The gates are multi-output and the unutilized outputs from these gates are called “garbage”. One of the… Expand

Elementary gates for quantum computation.

- Physics, Medicine
- Physical review. A, Atomic, molecular, and optical physics
- 1995

U(2) gates are derived, which derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number of unitary operations on arbitrarily many bits. Expand

Two-bit gates are universal for quantum computation.

- Physics, Medicine
- Physical review. A, Atomic, molecular, and optical physics
- 1995

A proof is given, which relies on the commutator algebra of the unitary Lie groups, that quantum gates operating on just two bits at a time are sufficient to construct a general quantum circuit. The… Expand

Quantum Algorithms: Applicable Algebra and Quantum Physics

- Mathematics
- 2001

Classical computer science relies on the concept of Turing machines as a unifying model of universal computation. According to the modern Church-Turing Thesis, this concept is interpreted in the form… Expand

Reducing quantum computations to elementary unitary operations

- Mathematics, Computer Science
- Comput. Sci. Eng.
- 2001

Standard techniques from numerical linear algebra can be used to represent quantum computations as sequences of simple quantum operations, called quantum Givens operators, on single quantum bits. Expand

Numerical recipes in C

- Computer Science
- 2002

The Diskette v 2.06, 3.5''[1.44M] for IBM PC, PS/2 and compatibles [DOS] Reference Record created on 2004-09-07, modified on 2016-08-08. Expand

Elementary gates for quantum c o putation.Physical

- 1995

Faradˇ zev. On economical construction of the transitive closure of an oriented graph

- Soviet Mathematics Doklady,
- 1970

On economical construction of the transitive closure of an oriented graph

- Soviet Mathematics Doklady
- 1970