# Question on the logic behind quantum computing

According to Wikipedia,

"Quantum computing studies theoretical computation systems (quantum computers) that make direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data.[1] Quantum computers are different from digital computers based on transistors. Whereas digital computers require data to be encoded into binary digits (bits), each of which is always in one of two definite states (0 or 1), quantum computation uses quantum bits (qubits), which can be in superpositions of states."

Which implies that in a Quantum computer a qubit can have the values 0 and 1 at the same time. With the help from Quantum mechanical phenomena such as entanglement and superposition.

But according to fundamental logic a statement can have only one truth value.

"The truth or falsity of a statement is known as it's truth value. For an expression to be a statement, it is not necessary that we actually know whether it is true or false, but it must clearly be the case that it is one or the other" -Analysis (Steven R.Lay)

With the facts being so, how can quantum computing be possible? Doesn't it violate basic logic? Or am I getting the whole thing wrong?

Also I thought this is the best SE to post my question as SEs regarding computing are not familiar with QM.

• propositional logic is not the only logic around. See for instance en.wikipedia.org/wiki/Fuzzy_logic
– user83548
Commented Sep 11, 2015 at 17:40
• Part of the confusion may arise from the fact that classical computers are overwhelmingly not being used to express the truth value of logical propositions but they are being used to approximate real numbers with IEEE floating points. While you can use a classical computer to prove logical statements, that's not their main application. Neither will it be the main application of quantum computers. We are still going to be mainly interested in calculating numerical approximations of problems. Commented Sep 11, 2015 at 17:55
• This link may go a long way toward answering your question: cds.cern.ch/record/383367/files/… Commented Sep 12, 2015 at 0:36
• @Ernie that seems to answer my question. I'll read the whole thing leisurely. Tnx :) Commented Sep 12, 2015 at 2:42

Here is the way I understand your question: quantum computers rely upon qubits, which can be 0 and 1 at the same time. You say that this violates logic, which states that it is preposterous for something to be both 0 and 1 at the same time--it must be one or the other. However, you should realize that the qubit only exists in a superposition of the 0 and 1 before we measure it--after we make a measurement, it has to assume 0 or 1, but never both. Therefore, we see that, after we make a measurement, it does not break the laws of logic--either we have a 1 (or 0), or we don't.

Before the measurement, however, it gets tricky. In this realm, quantum mechanics breaks logic--in particular, Bell's inequality. Let's say we have three two-valued properties: A, B, and C. We assume their properties are predetermined (even if we can't observe them) and the properties are local, i.e. they do not effect each other. Then the probability $P(X,Y)$ of finding the properties of $X$ identical to the properties of $Y$ is

$$P(A,B)+P(A,C)+P(B,C)\ge 1$$

A simple calculation can be done on a two-level quantum system that shows that Bell's inequality is violated. Thus, quantum mechanics breaks the laws of logic, and is a non-local theory: acting on one of the quantities A, B, or C will effect one of the other properties. In short, the nature of quantum mechanics itself, as a non-local theory, defies fundamental logical principles that we normally use to characterize our classically local world, and thus the components of a quantum computer will not follow that everyday world's logic. For an in-depth proof and discussion of Bell's inequality, look at this wonderful article by Lorenzo Maccone--some of the discussion about Bell's inequality is taken from this paper.

• Is it possible to construct a machine to conduct logical operations which itself do not obey? I'm a bit confused. Great answer though +1 Commented Sep 13, 2015 at 4:28
• @slhulk If we were to construct a quantum computer, I believe that it would have to follow modified laws of logic. See the following page for a discussion of this modified version of logic, known as quantum logic: en.wikipedia.org/wiki/Quantum_logic. Of course, what you are asking concerns quantum algorithms, a field which we know very little about. We have a search algorithm (Grover's algorithm), a factoring algorithm (Shor's algorithm), black-box algorithms and algorithms based on random walks. Little is known about quantum algorithms concerning logic, to the best of my knowledge. Commented Sep 14, 2015 at 2:25
• thnx for taking ur valuable time :) Commented Sep 14, 2015 at 5:39