Article
Logical Structures Underlying Quantum Computing
Federico Holik1, Giuseppe Sergioli2 , Hector Freytes2and Angel Plastino1,* 1 Instituto de Fisica (IFLP-CCT-CONICET), Universidad Nacional de La Plata, C.C. 727,
1900 La Plata, Argentina; holik@fisica.unlp.edu.ar
2 Dipartimento di Pedagogia, Psicologia, Filosofia, Università di Cagliari, Via Is Mirrionis 1, 09123 Cagliari, Italy; giuseppe.sergioli@gmail.com (G.S.); hfreytes@gmail.com (H.F.) * Correspondence: angeloplastino@gmail.com
Received: 24 November 2018; Accepted: 12 January 2019; Published: 16 January 2019
Abstract: In this work we advance a generalization of quantum computational logics capable of dealing with some important examples of quantum algorithms. We outline an algebraic axiomatization of these structures.
Keywords:quantum computing; non-kolmogorovian probability; quantum computational gates
1. Introduction
Quantum computers are one of the main technological goals of our time [1] and many efforts are focused on their development. While some examples of quantum computers were actually built [2], they are still not strong enough to overcome their classical competitors: decoherence poses a threat to the problem of scaling up the number of qubits [1]. While difficult to implement, the results are promising, and a lot of interest revolves around the study of quantum algorithms both, from a theoretical standpoint and an empirical one as well. In this paper, we focus on the following problem: the characterization of the logical and algebraic structures underlying quantum algorithms. The characterization of these structures is of fundamental importance for understanding the peculiarities of quantum computation.
To describe quantum computation from a logical and algebraic point of view, many formalisms were developed (see for example [3–9]). We refer to the logics studied in these works as quantum computational logics (QCL). The QCL approach is based on the characterization of the action of quantum gates using probabilistic truth values (see also [6]).
In this work, we present a generalization of the QCL approach in which the truth values are extended to include arbitrary readings of the quantum register. This move allows us to represent quantum algorithms of practical interest in a natural way. We also generalize the QCL approach to a huge family of propositional systems, based on orthomodular lattices. Putting the emphasis in the propositional structure of the readouts of the quantum register allows for a better comparison with the classical case. Our generalization reveals that quantum computing can be considered as a non-Kolmogorovian version of classical non-deterministic computing, continuing the line of research proposed in [10]. From this perspective, the orthomodular lattice of projection operators of the Hilbert space is the essential algebraic structure. This lattice was termed quantum logic after the pioneer work of Birkhoff and von Neumann [11] (for a more recent approach, c.f. [12–15]). In the quantum case, the non-Kolmogorovian character of the probabilistic calculus involved, comes directly from the fact that there are complementary contexts in which measurements can be performed. We think that this is a very important point, because it opens the door to investigating the role of contextuality in QC in a more explicit and natural way. This is in harmony with recent studies that suggest that the essential resource allowing for the advantages of quantum computing is contextuality [16–20],
a physical phenomenon strongly related to the non-distributive character of the lattice of quantum propositions [21]. See also [22], for a discussion of the fundamental role played by the projective geometry of the Hilbert space in quantum algorithms. Another advantage of our generalization is that of knowing a canonical form of finding quantum versions of classical formalisms and algorithms.
Finally, our approach shows how to conceive alternative forms of non-classical computing. Indeed, the general scheme presented in this manuscript could be used to compare QC with other alternative theories. A comparison of this kind, could help us to understand better the nature of quantum computing. Notice also that our formalism can be of guide for defining algorithms in physical frameworks that go beyond standard quantum mechanics. Indeed, the rigorous formulation of quantum field theory and quantum statistical mechanics require factor von Neumann algebras that go beyond the standard Type I case [23], reflecting the fact that these are (from a technical standpoint) non-equivalent probabilistic theories. Our approach can be of use in the study of quantum computing in the limit of systems with infinitely many degrees of freedom.
The paper is organized as follows. In Section2we review some general aspects of classical computing to motivate our further developments and present the essential aspects of the different forms of computing in a schematic way. We present our generalization of quantum computational logic in Section3. Next, in Section4we review how concrete algorithms of interest in applications fall into our theoretical scheme. In Section5we provide the outline of an axiomatic framework for these logics, which contain classical and quantum computing as particular cases. We also discuss how these algebraic structures can be expressed in math-fashion. Finally, some conclusions are drawn in Section6.
2. Classical Computing
A classical computing machine is based on bits. The bit is the elementary unit for measuring information. A physical bit (a system with only two relevant states) can take two values 0 and 1. In general, information will be stored and processed in classical computers by appealing to physical bits and operations on them. In this Section we start by reviewing the notions of deterministic and non-deterministic classical computation. Next, we describe the essential aspects of some particular models of quantum computers.
2.1. Deterministic Classical Computing
Any function F : {0, 1}N −→ {0, 1}Mcan be expressed in terms of Boolean functions (see for example [24], Chapter 2). Define a Boolean function as a function F :{0, 1}N −→ {0, 1}. A Boolean circuit can be represented as a composition of elementary Boolean functions. In general, a basisA of elementary functions is taken as a generating set for all other Boolean functions. One of the most important examples is the choiceA1= {∨,∧,¬}, where
Definition 1. ∨:{0, 1}2−→ {0, 1}with ∨(0, 0) =0 ∨(0, 1) =1 ∨(1, 0) =1 ∨(1, 1) =1 ∧:{0, 1}2−→ {0, 1}with ∧(0, 0) =0 ∧(0, 1) =0 ∧(1, 0) =0 ∧(1, 1) =1
¬:{0, 1} −→ {0, 1}with
¬(0) =1 ¬(1) =0
Notice that the elements ofA1have different n-arity. Any Boolean function F :{0, 1}N−→ {0, 1} can be written as a composition of the elementary functions belonging toA1. Thus, the computation of F can be effected via a physical circuit made up physical representations of elementary Boolean functions (elementary classical gates). In other words, the hardware that allows us to compute the function F can be made up by electronic components representing the elementary functions∨,∧and ¬, combined in a suitable way. The generalization of Boolean functions to functions F :{0, 1}N −→ {0, 1}M(with M≥2) is straightforward (we refer the reader to [24] for details).
The problem of finding a suitable notion of equivalence between circuits is of major importance. In general, there is more than one way to represent a function F as a composition of elementary Boolean functions (and thus, very different hardware devices may compute exactly the same function). Given two functions F, G : {0, 1}N −→ {0, 1}M, how can we determine whether they are equal or not? Notice that similarly, we can ask if two circuits, implementing functions F and G, are essentially the same or not. This is equivalent to testing the proposition F=G. In the classical case, this can be solved in a trivial way by simply considering all possible inputs x∈ {0, 1}Nand checking whether the outputs F(x)and G(x)are equal or not. Equivalently, if we do not know the functions, but we have the hardware representing them, we can compare them in a similar way, by running the two circuits and comparing the outputs. Notice that this procedure is equivalent to computing truth values of the elementary functions: if we know the truth tables of all Boolean generators, we will be able to compute the outputs of any Boolean function.
Please note that there is still more structure involved in this comparison between F and G.{0, 1}N is a set, and the set of all its subsetsP ({0, 1}N)is a Boolean algebra (with the conjunction∧taken as set intersection, the disjunction∨as set union and the negation¬as the set theoretical complement). This is of major importance for understanding the extension to classical probabilistic computing and quantum computing. Let us discuss this with more detail. A rational agent whose function is to manage the readout of the register can only deal with (and communicate) truth values of the propositional structure defined by the power setP ({0, 1}N). In this sense, the logic associated with a classical computer is represented by a Boolean algebra.
2.2. Non-Deterministic Classical Computing
The introduction of probabilistic steps in a computation proves to be useful for solving many particular problems [24]. Indeed, the exact solution of some problems displays high computational complexity, but this complexity can be lowered if we allow for a low rate of errors in the computation.
However, if the steps of the computation are produced in a probabilistic way, the output of an input x∈ {0, 1}Mmust be described by a probabilistic function F
x:{0, 1}N−→ [0, 1]satisfying ∀x∈ {0, 1}M
∑y∈{0,1}NFx(y) =1 (1)
Here arises an important observation. In the previous Section, we showed that the propositional structure associated with a rational agent dealing with the register was exactly the Boolean algebra P ({0, 1}N). However, Equation (1) defines in a canonical way (for each x ∈ {0, 1}M) a Kolmogorovian probability distribution inP ({0, 1}N)as follows:
µFx :P ({0, 1}N) → [0, 1] such that:
1. µFx(∅) =0
2. µFx(Ac) =1−µFx(A)
3. For any disjoint X, Y∈ P ({0, 1}N)we have µFx(X
[
Y) =µFx(X) +µFx(Y)
Thus, the classical propositional structure of the register implies that there will be a classical probabilistic distribution for the propositions communicated by a rational agent dealing with the readouts.
2.3. Quantum Computing in a Schematic Way
Before we continue, it is useful to give some definitions. States of a quantum system can be represented by so-called density operators, which are positive and trace class self-adjoint operators of trace one, acting on a separable Hilbert spaceH. We callC(H)to the set of all density operators. A density operator ρ is said to be pure if ρ2 = ρand mixed otherwise. An operator U acting on a separable Hilbert space is said to be unitary iff UU† =U†U= 1(here, U†represents the adjoint of the operator U). Quantum gates will be represented by unitary operators. As is well known, if U is unitary, the mapE (ρ) =UρU†maps density operators into density operators.
Let us try to summarize how a quantum computer works. Suppose that our quantum hardware has N qubits. In this case, the Hilbert space isH = NN
C2. A basic general description of all the central operations needed to perform a quantum algorithm can be given as follows.
Step 1. Chose an initial state represented by a density operator ρ for the qubits (notice that ρ can be taken to be mixed [25]). This state could be just the density operator associated with the vector |0i ⊗ |0i ⊗ · · · ⊗ |0ior any other desired state. In most situations of practical interest, the computational basis plays a key role in defining the inputs and the outputs of the algorithm. Let us denote the computational basis by B0.
Step 2. Apply a collection of gates represented by unitary operators{Ui}i=1,...,nto reach a desired final state σ=Un· · ·U2U1ρU†1U2†· · ·U†n.
Step 3. Perform a measurement on the system when state σ is reached, check the result obtained, and depending on the result, stop the process, or continue following the pertinent protocol if necessary (which will involve a similar, or, in some cases, the same- process). Notice that the measurement process involves the choice of a measurement basis. This process has associated a probability (dictated by Born’s rule). The probability of success for an algorithm is related to the probability of occurrence of a certain outcome (or collection of them). This outcome should be of interest for the successful computation involved in the protocol that one is following. Notice that a subspace containing the desired results always exists. The pertinent probability of success is related to the probability for the event of interest to happen.
It is illustrative to compare now the possible readouts of a rational agent R dealing with a quantum computer. Like in the classical probabilistic case, the possible observations are not restricted to the computational basis B0. Notice that B0defines a Boolean algebra of operators in a canonical way as follows. First, consider the set P0of all possible orthogonal projection operators corresponding to the elements of B0. The commutant of a set C of bounded operators acting on a Hilbert space is defined as C0 := {x ∈ B(H) | [x, y] = 0∀y ∈ C}. The double commutant of C is defined as(C0)0. Now, take the double commutant of P0to define the setPB0 := (P0)
00. It is easy to check thatP
B0 := (P0)
00 is a Boolean algebra. The projection operators inPB0 form the propositional structure associated
with the computational basis. However, as in the classical case, the measurements of the rational agent will not be generally restricted, to this set of propositions. Indeed, by applying rotations on the output state, R can measure other properties associated with the final quantum state. In case that, due to restrictions in the hardware, the readouts are only performed on the computational basis, a measurement in a different basis can be implemented by a rotation U applied on the quantum state
(using the equivalence Tr(ρU†PU) =Tr(UρU†P)). As it is well known, the set of possible propositions to be tested is formed by the setP (H)of all orthogonal projection operators acting inH. The collection P (H)is a modular non-distributive lattice for finite dimensional Hilbert spaces and an orthomodular one for infinite dimensional ones. The final quantum state—represented by the density operator σ—defines a quantum probability distribution
Pσ :P (H) −→ [0, 1]
given by Pσ(P) =Tr(σP)for all P∈ P (H). It possesses the following properties:
1 Pσ(0) =0 (0 is the null operator).
2 Pσ(P⊥) =1−Pσ(P), for all P∈ P (H).
3 For any family(Pj)j∈J ⊂ P (H)consisting of orthogonal projections for which Pj1Pj2 =0when
j16=j2, the following equality holds: Pσ(
_
Pj) =
∑
j∈JPσ(Pj).
Observe that, since the Hilbert spaceHis supposed to be separable, the family may be taken to be finite or countable. Notice also that the equality P∨Q+P∧Q=P+Q is true provided PQ=QP=P∧Q. Here the operations P∨Q and P∧Q are appropriately defined within the W∗-algebra (or von Neumann algebra) under discussion. In case that this W∗-algebra coincides withB(H), i.e., the algebra of all bounded linear operators on the Hilbert spaceH, then the operator P∧Q is the orthogonal projection on the subspace PH ∩QH, and P∨Q is the orthogonal projection on the closure of the subspace PH +QH. Of course, similar equalities hold for families of commuting orthogonal projections. We always have P⊥ =1−P
While the properties of a quantum probability distribution may resemble the properties of a Kolmogorovian one, there is a radical difference. The probability distribution associated with a classical probabilistic algorithm is defined in a Boolean algebra, but the probability distribution associated with a quantum one is defined in an orthomodular lattice [26]. The differences between these probability theories has been extensively studied in the literature (see for example [12,23,27]). For more discussion on this subject see [28–30], where the authors propose applications of non-Kolmogorovian probability theory outside of the quantum domain.
3. Logics Associated with Quantum Algorithms
In this Section we introduce our proposal for generalizing quantum computational logics. We start with the characterization of compositional gates and end up with a generalization of probabilistic truth values. 3.1. The Algebraic Structure of Quantum Logical Gates
In a real quantum computer, a general quantum gate is constructed by adequately composing elementary ones. In theoretical quantum computing, certain sets of universal gates are used. As examples, we can take the quantum Toffoli and the Hadamard gates [31]; another example is given by CNOT, Hadamard, and controlled phase gates. The important point to remark is the fact that we use, as a starting point, a set of generating gates G = {G1, ...., GN}(with finite elements). In the above examples we have: G1 = {T, H}and G2 = {CNOT, H, Rφ}. The native gates of the
hardware presented in [2] are given by G3 = {XX, Rφ}. In this paper, we concentrate on G1, but a similar analysis could be carried out for G2and G3.
Given a generating set of gates G, all physically implementable gates will be given by successive applications of the elements of G. This means that any actual gate implemented in the quantum computer will have the form: U=Un. . . U1, where Ui ∈G. Let us call to these compositions of gates (in analogy with the classical case) quantum polynomial gates. Denote by P(G)the set of all possible quantum polynomial gates. If G is formed by a universal set of gates, then P(G)will be dense in
UN(H)(the set of unitary operators acting onH). From a theoretical perspective, this is all we need to implement any desired quantum algorithm.
Any component of a quantum algorithm will be described as a succession of polynomials in P(G), and eventually, a reading (measurement) described by a projection onto a subspace or a family of them, with their associated probabilities computed using the Born rule. Notice that P(G)and its topological closure are the quantum versions of the logic of a classical computer. In the classical version, we have a functional calculus based on Boolean functions. The Boolean character is related to the fact that these functions commute. In the quantum version, we have a non-commutative matrix calculus instead.
An important problem in the logical approach to classical computation is given by testing functional equations. This problem can be solved by appealing to truth tables of elementary Boolean functions, such as∨,∧and¬, as explained in Section2. However, in the quantum version, the existence of non-compatible context and indeterminate processes leads us to a different notion of truth, based on probabilistic and contextual truth values. In the following Subsection, we explain how this works. 3.2. Probabilistic Truth Values
We start by defining equivalences between gates as follows: Definition 2. Given two quantum gates U and V, we say that
• U is equivalent to V with respect to ρ∈ C(H)and P∈ P (H)(and we denote it by U≡ρ
PV) if and only if Tr(UρU†P) =Tr(VρV†P)
For a given quantum gate U, we call probabilistic truth value associated with U with respect to P∈ P (H)the real number Tr(UρU†P).
• U is equivalent to V with respect to ρ∈ C(H)(and we denote it by U≡ρV) if and only if
Tr(UρU†P) =Tr(VρV†P) for all P∈ P (H).
• U is equivalent to V with respect to P∈ P (H)(and we denote it by U≡PV) if and only if Tr(UρU†P) =Tr(VρV†P)
for all ρ∈ C(H).
• U is equivalent to V (and we denote it by U≡V) if and only if Tr(UρU†P) =Tr(VρV†P) for all ρ∈ C(H)and P∈ P (H).
Notice that neither U ≡ρ V nor U ≡ρ
P V imply that U = V. On the contrary, U ≡ V implies U=V. We have included this last (trivial) definition just to easily illustrate the fact that U≡ρV and
U≡ρ
PV are relaxations of the identity relationship. Indeed, we can summarize this as follows: U=V⇐⇒U≡V=⇒U≡ρV=⇒U≡ρ
PV.
It is easy to find counterexamples showing that the converse implications are not valid.
The above definitions of equivalence between logical gates have associated the following probabilistic truth values:
• For a given quantum gate U, we call probabilistic truth value associated with U in the context P and state ρ the real number Tr(UρU†P).
• For a given quantum gate U, we call probabilistic truth values associated with U in the context P the family of real numbers Tr(UρU†P), where ρ∈ C.
• For a given quantum gate U, we call probabilistic truth values associated with U in the state ρ the family of real numbers Tr(UρU†P), where P∈ P (H).
Notice that the above definitions have associated a notion of implication between gates: Definition 4. Given two gates U and V, we say that
• U≤V with respect to ρ∈ C(H)and P∈ P (H)(and we denote it by U≤ρ
PV) if and only if Tr(UρU†P) ≤Tr(VρV†P)
• U≤V with respect to ρ (and we denote it by U≤ρV) if and only if
Tr(UρU†P) ≤Tr(VρV†P) for all P∈ P (H).
• U≤V with respect to P (and we denote it by U≤PV) if and only if Tr(UρU†P) ≤Tr(VρV†P) for all ρ∈ C(H).
It is also important to notice that the “≡ρ
P" relationship is coincident with the notion of probabilistic truth values of previous publications. For example, in [5,7], the probabilistic truth value of the Toffoli gate is defined as:
p(ρ⊗σ) =Tr(Tρ⊗σ⊗ |0ih0|T)(I⊗I⊗P1)) (2) where P1:= |1ih1|.
Another important issue is at stake here. The notion of probabilistic truth value outlined in Definition5contains the Boolean truth notion as a particular case as follows. We use as starting state the elements of the computational basis. Then, implement matrix versions of the usual classical gates (as for example, Toffoli). Use as a projection operator the projection associated with any element of the computational basis (or more generally, one may use the Boolean latticePB0, defined in Section2.3).
This procedure yields a Boolean calculus which is isomorphic to the usual one in reversible classical computation.
With the above definitions, we can define the truth value associated to each measurement outcome (i.e., the reading process) of any quantum protocol. The final truth value of the protocol, associated to the probability of occurrence of the success subspace, will be related to the probability of success of the algorithm. As in the classical case, we need to test the equivalence between different sets of gates. This can be done in a natural way by appealing to the≡ρand≡ρ
Prelations. Indeed, if our aim is to compare the action of two sets of gates regarding a definite subspace of success, we must use the≡ρ
Prelationship. If our aim is to compare two gates regarding the unitary process before any reading (measurement), we must use the stronger relation≡ρ.
Notice that this last definition of equivalence (the one given by≡ρ) is the generalization of the
truth table to the Boolean setting. Let us elaborate a little bit on this notion. In a classical setting, if we aim to compare between logical circuits (defined as compositions of Boolean functions), all we must do is to list truth tables on each side of the equation. A similar remark follows for non-deterministic
classical computation: we must test the equivalence by evaluating the probability of each output on each side of the equation. In both cases (deterministic and no-deterministic), if these numbers are coincident, we speak about logically equivalent algorithms.
However, now, as remarked above, we have infinitely many contexts in the quantum case (indeed, the wholeP (H)is available). This forces us to test the equivalence (equality in a logical circuit equation) in several different contexts. Let us illustrate this statement with a concrete example. Suppose that we have two gates U and V, and that we want to check their equivalence with respect to a reference state ρ. Thus, we must compare Tr(UρU†P) =Tr(VρV†P)for a suitably chosen set of projection operators (in principle, there are infinitely many of them, but in practice, only a reduced family of them is needed, depending on the dimensionality of the Hilbert space. This is a well-studied question). Notice that Tr(UρU†P) =Tr(VρV†P)is equivalent to Tr(ρU†PU) =Tr(ρV†PV). To test this equation (and to give the problem a form similar to the classical one) we can choose a suitable family of orthonormal bases, each defining a different measurement context. Each one of these bases defines its own “computational basis”. Thus, instead of checking the probabilities in one single Boolean context (a set of outputs) as in the non-deterministic classical case, what we are doing here is to perform the same procedure for all possible quantal contexts defined by the chosen set of bases (or at least, for all possible contexts of interest for the problem we want to solve). All these properties reveal that quantum computing is the non-commutative version of classical non-deterministic computation (as expected!), and that the relationship defined by≡ρis nothing but the generalization of the truth tables to the non-commutative
setting.
The above definitions introduce different equivalence notions of gates. In addition, we can compute a kind of quotient of P(G)with regards to this equivalence relationships (i.e., we can compute the quotient spaces P(G)/≡ρ
Pand P(G)/≡ρ). Notice that P(G)/≡is meaningless, because P(G)/≡ equals P(G). Each class of P(G)/ ≡ρ
P and P(G)/ ≡ρ contains equivalent gates for the different purposes defined by the different equivalence relations.
4. Examples of Quantum Algorithms
Now we show how our approach can accommodate some of the most important quantum algorithms. 4.1. Deutsch-Jozsa Algorithm
Let us examine first the Deutsch-Jozsa algorithm [1]. In this case, the task is to determine if a function f is constant or balanced. There are four functions from{0, 1} −→ {0, 1}, namely:
f1(0) =0 f1(1) =1 f2(0) =1 f2(1) =0 f3(0) =0 f3(1) =0 f4(0) =1 f4(1) =1
(3)
Thus, we have two classes: C= {f1, f2}and B= {f3, f4}, and we must determine if the unknown function f belongs to B or to C. Let us see now how this can be reduced to the steps outlined in Section2.3. Step 1. In the first step, prepare the quantum state|0i|1i.
Step 2. Next, the Hadamard operator is applied to both qubits yielding the state: 1
2(|0i + |1i)(|0i − |1i).
The quantum implementation of the function f (which establishes the connection between the classical problem and the quantum computation) will be given by a quantum operator such that it maps|xi|yi to|xi|f(x) ⊕yi. Applying this function to the state gives
(−1)f (0)1
2(|0i + (−1)
Now, applying the Hadamard transformation again to the first qubit we get: |ψi = (−1)f (0)1
2((1+ (−1)
f (0)⊕ f (1))|0i + (1− (−1)f (0)⊕ f (1))|1i)(|0i − |1i).
Step 3. The next step consists in determining the projection of the above state to the subspaces represented by projection operators|0ih0| ⊗1and|1ih1| ⊗1.
4.2. Determination of a Function’s Period
The determination of the period of a periodic function f lies at the heart of the Shor and Simon quantum computation algorithms [1]. The objective now is to determine the period of a function f :ZN −→ Z, such that f(x+r) = f(x)for all x. It is assumed that the function does not take the same value twice in the same period.
Step 1. Start the computer by generating -using the usual procedure- the state: |fi = √1 N N−1
∑
x=0 |xi|f(x)i. (4)It is not possible to extract the period yet. Even if we measure the value of the second register and obtain the value y0, we will end up with the following state in the first register (with x0the smallest x such that f(x) =y0and N=Kr):
|ψi = √1 K K−1
∑
k=0 |x0+kri. (5)However,|ψidoes not give us information about r yet.
Step 2. To obtain the period, it is necessary to apply the quantum Fourier transform (QFT), which is a unitary matrix with entries
Fab = √1 Nexp
2πiab
N. (6)
By applying the QFT to|ψiwe obtain
F |ψi = √1 r r−1
∑
j=0 exp2πix0jr |jN ri. (7)Step 3. Finally, a measurement is performed in the basis{|jNri}, and using the result it is possible to determine the period of the function as follows. The obtained value c will be such that c=jNr, for some 0≤j≤r−1. Then,cj = Nr, and if j is coprime with r, it will be possible to determine r. The success of the algorithm depends on the fact that j and r will be coprimes with a large enough probability. 5. Axiomatization of the Quantum Computational Logic
In the classical case, we know that the functions are given by a commutative calculus generated by the elementary Boolean functions∨,∧and¬. Thus, the axiomatization of a classical computational logic can be given in terms of the axioms defining a Boolean algebra. Is it possible to proceed in an analogous way for our notion of quantum computational logics? We outline an answer to this question below.
Notice first that the classical connectives∨,∧and¬have the natural interpretation given by: • ∨is the operation of disjunction in our natural language.
• ∧is the operation of conjunction in our natural language. • ¬is the operation of negation in our natural language.
However, quantum computers operate in a very different way. If we consider as elementary gates the set G3, we have the following semantical/physical interpretation:
• Hi: generates a superposition in qubit i.
• CNOT: flips the value of the second qubit if the control qubit is 1; do nothing otherwise. • Rφadds a phase of φ in one of the terms of the superposition.
Notice the following: all truth values of a classical probabilistic calculus are computed regarding classical propositions. However, these propositions are nothing but the elements of a Boolean algebra. As an example, consider a computer with N bits. Thus, all possible inputs are given by elements of the set {0, 1}N(and also the outputs). Thus, all possible readings (measurements) in the output of a computation are given by elements of{0, 1}N, and all possible propositions are nothing but conjunctions, disjunctions, and negations of this outcome set. In other words, all elementary propositions are given by the elements of the Boolean algebraP ({0, 1}N). The nature of the classical (deterministic) computing process assigns a valuation to the set{0, 1}to each element of the setP ({0, 1}N). Non-deterministic classical computation instead, assigns probability values in the interval[0, 1].
The quantum setting, despite of its formidable appearance, is completely analogous. We have stressed above that the quantum calculus contains the classical one as a special case. This is totally reasonable: quantum mechanics defines a probabilistic classical theory for each context. In other words, a quantum state can be seen as a collection of classical probability distributions pasted in a harmonic way using the density operator associated with that state [12]. What is thus the analogous of a reading of a quantum register? The answer was given by von Neumann in the first axiomatization of the formalism: each elementary reading (i.e., any possible empirically testable proposition) is represented by a projection operator P ∈ P (H). Thus, we have a very clear operational interpretation of the equivalence relations and truth values defined in Definition5: what we are doing here is to compute the truth value of a quantum state regarding a particular proposition. This notion of truth in quantum computation is all that we need to compare different sets of gates and the success probability of each quantum algorithm.
Another important thing to remark is that the calculus defined by the matrices involved in a quantum case is not commutative. Thus, we can anticipate that the axiomatization will not involve a Boolean algebra.
Thus, to define a suitable algebraic axiomatics for quantum computation, all we must do is to consider: (i) a setLof empirically testable propositions (which are intended to represent all possible readings of the quantum register). It is natural to demand thatLshould be an orthomodular lattice (as we show below, this covers the classical and quantum cases as well); (ii) a set of statesCassigning definite probabilities to each element of L(these can be defined in the usual way as σ-additive probabilities) [12]; (iii) an elementary set G of operations acting by automorphisms inL. Remember that an automorphism of a logic is defined as a bijective map U :L −→ Lsatisfying (a) U(0) =0 and U(1) = 1, (b) for any denumerable sequence X1, X2, . . . we have U(WnXn) = WnU(Xn)and U(V
nXn) =
V
nU(Xn)and (c) for all X ∈ L, U(X⊥) = (U(X))⊥. The set G generates the collection P(G) of logical polynomials (by composition). The set Ξ = hL;C; Giwill be called a generalized computational scheme. In the rest of this section, we make extensive use of the following notation: given an automorphism U acting onL, define the action U(ν)of U on the state ν as U(ν)(X):=ν(U(X)), for all X∈ L. UsingΞ we can define P(G)(that determines the set of all possible logical gates) and the notions of probabilistic truth value relative to a context and equivalence of logical gates as follows: Definition 5. Given two gates U, V∈P(G), we say that
• U is equivalent to V with respect to ν∈ Cand X∈ L(and we denote it by U≡ν
XV) if and only if µ(X) =µ0(X)
where µ(−) =U(ν)(−)and µ0(−) =V(ν)(−).
• U is equivalent to V with respect to ν (and we denote it by U≡νV) if and only if
µ(X) =µ0(X) for all X∈ L.
• U is equivalent to V (and we denote it by U≡V) if and only if µ(X) =µ0(X)for all ν∈ Cand X∈ L. We can also define the notion of generalized protocol using the following steps:
Step 1. Chose an initial reference state ν ∈ C (this state is intended to be the same for all possible algorithms, and is interpreted as the initial state of the devise).
Step 2. Apply a collection of gates{Ui}i=1,...,nto reach a desired final state µ(−) = (Un· · ·U2U1)(ν)(−), possessing the properties needed to perform the desired computation (answer the question that we need to answer).
Step 3. Perform a measurement on the system when the state µ is reached, check the result obtained, and depending on the result, stop the process, or continue the protocol if necessary (which will involve a similar -in some cases, the same- process).
The intended interpretations of the above notions are similar to those of classical and quantum algorithms. We recover classical computation by settingL = B(whereBis a Boolean algebra) and quantum computation whenL = P (H)(using the concomitant definitions of initial reference state, probabilities, etc.).
As in the quantum case, we can give definitions of probabilistic truth values: Definition 6. Given two gates U and V, we say that
• For a given generalized gate U, we call probabilistic truth value associated with U in the event X∈ L and initial state ν the real number U(ν)(X).
• For a given generalized gate U, we call probabilistic truth values associated with U in the event X∈ Lthe family of real numbers U(ν)(X), where ν∈ C.
• For a given generalized gate U, we call probabilistic truth values associated with U in the state ν the family of real numbers U(ν)(X), where X∈ L.
Notice that the above definitions have associated a notion of implication between gates: Definition 7. Given two gates U and V, we say that
• U≤V with respect to ν∈ Cand X∈ L(and we denote it by U≤ν
X V) if and only if U(ν)(X) ≤V(ν)(X)
• U≤V with respect to ν (and we denote it by U≤νV) if and only if
U(ν)(X) ≤V(ν)(X) for all X∈ L.
• U≤V with respect to X∈ L(and w denote it by U≤XV) if and only if U(ν)(X) ≤V(ν)(X)
The effect of the Hadamard gate in the computational basis is to generate a superposition out of the input qubit. Thus, it is relevant for our construction to describe how superpositions are defined in arbitrary orthomodular lattices (we follow [32], Chapter III, Section 4). Given an orthomodular lattice L, letDbe a collection of states inL. Then, a state ν is a superposition of the states inD, if and only if, for all X∈ Lwe have
∀µ∈ D (µ(X) =0) =⇒ ν(X) =0 (8)
The above definition coincides with the usual one for the case of the lattice of projection operators acting on a Hilbert space and pure states. In Boolean algebras, no pure state can be a superposition of other pure states. As automorphisms of a logic are angle-preserving (i.e., they are straightforward generalizations of the rotations acting on the projective geometry associated with a Hilbert space), their effect on a given set of propositions will be, in general, to generate superpositions. This fact guarantees that we will be able to recover a quantum-like computation rich enough so as to display contextuality and entanglement (as is the case for example, with factor von Neumann algebras, for which a version of the Kochen-Speker theorem can be proved [21]; for the study of correlations in the algebraic approach see [33]).
6. Conclusions
In this work we have presented a generalization of quantum computational logics capable of dealing with some important examples of quantum algorithms. We show that our constructions generalize previous studies on the subject. In Section 5we have outlined an axiomatization for quantum computational logics. Our developments lead to new problems related to the algebraic characterization of computational gates in a non-commutative setting. They also open the door for further generalization of the notion of algorithm, beyond the classical and standard quantum mechanical formalisms.
Author Contributions:All authors contributed equality in writing the paper. All authors have read and approved the final manuscript.
Funding:This work has been partially supported by Regione Autonoma della Sardegna in the framework of the project “Time-logical evolution of correlated microscopic systems” (CRP 55, L.R. 7/2007, 2015), by Fondazione Banco di Sardegna & Regione Autonoma della Sardegna in the framework of the project “Science and its logics, the representation’s dilemma”, cup: F72F16003220002, and by Fondazione Banco di Sardegna of the project “Strategies and Technologies for Scientific Education and Dissemination”, cup: F71I17000330002.
Acknowledgments:This work has been partially supported by CONICET (Argentina). Conflicts of Interest:The authors declare no conflict of interest.
References
1. Nielsen, M.A.; Chuang, I.L. Quantum Computation and Quantum Information; Cambridge University Press: Cambridge, UK, 2010.
2. Gambetta, J.M.; Chow, J.M.; Steffen, M. Building logical qubits in a superconducting quantum computing system. NPJ Quant. Inf. 2017, 3, 2. [CrossRef]
3. Freytes, H.; Domenech, G. Quantum computational logic with mixed states. Math. Logic Q. 2013, 59, 27–50.
[CrossRef]
4. Chiara, M.L.D.; Giuntini, R.; Sergioli, G. Probability in quantum computation and quantum computational logics: A survey. Math. Struct. Comp. Sci. 2013, 24, 1–14.
5. Chiara, M.L.D.; Giuntini, R.; Sergioli, G.; Leporini, R. Abstract quantum computing machines and quantum computational logics. Int. J. Quant. Inf. 2016, 14, 1640019. [CrossRef]
6. Freytes, H.; Sergioli, G. Fuzzy approach for Toffoli gate in quantum computation with mixed states. Rep. Math. Phys. 2014, 74, 154–180. [CrossRef]
7. Chiara, M.L.D.; Giuntini, R.; Sergioli, G.; Leporini, R. A many-valued approach to quantum computational logics. Fuzzy Sets Syst. 2016, 335, 94–111. [CrossRef]
8. Chiara, M.L.D.; Giuntini, R.; Leporini, R.; Freytes, H.; Sergioli, G. Probabilities and epistemic operations in the logics of quantum computation. Entropy 2018, 20, 837. [CrossRef]
9. Chiara, M.L.D.; Giuntini, R.; Leporini, R.; Sergioli, G. A first-order epistemic quantum computational semantics with relativistic-like epistemic effects. Fuzzy Sets Syst. 2016, 298, 69–90. [CrossRef]
10. Holik, F.; Bosyk, G.M.; Bellomo, G. Quantum Information as a Non-Kolmogorovian Generalization of Shannon’s Theory. Entropy 2015, 17, 7349–7373. [CrossRef]
11. Birkhoff, G.; von Neumann, J. The logic of quantum mechanics. Ann. Math. 1936, 37, 823–843. [CrossRef] 12. Holik, F.; Sáenz, M.; Plastino, A. A discussion on the origin of quantum probabilities. Ann. Phys. 2014,
340, 293–310. [CrossRef]
13. Domenech, G.; Holik, F.; Massri, C. A quantum logical and geometrical approach to the study of improper mixtures. J. Math. Phys. 2010, 51, 052108. [CrossRef]
14. Holik, F.; Massri, C.; Ciancaglini, N. Convex quantum logic. Int. J. Theor. Phys. 2012, 51, 1600–1620.
[CrossRef]
15. Holik, F.; Massri, C.; Plastino, A.; Zuberman, L. On the lattice structure of probability space in quantum mechanics. Int. J. Theor. Phys. 2013, 51, 1836–1876. [CrossRef]
16. Anders, J.; Browne, D.E. Computational Power of Correlations. Phys. Rev. Lett. 2009, 102, 050502. [CrossRef]
[PubMed]
17. Delfosse, N.; Allard-Guerin, P.; Bian, J.; Raussendorf, R. Wigner Function Negativity and Contextuality in Quantum Computation on Rebits. Phys. Rev. X 2015, 5, 021003. [CrossRef]
18. Howard, M.; Wallman, J.J.; Veitch, V.; Emerson, J. Contextuality supplies the ’magic’ for Quantum Computation. Nature 2014, 510, 351. [CrossRef]
19. Raussendorf, R.; Browne, D.E.; Delfosse, N.; Okay, C.; Bermejo-Vega, J. Contextuality and Wigner function negativity in qubit quantum computation. arXiv 2017, arXiv:1511.08506.
20. Raussendorf, R. Contextuality in measurement-based quantum computation. Phys. Rev. A 2013, 88, 022322.
[CrossRef]
21. Döring, A. Kochen-Specker Theorem for von Neumann Algebras. Int. J. Theor. Phys. 2005, 44, 139–160.
[CrossRef]
22. Bub, J. Quantum computaton from a quantum logical perspective. Quant. Inf. Comput. 2007, 7, 281–296. 23. Rédei, M.; Summers, S. Quantum probability theory. Stud. Hist. Philos. Sci. Part B Stud. Hist. Philos.
Modern Phys. 2007, 38, 390–417. [CrossRef]
24. Kitaev, A.Y.; Shen, A.H.; Vyalyi, M.N. Classical and Quantum Computation; Graduate Studies in Mathematics Volume 47; American Mathematical Society Providence: Rhode Island, RI, USA, 2002.
25. Aharanov, D.; Kitaev, A.; Nisan, N. Quantum circuits with mixed states. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, Dallas, TX, USA, 24–26 May 1998; pp. 20–30.
26. Kalmbach, G. Ortomodular Lattices; Academic Press: London, UK, 1983.
27. Gudder, S.P. Stochastic Methods in Quantum Mechanics; Dover Publications: North Holland, The Netherland; New York, NY, USA; Oxford, UK, 1979.
28. Khrennikov, A. Ubiquitous Quantum Structure-From Psychology to Finance; Springer: Berlin/Heidelberg, Germany, 2010.
29. Khrennikov, A. Social Laser: Action amplifcation by stimulated emission of social energy. Philos. Trans. R. Soc. A 2016, 374, 20150094. [CrossRef] [PubMed]
30. Aerts, D.; Gabora, L.; Sozzo, S. Concepts and Their Dynamics: A Quantum-Theoretic Modeling of Human Thought. Top. Cognit. Sci. 2013, 5, 737–772. [CrossRef]
31. Aharonov, D. A Simple Proof that Toffoli and Hadamard are Quantum Universal. arXiv 2003, arXiv:quant-ph/0301040v1.
32. Varadarajan, V. Geometry of Quantum Theory I; van Nostrand: Princeton, NJ, USA, 1968.
33. Clifton, R.; Halvorson, H. Entanglement and Open Systems in Algebraic Quantum Field Theory. Stud. Hist. Philos. Sci. Part B Stud. Hist. Philos. Modern Phys. 2001, 32, 1–31. [CrossRef]
c
2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
