Some Problems and Methods in Formal Quantum Logic

François David

Ondrej Krídlo, Manuel Ojeda‐Aciego

Stanley Gudder

William N. N. Hung, Xiaoyu Song B, Guowu Yang +2 more

Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.

C. Piron

J. Jay Zeman

The non-classical nature of quantum theory has led to a number of efforts to formalize the logic of statements whose universe of discourse is the subatomic (see, for example, [3], [6], [8], and [10]).It might be hoped that ideally the fruit of such efforts would be a formalism not totally divorced from the classical logic, but incorporating or incorporated in it in such a manner as to unify the logic of the micro-and the macro-worlds.Indeed, this has been the general direction taken by these efforts, including that which we principally examine and expand upon here.*Josef Jauch, [6], pp.67-89, developed a "propositional calculus of quantum mechanics".He objected to calling a system like his a "logic of quantum mechanics"; however, our use of 'logic' here is not, I think, the use to which Jauch objected.A logic, for our present purposes, is a mathematical formalism having a reasonable interpretation as a theory of deduction; its actual application as normative of argumentation in reality is a matter of empirical judgment.This seems close to the way Jauch wished to use "propositional calculus" but more general, allowing for extension to a quantification theory of quantum mechanics, for example.Although Jauch's presentation of a propositional calculus of quantum mechanics is mathematically interesting and suggestive, there are a number of problems connected with it.It is our purpose to engage some of these problems and to present a rigorously defined formalism intended to come close to doing the job intended by Jauch for his logic.The success or lack of success of this effort as related to actual application of this formalism in the foundations of quantum theory is, I think, a matter for the physicists to decide; the empirical judgment involved in this application is not in the scope of this paper.If a formalism is to have a reasonable interpretation as a theory of deduction, it seems clear that it must include a relation which, when it holds between two elements of the formalism, may be reasonably interpreted as expressing that one of the elements 'follows from' the other, in •The author wishes to thank Robert Piziak for advice and comments in the course of research for this paper.