Bridging Classical Logic and Quantum Computation Through Contradictory Reasoning

Abstract

This paper exemplifies the use of a novel semantic framework for first-order logic, informed by quantum mechanics and designed to capture some of the nuances of quantum computation. We demonstrate that, for key quantum procedures—concretely the Deutsch algorithm and the 2-gate decomposition of the Toffoli gate—there exist formulas that, despite being inconsistent in classical terms, partially describe algorithmic behaviour and exhibit unique non-classical consistency features. Moreover, we briefly discuss how the approach illustrated in this article would need to be elaborated to deal with other key algorithms such as the Deutsch–Jozsa algorithm and the Phase Estimation algorithm.
An implication of our findings is the possibility that embracing contradictions might be useful for innovation in quantum algorithm design.