Non-Unitary Quantum Logic -- SERI MATS Research Sprint

post by Yegreg · 2023-02-16T19:31:50.993Z · LW · GW · 0 comments

Contents

  Setup
    Syntax
    Semantics
  Lattices
    Example
  Classical vs Quantum Logic
    Example: the double slit experiment
  Consistency in Quantum Logic
    Lattice Theory Prerequisites
      Modular lattices
      Arguesian lattices
    A Counterexample
None
No comments

The following discussion was inspired by a comment [AF(p) · GW(p)] on Vanessa Kosoy's Shortform regarding affine infradistributions. I expect the results here would not be considered surprising or novel by an expert in quantum logic or lattice theory. In particular [HTZ16[1]] shows the unsolvability of the problem described below, and [HZ10[2]] covers many related results as well. However, I haven't found this exact result written down anywhere, and I expect this beginner-friendly and mostly self-contained exposition to be useful for a reader interested in a glance into quantum logic.

Setup

The term "quantum logic" is often used to refer to the structure formed by subspaces of a Hilbert space (thought of as quantum propositions). The analogs of logical 'and', 'or', and 'not' are taken to be the operations of intersection, sum, and complements of subspaces, respectively. We can loosen this structure by dropping the inner product (so downgrading our Hilbert space to just a vector space), and hence the notion of orthogonal complements. We can call the resulting simplified logic "non-unitary" (for the lack of an inner product) quantum logic. We'll restrict our attention to the finite dimensional case. The following is the corresponding syntax and semantics.

Syntax

Let  be a set of propositional variables. We define the set  of well-formed formulas recursively as follows.

A theory  is a subset . Elements of  are written . We'll write  for when both  and .

Semantics

For a vector space , let  denote the set of all linear subspaces of .

Definition 1. A model consists of a finite dimensional vector space , and a map , satisfying the following:

We say  models the theory , if  for every  in .

Lattices

The set  forms a lattice under '' and '', with partial order given by ''. Thus the map  defining the model factors through the lattice quotient of the language  (this is the free bounded lattice generated by the propositional variables, which we'll also call  by abuse of notation).

Given a theory , we can take the quotient of the lattice  by the relations specified in  More precisely we quotient by the congruence relation  generated by  as follows. We can replace each  by , so we can assume  only contains equalities. Then we define the congruence relation  as the smallest congruence relation for which  whenever  is in . Taking the quotient by this congruence relation we end up with a lattice corresponding to , which we'll denote . If  models , then  factors as a lattice homomorphism 

Example

For example, if  consists of , and , we end up with the following lattice :

Classical vs Quantum Logic

In classical (Boolean) logic, a model would be a lattice homomorphism from  to , the lattice of subsets of a set , while in quantum logic we use the lattice of subspaces of a vector space. The key characteristic of classical logic is the distributive property: 

 and its dual.

Note that any classical model of a theory also gives rise to a quantum model by taking the vector space  with basis the set , and composing with the lattice homomorphism  given by span.

Example: the double slit experiment

It's educational to consider an example of a non-classical quantum logic. Consider 3 events , and  (can be thought of as a particle passing through the first slit, passing through the second slit, and hitting the screen at a given point, respectively), whose corresponding propositions form the following non-distributive lattice (called ):

It is easy to see that  cannot be represented as a lattice of subsets due to the failure of distributivity. However, we can model  as three distinct lines in the lattice of subspaces of the plane.

Consistency in Quantum Logic

We call a theory  consistent if it has a non-trivial (i.e. where ) model. Boolean consistency (or satisfiability) is well-know to be NP-hard, so it's natural to ask about the complexity of deciding consistency in the quantum setting.

One immediate necessary criterion for consistency can be seen as follows. If  is a lattice homomorphism, then by taking the dimension of subspaces, we get a map  satisfying the following properties:

We might wonder whether the existence of such a  is sufficient.

Conjecture 2. Given a dimension function  as above, there exists a linear representation of  with dimensions as specified by .

If this conjecture were true, that would mean the existence of a polynomial time algorithm to check quantum satisfiability (since finding such a  is a linear programming problem). As it turns out, the conjecture is false, which we show in Counterexample 2. Hence the proposed simple polynomial time algorithm to check quantum consistency doesn't work. Indeed, quantum consistency turns out to be unsolvable[1].

Lattice Theory Prerequisites

Modular lattices

Vector subspaces have the property that if  and  then . So any linear representation of the lattice  would factor through the quotient lattice where if  and  we identify  and . The resulting quotient lattice  and the induced map  would satisfy a stronger version of the properties 1-3 above, where in 2 we now have  whenever . It turns out that lattices with such a function  are exactly the modular lattices (with the additional property of every bounded chain being finite). These results are spelled out in point 7 and Theorem 9 of Chapter V in [Bir40[3]].

Thus Conjecture 2 boils down to whether these modular lattices always have non-trivial linear representations. This seems somewhat unlikely at first glance, since linear subspace lattices need to satisfy additional properties, e.g. the arguesian property (discussed further in the "Arguesian lattices" section), and indeed in Counterexample 9 we show that this is not the case.

Definition 3. For  in a lattice, the quotient (also called the interval)  is the sublattice 

Definition 4. For any  in a lattice we say the quotients  and  are projective (to each other). So being projective is the equivalence relation generated by these pairs of quotients.

Definition 5. A quotient  is called prime if , but there's no  such that .

Lemma 6. A modular lattice of finite length is simple (i.e., without proper congruence relations) if and only if all its prime quotients are projective (to each other). Note that being simple means having no proper non-trivial quotients.

Proof. This is Corollary 1 in Chapter V, Section 7 of [Bir40[3]]. We only need the simpler "if" direction here, which is fairly straightforward to see directly as follows. If  is a congruence relation on , then  implies , and the dual claim also holds. So if a certain quotient is annulled by  (i.e. made equivalent) then so is every projective quotient.

Now assume  is non-trivial, so  for some . Then also . Since  is finite length, there is some  with  prime (and ). Then by the above every prime quotient is annulled by , which in a finite length lattice implies that  annuls everything. ◻

Arguesian lattices

Definition 7. A modular lattice  is called arguesian if for any  (), 

 implies 

 where  ().

This is the lattice-theoretic formulation of Desargues' theorem, considering the incidence lattice of a projective space:

Lemma 8. For any ring , the lattice of submodules  of a (left) -module  is an arguesian lattice. In particular any sublattice of  is also arguesian.

Proof. Let  be submodules such that the assumption in the arguesian property 

 is satisfied. Let . We want to show that . Let , so by definition 

 for , and . Now 

 so by (1) we have , i.e.  for  and . But then 

 and 

 so 

 as required. ◻

A Counterexample

Counterexample 9. Conjecture 2 fails for the incidence lattice  of a finite non-Desarguesian projective plane. Note that the smallest such plane has  points, which corresponds to a theory  on  propositional variables.

Proof. The lattice  is modular (an explicit dimension function  can be defined by , and  for all points and lines). Being the incidence lattice of a non-Desarguesian plane,  is not arguesian. This lattice also turns out to be simple (i.e. without any smaller non-trivial quotients), and so by Lemma 8 it cannot have a non-trivial linear representation. The fact that  is simple follows from Lemma 6 after showing that all prime quotients are projective for this incidence lattice.

First consider a point  in the projective plane, and let  be the distinct lines through . Then by definition (using  here to denote intervals projective to each other) , and  for any . Since there are at least three lines through , this then implies all of , and  are projective to each other for all  by transitivity.

Now let  be a point distinct from , and let  be the line through  and . Then from the above  is projective to both  and , which in turn are projective to  and .

Putting all of these together, since any line contains at least one point, we can deduce that in fact all prime quotients are projective to each other in the incidence lattice. ◻

To construct a theory  from Counterexample 9, we can introduce propositional variables  corresponding to the points  of the projective plane,  corresponding to the lines , and let  contain all the following:

  1. ^

    Christian Herrmann and Yasuyuki Tsukamoto and Martin Ziegler. On the consistency problem for modular lattices and related structures, 2016

  2. ^

    Christian Herrmann and Martin Ziegler. Computational Complexity of Quantum Satisfiability, 2010

  3. ^

    [Bir40] Garrett Birkhoff. Lattice Theory. American Mathematical Society, New
    York, 1940

0 comments

Comments sorted by top scores.