A METHODOLOGICAL ANALYSIS OF CIRCUIT-BASED QUANTUM AND REVERSIBLE COMPUTING

The present dissertation offers a perspective on the theory and methodologies of Quantum Computing, in particular of its common realization as a reversible circuit-based computing paradigm. Starting from the very beginning, the postulates of Quantum Mechanics, the dissertation focuses on the multifaceted formal tradition of Quantum Computing, and the interplay between the various mathematical aspects and the intuitive interpretations of Quantum. The main result of the present dissertation consists in on an in-depth treatment of Quantum and Reversible circuits as syntactic objects, presenting a categorial formalization of circuits and syntactic reductions on them, for which a termination result is proven. Lastly, the thesis ends with a presentation of some known Quantum Algorithms, and in particular the Approximate Quantum Algorithm, that offers a radically different perspective on circuit depth reductions as an alternative to formal reductions.