Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

CLE e-Prints

A Paraconsistent Approach to Quantum Computing

Juan C. Agudelo, Walter Alexandre Carnielli

Published Feb 1, 2008• 0 citations
OpenAlex

Abstract

We propose a method to define axiomatic theories for deterministic Turing machine computations. This method, when applied to axiomatizing computations in non-deterministic Turing machines, produces (in some cases) contradictory theories, therefore trivial theories (considering classical logic as the underlying logic). Substituting in such theories the underlying logic by the paraconsistent logic LFI1∗ permits us to define a new model of computation which we call paraconsistent Turing machine. We show that this initial model of computation allows the simulation of important quantum computing features. In particular, it allows to simulate the quantum solution of the well-known Deutsch’s and Deutsch-Jozsa problems. However, we show that this initial model of computation does not adequately represent the notion of entangled states, a key feature in quantum computing. In this way, the construction is refined by defining a paraconsistent logic with a connective expressing entangled states in a logical fashion, and this logic is used to define a more sharpened model of paraconsistent Turing machines, better approaching the quantum computing features. Finally, we define complexity classes for the models introduced and establish some surprising relationships with classical complexity classes.

Related papers

Paraconsistent Machines and their Relation to Quantum Computing

Juan C. Agudelo, Walter Alexandre Carnielli

We describe a method to axiomatize computations in deterministic Turing machines (TMs). When applied to computations in non-deterministic TMs, this method may produce contradictory (and therefore trivial) theories, considering classical logic as the underlying logic. By substituting in such theories the underlying logic by a paraconsistent logic we define a new computation model, the paraconsistent Turing machine. This model allows a partial simulation of superposed states of quantum computing. Such a feature allows the definition of paraconsistent algorithms which solve (with some restrictions) the well-known Deutsch's and Deutsch-Jozsa problems. This first model of computation, however, does not adequately represent the notions of entangled states and relative phase, which are key features in quantum computing. In this way, a more sharpened model of paraconsistent TMs is defined, which better approaches quantum computing features. Finally, we define complexity classes for such models, and establish some relationships with classical complexity classes.

arXiv:0802.0150•Journal of Logic and Computation•Nov 10, 2009•20 citations

Quantum Algorithms, Paraconsistent Computation and Deutsch's Problem.

Juan C. Agudelo, Walter Alexandre Carnielli

We present the new model of paraconsistent Turing machines and revise the models of quantum Turing machines and quantum circuits, stressing the concepts of entangled states and quantum parallelism which are important features for efficient quantum algorithms. We revise a quantum circuit that solves the so-called Deutsch’s problem, and then provide another solution to Deutsch’s problem by means of paraconsistent Turing machines. This raises some stimulating questions, and we close the paper by discussing some relationships between paraconsistent Turing machines and quantum Turing machines.

Indian International Conference on Artificial Intelligence•Jan 1, 2005•5 citations

Quantum Algorithms, Paraconsistent Computation and Deutsch's Problem

We present the new model of paraconsistent Turing machines and revise the models of quantum Turing machines and quantum circuits, stressing the concepts of entangled states and quantum parallelism which are important features for efficient quantum algorithms. We revise a quantum circuit that solves the so-called Deutsch's problem, and then provide another solution to Deutsch's problem by means of paraconsistent Turing machines. This raises some stimulating questions, and we close the paper by discussing some relationships between paraconsistent Turing machines and quantum Turing machines.

CLE e-Prints•Dec 10, 2005•0 citations

Quantum complexity theory

Ethan Bernstein, Umesh V. Vazirani

Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1993•1,413 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

SIAM Journal on Computing•Oct 1, 1997•1,635 citations

Computational Power of the Quantum Turing Automata

Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri +1 more

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future

•Apr 1, 2007•0 citations
We propose a method to define axiomatic theories for deterministic Turing machine computations. This method, when applied to axiomatizing computations in non-deterministic Turing machines, produces (in some cases) contradictory theories, therefore trivial theories (considering classical logic as the underlying logic). Substituting in such theories the underlying logic by the paraconsistent logic LFI1∗ permits us to define a new model of computation which we call paraconsistent Turing machine. We show that this initial model of computation allows the simulation of important quantum computing features. In particular, it allows to simulate the quantum solution of the well-known Deutsch’s and Deutsch-Jozsa problems. However, we show that this initial model of computation does not adequately represent the notion of entangled states, a key feature in quantum computing. In this way, the construction is refined by defining a paraconsistent logic with a connective expressing entangled states in a logical fashion, and this logic is used to define a more sharpened model of paraconsistent Turing machines, better approaching the quantum computing features. Finally, we define complexity classes for the models introduced and establish some surprising relationships with classical complexity classes.
We describe a method to axiomatize computations in deterministic Turing machines (TMs). When applied to computations in non-deterministic TMs, this method may produce contradictory (and therefore trivial) theories, considering classical logic as the underlying logic. By substituting in such theories the underlying logic by a paraconsistent logic we define a new computation model, the paraconsistent Turing machine. This model allows a partial simulation of superposed states of quantum computing. Such a feature allows the definition of paraconsistent algorithms which solve (with some restrictions) the well-known Deutsch's and Deutsch-Jozsa problems. This first model of computation, however, does not adequately represent the notions of entangled states and relative phase, which are key features in quantum computing. In this way, a more sharpened model of paraconsistent TMs is defined, which better approaches quantum computing features. Finally, we define complexity classes for such models, and establish some relationships with classical complexity classes.
We present the new model of paraconsistent Turing machines and revise the models of quantum Turing machines and quantum circuits, stressing the concepts of entangled states and quantum parallelism which are important features for efficient quantum algorithms. We revise a quantum circuit that solves the so-called Deutsch’s problem, and then provide another solution to Deutsch’s problem by means of paraconsistent Turing machines. This raises some stimulating questions, and we close the paper by discussing some relationships between paraconsistent Turing machines and quantum Turing machines.
We present the new model of paraconsistent Turing machines and revise the models of quantum Turing machines and quantum circuits, stressing the concepts of entangled states and quantum parallelism which are important features for efficient quantum algorithms. We revise a quantum circuit that solves the so-called Deutsch's problem, and then provide another solution to Deutsch's problem by means of paraconsistent Turing machines. This raises some stimulating questions, and we close the paper by discussing some relationships between paraconsistent Turing machines and quantum Turing machines.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future