Refutation of Quantum Predicate Logic with Equality

We develop a characterization of quantum states by means of first order variables and random variables, within a predicative logic with equality, in the framework of basic logic and its definitory equations. We introduce the notion of random first order domain and find a characterization of pure states in predicative logic and mixed states in propositional logic, due to a focusing condition. We discuss the role of first order variables and the related contextuality, in terms of sequents.

Aug 14, 20166 citations

Refutation of Quantum Predicate Logic with Equality

Colin James

Published Apr 1, 2020• 0 citations

OpenAlex

Related papers

Refutation of Orthomodular Quantum Logic

Colin James

Feb 1, 20200 citations

Quantum predicate logic with equality

Andre Kornell

The quantum propositional logic of Birkhoff and von Neumann is the logic of Boolean observables on a quantum system. The quantum predicate logic of Weaver extends this quantum propositional logic to a logic of Boolean observables on composite quantum systems. We investigate a variant of this quantum predicate logic in which the physical systems are modeled by hereditarily atomic von Neumann algebras. Such physical systems may be infinite-dimensional, but their superselection sectors are finite-dimensional. From the perspective of noncommutative mathematics, they are a quantum generalization of sets. We define an equality relation on each such quantum set. This definition allows us to axiomatize several classes of discrete quantum structures within quantum predicate logic, including quantum graphs, quantum groups and quantum metric spaces. We likewise characterize the quantum isomorphism of simple graphs. The proof that discrete quantum groups may be so axiomatized is due to Stefaan Vaes.The quantum propositional logic of Birkhoff and von Neumann is the logic of Boolean observables on a quantum system. The quantum predicate logic of Weaver extends this quantum propositional logic to a logic of Boolean observables on composite quantum systems. We investigate a variant of this quantum predicate logic in which the physical systems are modeled by hereditarily atomic von Neumann algebras. Such physical systems may be infinite-dimensional, but their superselection sectors are finite-dimensional. From the perspective of noncommutative mathematics, they are a quantum generalization of sets. We define an equality relation on each such quantum set. This definition allows us to axiomatize several classes of discrete quantum structures within quantum predicate logic, including quantum graphs, quantum groups and quantum metric spaces. We likewise characterize the quantum isomorphism of simple graphs. The proof that discrete quantum groups may be so axiomatized is due to Stefaan Vaes.

Apr 9, 20202 citations

Implicational quantum logic

Kenji Tokuo

AxiomathesJan 21, 20221 citation

Quantum logic revisited

Leopoldo Rom�n, B. Rumbos

Foundations of PhysicsJun 1, 199127 citations

The Kikuchi Hierarchy is Sharp for $k$ XOR

Alexander Schmidhuber, Matthew B. Hastings

Planted noisy $k$ XOR and the strong refutation of random $k$ XOR are governed by a conjectured trade-off between signal strength and time: Level $\ell$ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where $ρ$ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse $k$ XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $k\ge3$ . At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$ . We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.Planted noisy $k$XOR and the strong refutation of random $k$XOR are governed by a conjectured trade-off between signal strength and time: Level $\ell$ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where $ρ$ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse $k$XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $k\ge3$. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$. We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.

cs.DSCross-listedarXiv:2607.29672Aug 3, 2026

Characterization of quantum states in predicative logic

Giulia Battilotti

Aug 14, 20166 citations

Planted noisy

k

XOR and the strong refutation of random

k

XOR are governed by a conjectured trade-off between signal strength and time: Level

\ell

of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where

ρ

is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse

k

XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity

k\ge3

. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree

O_k(\ell)

. We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.