Current-day electronic computers are not fundamentally different from purely mechanical computers: the operation of either can be described fully in terms of classical physics. By contrast, computers could in principle be built to profit from actual quantum phenomena that have no classical analogue, such as entanglement and interference, sometimes providing exponential speed-up compared with classical computers. Every quantum algorithm requires the implementation of a quantum oracle (logic circuit), whose function is to recognize solutions to a given problem. To completely exploit the "quantum parallelism," this oracle should be realized by using quantum gates because it must be able to handle an arbitrary superposition of basis vectors (quantum states.) A key problem is thus how to construct a minimum-cost realization of this kind of quantum logic circuit. This research focuses on the development of an efficient synthesis framework for quantum logic circuits. The proposed synthesis algorithm and flow can generate a quantum circuit using the most basic quantum operators, i.e., the rotation and controlled-rotation primitives in the Bloch Sphere Representation. More importantly, this work introduces the notion of quantum factored forms, and develops a canonical and concise representation of quantum logic circuits, called a quantum decision diagram (QDD). The QDDs are amenable to efficient manipulation and optimization including recursive unitary functional bidecomposition. Subsequently, an effective QDD-based algorithm is developed and applied to automatic synthesis of quantum logic circuits. If successful, this research will pave the way toward building quantum computing circuits and eventually systems. Its impacts can thus be broad and substantial.
