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. 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 1 -complete for k≥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 ϵ n k constraints must be removed before a product state solution exists, for some fixed ϵ>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.