Elementary gates for quantum computation
Citations Over TimeTop 1% of 1995 papers
Abstract
We show that a set of gates that consists of all one-bit quantum gates [U(2)] and the two-bit exclusive-OR gate [that maps Boolean values (x,y) to (x,x\ensuremath{\bigoplus}y)] is universal in the sense that all unitary operations on arbitrarily many bits n [U(${2}^{\mathit{n}}$)] can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical and of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We 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 required for arbitrary n-bit unitary operations.
Related Papers
- → Improving the Realization of Multiple-Control Toffoli Gates Using the NCVW Quantum Gate Library(2016)10 cited
- → Complexity of reversible circuits and their quantum implementations(2016)18 cited
- → New Structural Quantum Circuit Simulating a Toffoli Gate(2005)2 cited
- → Synthesis of Linear Reversible Circuits and EXOR-AND-based Circuits for Incompletely Specified Multi-Output Functions(2017)
- → Synthesis of Linear Reversible Circuits and EXOR-AND-based Circuits for Incompletely Specified Multi-Output Functions(2000)