Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator

This paper compares three fixed-dimension satisfiability semantics for quantum logic—standard Hilbert-lattice, global commuting-projector, and local partial-Boolean—proving a strict hierarchy where the standard semantics is strictly more expressive than the others, as demonstrated by an explicit formula that is satisfiable in the standard semantics but unsatisfiable under the other two for all dimensions $d \ge 2$.

The Gist

Imagine you are trying to solve a logic puzzle, but instead of using standard "True/False" switches, you are using quantum switches. These switches are special because they can be "on," "off," or in a fuzzy state of both, depending on how you look at them.

This paper is about three different rulebooks for how to play with these quantum switches. The author, Joaquim, asks: Are these three rulebooks actually different, or do they just sound different but lead to the same results?

Here is the breakdown using simple analogies.

The Three Rulebooks (Semantics)

Think of the three rulebooks as three different ways to organize a team of workers (the "atoms" or variables in the formula) to build a structure.

1. The "Standard" Rulebook (Hilbert-Lattice):

   • The Analogy: Imagine a giant, flexible construction site. You can mix and match any workers however you want. If Worker A and Worker B don't get along (they don't "commute"), you can still put them on the same team, but the result might be messy or unexpected. This rulebook allows for chaos and non-distributivity. In this world, the rule "A and (B or C)" is not always the same as "(A and B) or (A and C)."
   • The Vibe: "Anything goes, as long as it fits in the geometry of the room."

2. The "Global Commuting" Rulebook:

   • The Analogy: Imagine a strict corporate office. Before you can start building, every single worker must agree to get along with every other worker in the entire project. If Worker A and Worker B don't get along, you can't even start the project. Once they agree, they act like a normal, boring team where standard logic applies perfectly.
   • The Vibe: "No conflicts allowed. Everyone must be on the same page before we begin."

3. The "Local Partial-Boolean" Rulebook:

   • The Analogy: Imagine a series of small, isolated workstations. You only check if two workers get along right at the moment they are asked to work together. If Worker A and Worker B are asked to work together, they must get along. But if Worker A never meets Worker C, they don't need to get along. It's a "check-as-you-go" approach.
   • The Vibe: "Don't worry about the whole team; just make sure the people shaking hands right now are friendly."

The Big Question

The author wanted to know: Are these three rulebooks actually different?

• If you can build a structure under the "Local" rules, can you also build it under the "Global" rules?
• If you can build it under "Global," can you build it under "Standard"?

The Results: The Chain of Power

The author proved a clear hierarchy, like a game of "Rock, Paper, Scissors" where one rulebook is always more powerful than the next:

1. Global $\rightarrow$ Local $\rightarrow$ Standard
   • If a puzzle can be solved when everyone must get along (Global), it can definitely be solved when you only check friendships locally (Local).
   • If it can be solved locally, it can definitely be solved in the chaotic Standard world.
   • Why? Because the Standard world has the fewest restrictions. It's the easiest to satisfy.

The "Separator" Formula: The Smoking Gun

To prove that the "Standard" rulebook is strictly better (more permissive) than the other two, the author created a specific logic puzzle called SEP-1.

The Puzzle:

"Take a group A. Inside that group, look at the combination of B or C. But, make sure that this is NOT the same as (A with B) combined with (A with C)."

In Plain English:
This puzzle relies on a weird quantum quirk called non-distributivity. In the Standard world, it is possible for "A and (B or C)" to be a bigger, more complex thing than "(A and B) or (A and C)."

• In the Standard World: The puzzle is solvable. The geometry of the quantum space allows this weirdness to exist.
• In the Global World: The puzzle is impossible. Because everyone must get along, the weirdness disappears, and the two sides of the equation become identical. The puzzle collapses to "False."
• In the Local World: The puzzle is also impossible. Even though we only check friendships locally, the structure of this specific puzzle forces everyone to get along anyway. Once they get along, the weirdness vanishes, and the puzzle fails.

The Conclusion

The paper draws a clear line in the sand:

1. Standard Logic is the most powerful. It can solve puzzles that the other two cannot.
2. Global and Local logic are more restrictive. They are "stricter" versions of quantum logic.
3. The Mystery: We know Standard is the strongest. We know Global is weaker than Standard. But we don't know yet if Local is actually stronger than Global, or if they are exactly the same. The author leaves this as an open question for future researchers.

Why Does This Matter?

In the past, people might have confused these three rulebooks, thinking they were all the same thing. This paper says: "Stop! They are different."

If you are trying to prove that a quantum computer can solve a problem, you need to know exactly which rulebook you are using. If you use the "Standard" rules, you might think you've solved a problem that is actually impossible under the stricter "Global" or "Local" rules. This paper provides the map to keep those worlds separate.

Technical Summary

Here is a detailed technical summary of the paper "Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator" by Joaquim Reizi Higuchi.

1. Problem Statement

The paper addresses the ambiguity surrounding the interpretation of propositional logic connectives ($\neg, \land, \lor$) within the context of finite-dimensional quantum logic. While the standard interpretation uses the lattice of subspaces of a Hilbert space, alternative interpretations exist that impose different constraints on commutativity.

The core problem is to rigorously distinguish between three specific satisfiability semantics for a fixed finite dimension $d \ge 1$ over a field $F \in \{R, C\}$:

1. Standard Hilbert-lattice Semantics ($STD$): Connectives are interpreted as lattice operations (intersection and sum) on the subspace lattice $L(H)$. No commutativity is required between the projectors representing atomic variables.
2. Global Commuting-Projector Semantics ($COM$): All atomic projectors in a formula must pairwise commute. This restricts the interpretation to a single Boolean algebra (a "Boolean block").
3. Local Partial-Boolean Semantics ($PBA$): Binary connectives are defined only if the operands are "commeasurable" (pairwise commuting). Commutativity is checked locally at each node of the parse tree, rather than globally for the entire set of atoms.

The paper seeks to clarify the logical relationships between these three notions and determine if they define distinct classes of satisfiable formulas.

2. Methodology

The author employs a formal semantic approach using linear algebra and lattice theory:

• Formalization: Precise recursive definitions are provided for the three semantics.
  • $STD$ uses subspace intersection ($\cap$) and sum ($+$).
  • $COM$ uses projector multiplication ($PQ$) and the formula $P+Q-PQ$ for join, assuming global commutativity.
  • $PBA$ defines values recursively, requiring commutativity ($PQ=QP$) only when evaluating a binary connective.
• Implication Proofs: The paper establishes a chain of implications ($COM \implies PBA \implies STD$) by proving that any valuation satisfying the stricter constraints (global commutativity) automatically satisfies the looser ones, and that the range of a projector in $PBA$ corresponds to the subspace in $STD$.
• Counter-Example Construction: To prove strict separation, the author constructs a specific formula, SEP-1, designed to exploit the failure of the distributive law in non-commutative lattices while collapsing to a tautology in commutative (Boolean) settings.

3. Key Contributions

The paper makes three primary contributions:

1. Formal Hierarchy: It establishes the implication chain for any dimension $d \ge 1$ and formula $\phi$:
   $$Sat^d_{COM}(\phi) \implies Sat^d_{PBA}(\phi) \implies Sat^d_{STD}(\phi)$$
2. Explicit Separator Formula: It introduces the formula SEP-1:
   $$SEP\text{-}1 := (p \land (q \lor r)) \land \neg ((p \land q) \lor (p \land r))$$
   This formula is the negation of the distributive law.
3. Strict Separation Results: It proves that for every dimension $d \ge 2$:
   • $SEP\text{-}1$ is satisfiable under the Standard ($STD$) semantics.
   • $SEP\text{-}1$ is unsatisfiable under both the Global Commuting ($COM$) and Local Partial-Boolean ($PBA$) semantics.

4. Detailed Results

The Implication Chain

• $COM \implies PBA$: If a formula is satisfiable under global commutativity, the valuation is also valid under the local partial-Boolean semantics because global commutativity implies local commutativity at every node. The values computed in both semantics coincide.
• $PBA \implies STD$: If a formula is satisfiable under $PBA$, there exists a projector valuation where the final result is non-zero. By mapping these projectors to their ranges (subspaces), one constructs a standard valuation that yields a non-zero subspace, proving $STD$ satisfiability.

The Separator (SEP-1) Analysis

• Under $COM$ and $PBA$:
  • In $COM$, all atoms commute, forcing the logic to behave like classical Boolean algebra. In Boolean algebras, the distributive law holds: $p \land (q \lor r) = (p \land q) \lor (p \land r)$. Thus, the formula becomes $X \land \neg X = 0$ (unsatisfiable).
  • In $PBA$, the paper proves (Lemma 4.3) that for $SEP\text{-}1$ to be defined, the atoms $p, q, r$ must pairwise commute. Once they commute, the logic collapses to the Boolean case, and the formula evaluates to 0.
• Under $STD$:
  • The paper constructs a counter-example in dimension $d=2$. Let $p$ be the subspace spanned by $(e_1 + e_2)$, $q$ by $e_1$, and $r$ by $e_2$.
  • Here, $q \lor r$ spans the whole plane, so $p \land (q \lor r) = p$.
  • However, $p \land q = \{0\}$ and $p \land r = \{0\}$, so $(p \land q) \lor (p \land r) = \{0\}$.
  • The formula evaluates to $p \land \neg \{0\} = p \neq \{0\}$. Thus, it is satisfiable.

Classification of Satisfiability Classes

For $d \ge 2$, the classes of satisfiable formulas satisfy:
$$SAT^d_{COM} \subseteq SAT^d_{PBA} \subsetneq SAT^d_{STD}$$
$$SAT^d_{COM} \subsetneq SAT^d_{STD}$$

5. Significance and Open Problems

• Clarification of Semantics: The paper resolves confusion in the literature by showing that "quantum satisfiability" is not a monolithic concept. The standard Hilbert-lattice semantics is strictly more expressive than interpretations that enforce commutativity (either globally or locally).
• Complexity Context: The author positions this work as a semantic comparison rather than a complexity reduction. It acknowledges that generic reductions for standard semantics are already known (via Herrmann) and that complexity results for partial Boolean algebras exist (via Dawar-Shah). This paper fills the gap by explicitly separating these definitions.
• Open Problem: The paper leaves one relationship unresolved: Is $SAT^d_{COM}$ strictly contained in $SAT^d_{PBA}$?
  • While $PBA$ allows local commutativity checks that might theoretically be less restrictive than global checks, the paper does not provide a formula that is $PBA$-satisfiable but $COM$-unsatisfiable.
  • The open question is whether there exists a formula where the nodewise commutativity constraints do not force the entire set of atoms to commute globally.

In summary, this paper provides a rigorous, short, and explicit proof that the failure of distributivity in quantum logic is the precise mechanism that separates standard subspace semantics from any semantics enforcing commutativity, while highlighting a remaining gap in understanding the relationship between local and global commutativity constraints.