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

arXiv:1102.3587

Solving UNIQUE-SAT in a Modal Quantum Theory

Jeremiah James Willcock, Amr Sabry

Published Feb 17, 2011• 5 citations
arXivHTMLPDF

Abstract

In recent work, Benjamin Schumacher and Michael D. Westmoreland investigate a version of quantum mechanics which they call modal quantum theory. This theory is obtained by instantiating the mathematical framework of Hilbert spaces with a finite field instead of the field of complex numbers. This instantiation collapses much the structure of actual quantum mechanics but retains several of its distinguishing characteristics including the notions of superposition, interference, and entanglement. Furthermore, modal quantum theory excludes local hidden variable models, has a no-cloning theorem, and can express natural counterparts of quantum information protocols such as superdense coding and teleportation. We show that the problem of UNIQUE-SAT --- which decides whether a given Boolean formula is unsatisfiable or has exactly one satisfying assignment --- is deterministically solvable in any modal quantum theory in constant time. The solution exploits the lack of orthogonality in modal quantum theories and is not directly applicable to actual quantum theory.

DOI
10.48550/arxiv.1102.3587

Related papers

Quantum Computing over Finite Fields

Roshan P. James, Gerardo Ortíz, Amr Sabry

In recent work, Benjamin Schumacher and Michael~D. Westmoreland investigate a version of quantum mechanics which they call "modal quantum theory" but which we prefer to call "discrete quantum theory". This theory is obtained by instantiating the mathematical framework of Hilbert spaces with a finite field instead of the field of complex numbers. This instantiation collapses much the structure of actual quantum mechanics but retains several of its distinguishing characteristics including the notions of superposition, interference, and entanglement. Furthermore, discrete quantum theory excludes local hidden variable models, has a no-cloning theorem, and can express natural counterparts of quantum information protocols such as superdense coding and teleportation. Our first result is to distill a model of discrete quantum computing from this quantum theory. The model is expressed using a monadic metalanguage built on top of a universal reversible language for finite computations, and hence is directly implementable in a language like Haskell. In addition to superpositions and invertible linear maps, the model includes conventional programming constructs including pairs, sums, higher-order functions, and recursion. Our second result is to relate this programming model to relational programming, e.g., a pure version of Prolog over finite relations. Surprisingly discrete quantum computing is identical to conventional logic programming except for a small twist that is responsible for all the ``quantum-ness.'' The twist occurs when merging sets of answers computed by several alternatives: the answers are combined using an "exclusive" version of logical disjunction. In other words, the two branches of a choice junction exhibit an "interference" effect: an answer is produced from the junction if it occurs in one or the other branch but not both.

arXiv:1101.3764•Jan 19, 2011•11 citations

Quantum mechanics over sets

David Ellerman

In the tradition of toy models of quantum mechanics in vector spaces over finite fields (e.g., Schumacher and Westmoreland's "modal quantum theory"), one finite field stands out, 2, since vectors over 2 have an interpretation as natural mathematical objects, i.e., sets. This engages a sets-to-vector-spaces bridge that is part of the mathematical folklore to translate both ways between set concepts and vector space concepts. Using that bridge, the mathematical framework of (finite-dimensional) quantum mechanics can be transported down to sets resulting in quantum mechanics over sets or QM/sets. This approach leads to a different treatment of Dirac's brackets than in "modal quantum theory" (MQT), and that gives a full probability calculus (unlike MQT that only has zero-one modalities of impossible and possible). That, in turn, leads to a rather fulsome theory of QM over sets that includes "logical" models of the double-slit experiment, Bell's Theorem, quantum information theory, quantum computing, and much else. Indeed, QM/sets is proposed as the "logic" of QM in the old-fashioned sense of "logic" as giving the simplified essentials of a theory. QM/sets is also a key part of a broader research program to provide an interpretation of QM based on the notion of "objective indefiniteness," a program that grew out the recent development of the logic of partitions mathematically dual to the usual Boolean logic of subsets.

arXiv:1310.8221•Bulletin of the American Physical Society•Oct 30, 2013•12 citations

Possibility, probability and entanglement: Non-contextuality in modal quantum mechanics

Michael D. Westmoreland, Benjamin W. Schumacher

Modal quantum theory (MQT) is a simplified cousin of ordinary Hilbert space quantum theory. We show that two important theorems of actual quantum theory, the Kochen-Specker theorem excluding non-contextual hidden variables and the Conway-Kochen "free will theorem" about entangled systems, have direct analogues in MQT. The structure of possible measurement results for an entangled system in MQT cannot be represented by probability assignments satisfying the no-signaling principle, such as those given by ordinary quantum theory.

AIP conference proceedings•Jan 1, 2012•1 citation

Cloning, deleting, and hiding in modal quantum theory

Diamond, Phillip, Benjamin W. Schumacher

We examine the toy model of modal quantum theory (MQT), an analogue of actual quantum theory based on finite fields. In particular, we investigate how several essential ``no-go'' results (for cloning, deleting and hiding processes) work in MQT. Cloning and deleting are still forbidden in MQT, though the details of these results are somewhat different in the new context. However, the information of a modal qubit can be completely hidden in the correlations between two entangled modal qubits.

arXiv:2310.04397•Oct 6, 2023•0 citations

Non-contextuality and free will in modal quantum theory

Benjamin W. Schumacher, Michael D. Westmoreland

Modal quantum theory (MQT) is a simplified cousin of ordinary Hilbert space quantum theory. We show that two important theorems of actual quantum theory, the Kochen-Specker theorem excluding non-contextual hidden variables and the Conway-Kochen "free will theorem" about entangled systems, have direct analogues in MQT. The proofs of these analogue theorems are similar to, but much simpler than, the originals. We also show that the structure of possible measurement results for an entangled system in MQT cannot be represented by probability assignments satisfying the no-signaling principle, such as those given by ordinary quantum theory.

arXiv:1010.5452•Oct 26, 2010•6 citations

Testing Quantum Satisfiability

Ashley Montanaro, Changpeng Shao, Dominic Verdon

Abstract Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA $$_1$$ 1 -complete for $$k\ge 3$$ k ≥ 3 , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the ‘property testing’ promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by ‘far from satisfiable by a product state’ we mean that $$\epsilon n^k$$ ϵ n k constraints must be removed before a product state solution exists, for some fixed $$\epsilon >0$$ ϵ > 0 . The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.

arXiv:2301.10699•Communications in Mathematical Physics•Sep 1, 2025•2 citations
In recent work, Benjamin Schumacher and Michael D. Westmoreland investigate a version of quantum mechanics which they call modal quantum theory. This theory is obtained by instantiating the mathematical framework of Hilbert spaces with a finite field instead of the field of complex numbers. This instantiation collapses much the structure of actual quantum mechanics but retains several of its distinguishing characteristics including the notions of superposition, interference, and entanglement. Furthermore, modal quantum theory excludes local hidden variable models, has a no-cloning theorem, and can express natural counterparts of quantum information protocols such as superdense coding and teleportation. We show that the problem of UNIQUE-SAT --- which decides whether a given Boolean formula is unsatisfiable or has exactly one satisfying assignment --- is deterministically solvable in any modal quantum theory in constant time. The solution exploits the lack of orthogonality in modal quantum theories and is not directly applicable to actual quantum theory.
In recent work, Benjamin Schumacher and Michael~D. Westmoreland investigate a version of quantum mechanics which they call "modal quantum theory" but which we prefer to call "discrete quantum theory". This theory is obtained by instantiating the mathematical framework of Hilbert spaces with a finite field instead of the field of complex numbers. This instantiation collapses much the structure of actual quantum mechanics but retains several of its distinguishing characteristics including the notions of superposition, interference, and entanglement. Furthermore, discrete quantum theory excludes local hidden variable models, has a no-cloning theorem, and can express natural counterparts of quantum information protocols such as superdense coding and teleportation. Our first result is to distill a model of discrete quantum computing from this quantum theory. The model is expressed using a monadic metalanguage built on top of a universal reversible language for finite computations, and hence is directly implementable in a language like Haskell. In addition to superpositions and invertible linear maps, the model includes conventional programming constructs including pairs, sums, higher-order functions, and recursion. Our second result is to relate this programming model to relational programming, e.g., a pure version of Prolog over finite relations. Surprisingly discrete quantum computing is identical to conventional logic programming except for a small twist that is responsible for all the ``quantum-ness.'' The twist occurs when merging sets of answers computed by several alternatives: the answers are combined using an "exclusive" version of logical disjunction. In other words, the two branches of a choice junction exhibit an "interference" effect: an answer is produced from the junction if it occurs in one or the other branch but not both.
In the tradition of toy models of quantum mechanics in vector spaces over finite fields (e.g., Schumacher and Westmoreland's "modal quantum theory"), one finite field stands out, 2, since vectors over 2 have an interpretation as natural mathematical objects, i.e., sets. This engages a sets-to-vector-spaces bridge that is part of the mathematical folklore to translate both ways between set concepts and vector space concepts. Using that bridge, the mathematical framework of (finite-dimensional) quantum mechanics can be transported down to sets resulting in quantum mechanics over sets or QM/sets. This approach leads to a different treatment of Dirac's brackets than in "modal quantum theory" (MQT), and that gives a full probability calculus (unlike MQT that only has zero-one modalities of impossible and possible). That, in turn, leads to a rather fulsome theory of QM over sets that includes "logical" models of the double-slit experiment, Bell's Theorem, quantum information theory, quantum computing, and much else. Indeed, QM/sets is proposed as the "logic" of QM in the old-fashioned sense of "logic" as giving the simplified essentials of a theory. QM/sets is also a key part of a broader research program to provide an interpretation of QM based on the notion of "objective indefiniteness," a program that grew out the recent development of the logic of partitions mathematically dual to the usual Boolean logic of subsets.
Modal quantum theory (MQT) is a simplified cousin of ordinary Hilbert space quantum theory. We show that two important theorems of actual quantum theory, the Kochen-Specker theorem excluding non-contextual hidden variables and the Conway-Kochen "free will theorem" about entangled systems, have direct analogues in MQT. The structure of possible measurement results for an entangled system in MQT cannot be represented by probability assignments satisfying the no-signaling principle, such as those given by ordinary quantum theory.
We examine the toy model of modal quantum theory (MQT), an analogue of actual quantum theory based on finite fields. In particular, we investigate how several essential ``no-go'' results (for cloning, deleting and hiding processes) work in MQT. Cloning and deleting are still forbidden in MQT, though the details of these results are somewhat different in the new context. However, the information of a modal qubit can be completely hidden in the correlations between two entangled modal qubits.
Modal quantum theory (MQT) is a simplified cousin of ordinary Hilbert space quantum theory. We show that two important theorems of actual quantum theory, the Kochen-Specker theorem excluding non-contextual hidden variables and the Conway-Kochen "free will theorem" about entangled systems, have direct analogues in MQT. The proofs of these analogue theorems are similar to, but much simpler than, the originals. We also show that the structure of possible measurement results for an entangled system in MQT cannot be represented by probability assignments satisfying the no-signaling principle, such as those given by ordinary quantum theory.
Abstract Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA 1_11​ 1 -complete for k≥3k\ge 3k≥3 k ≥ 3 , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum k-SAT can be solved in randomised polynomial time given the ‘property testing’ promise that the instance is either satisfiable (by any state) or far from satisfiable by a product state; by ‘far from satisfiable by a product state’ we mean that ϵnk\epsilon n^kϵnk ϵ n k constraints must be removed before a product state solution exists, for some fixed ϵ>0\epsilon >0ϵ>0 ϵ > 0 . The proof has two steps: we first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum k-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.