Synthesis of Quantum Logic Circuits
| dc.creator | Shende, Vivek V. | |
| dc.creator | Bullock, Stephen S. | |
| dc.creator | Markov, Igor L. | |
| dc.date | 2004-06-23 | |
| dc.date | 2006-04-18 | |
| dc.date.accessioned | 2026-07-07T06:36:57Z | |
| dc.date.available | 2026-07-07T06:36:57Z | |
| dc.description | We discuss efficient quantum logic circuits which perform two tasks: (i) implementing generic quantum computations and (ii) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state-space of an n-qubit register is not finite and contains exponential superpositions of classical bit strings. Our proposed circuits are asymptotically optimal for respective tasks and improve published results by at least a factor of two. The circuits for generic quantum computation constructed by our algorithms are the most efficient known today in terms of the number of expensive gates (quantum controlled-NOTs). They are based on an analogue of the Shannon decomposition of Boolean functions and a new circuit block, quantum multiplexor, that generalizes several known constructions. A theoretical lower bound implies that our circuits cannot be improved by more than a factor of two. We additionally show how to accommodate the severe architectural limitation of using only nearest-neighbor gates that is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts. | |
| dc.description | 18 pages; v5 fixes minor bugs; v4 is a complete rewrite of v3, with 6x more content, a theory of quantum multiplexors and Quantum Shannon Decomposition. A key result on generic circuit synthesis has been improved to ~23/48*4^n CNOTs for n qubits | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0406176 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0406176 | |
| dc.identifier | IEEE Trans. on Computer-Aided Design, vol. 25, no. 6, June 2006, pp.1000 - 1010 | |
| dc.identifier | doi:10.1109/TCAD.2005.855930 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/100258 | |
| dc.subject | Quantum Physics | |
| dc.title | Synthesis of Quantum Logic Circuits | |
| dc.type | text |