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

Complexity of Quantum Logic Satisfiability in Fixed Dimension: Realification and Rank-One Encodings

Higuchi, Joaquim Reizi

Published Jan 1, 2025• 0 citations
Publisher
DOI
10.13140/rg.2.2.24365.14560

Related papers

Complexity of Quantum Logic Satisfiability in Fixed Dimension: Realification and Rank-One Encodings

Higuchi, Joaquim Reizi

Quantum propositional logic, introduced by Birkhoff and von Neumann, formalizes reasoning about experimental propositions in quantum mechanics through closed subspaces of Hilbert spaces. We provide a comprehensive complexity analysis of the satisfiability problem for quantum logic formulas over the connectives conjunction, disjunction, and negation. Distinguishing between weak satisfiability (evaluation to a nonzero subspace) and strong satisfiability (evaluation to the full space), we establish that both notions coincide with Boolean satisfiability for dimension one, are classically NP complete for dimension two, and become complete for the Blum Shub Smale class NP_R when dimension d >= 3 is fixed. Our principal contribution is twofold. First, we present two alternative constructive reductions from quantum logic satisfiability to the Existential Theory of the Reals (ETR): a realification based encoding that explicitly handles the complex to real translation through commutant characterizations, and a rank one column encoding with orthogonal splitting gadgets. Both reductions yield polynomial size systems of quadratic equations for fixed dimension, proving membership in the complexity class existsR and hence in PSPACE via Cannys algorithm. Second, we provide detailed size bounds distinguishing weak and strong satisfiability: weak satisfiability encodes with O(n D^2 + N_v D) scalar variables where n is the number of atoms, D the real dimension, and N_v the number of disjunctions, while strong satisfiability requires O(n D^2 + N_v D^2) variables due to basis vector witnesses. When dimension is part of the input, strong satisfiability becomes polynomial time equivalent to feasibility of noncommutative integer polynomial equations. These results position quantum logic satisfiability precisely between classical NP and existsR, highlighting dimension as a fundamental complexity parameter.

•Nov 17, 2025•0 citations

A Formalism for Quantum Computing and a Satisfiability Problem

César Bautista-Ramos, M. Castro-Cardona, Alfred Zehe

Elsevier eBooks•Jan 1, 2005•0 citations

Computational Complexity of Quantum Satisfiability

Christian Herrmann, Martin Ziegler

Quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables. It generalizes, and on 1-dimensional Hilbert space coincides with, Boolean propositional logic. We introduce the weak and strong satisfiability problem for quantum logic terms. It turns out that in dimension two both are also NP-complete. For higher-dimensional spaces R^d and C^d with d>2 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale model of real computation. This provides a unified view on both Turing and real BSS complexity theory; and extends the still relatively scarce family of NP_R-complete problems with one perhaps closest in spirit to the classical Cook-Levin Theorem. Our investigations on the dimensions a term is weakly/strongly satisfiable in lead to satisfiability problems in indefinite finite and finally in infinite dimension. Here, strong satisfiability turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations

arXiv:1004.1696•Apr 10, 2010•0 citations

Expressiveness and Computational Complexity of Geometric Quantum Logic

Christian Herrmann, Martin Ziegler

•Apr 10, 2010•0 citations

Quantum Computational Logics: A Survey

María Luisa Dalla Chiara, Roberto Giuntini, Roberto Leporini

arXiv:quant-ph/0305029•Trends in logic•Jan 1, 2003•48 citations

Twisted Fiber Bundle Codes over Group Algebras

Chaobin Liu

We introduce a twisted fiber bundle construction of quantum CSS codes over group algebras \(R=\mathbb F_2[G]\), where each base generator carries a generator-dependent \(R\)-linear fiber twist satisfying a flatness condition. This construction extends the untwisted lifted product code, recovered when all twists are identities. We show that invertible twists (satisfying a flatness condition) give a complex chain-isomorphic to the untwisted one, so the resulting binary CSS codes have the same blocklength \(n\) and encoded dimension \(k\). In contrast, singular chain-compatible twists can lower boundary ranks and increase the number of logical qubits. Examples over \(R=\mathbb F_2[D_3]\) show that singular chain-compatible twists can increase the encoded dimension \(k\) at fixed blocklength \(n\), and in these finite examples the minimum distance \(d\) remains unchanged. This provides evidence that singular twisting enlarges the design space beyond the ordinary lifted product construction.

quant-pharXiv:2604.01478•Apr 3, 2026•0 citations
Quantum propositional logic, introduced by Birkhoff and von Neumann, formalizes reasoning about experimental propositions in quantum mechanics through closed subspaces of Hilbert spaces. We provide a comprehensive complexity analysis of the satisfiability problem for quantum logic formulas over the connectives conjunction, disjunction, and negation. Distinguishing between weak satisfiability (evaluation to a nonzero subspace) and strong satisfiability (evaluation to the full space), we establish that both notions coincide with Boolean satisfiability for dimension one, are classically NP complete for dimension two, and become complete for the Blum Shub Smale class NP_R when dimension d >= 3 is fixed. Our principal contribution is twofold. First, we present two alternative constructive reductions from quantum logic satisfiability to the Existential Theory of the Reals (ETR): a realification based encoding that explicitly handles the complex to real translation through commutant characterizations, and a rank one column encoding with orthogonal splitting gadgets. Both reductions yield polynomial size systems of quadratic equations for fixed dimension, proving membership in the complexity class existsR and hence in PSPACE via Cannys algorithm. Second, we provide detailed size bounds distinguishing weak and strong satisfiability: weak satisfiability encodes with O(n D^2 + N_v D) scalar variables where n is the number of atoms, D the real dimension, and N_v the number of disjunctions, while strong satisfiability requires O(n D^2 + N_v D^2) variables due to basis vector witnesses. When dimension is part of the input, strong satisfiability becomes polynomial time equivalent to feasibility of noncommutative integer polynomial equations. These results position quantum logic satisfiability precisely between classical NP and existsR, highlighting dimension as a fundamental complexity parameter.
Quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables. It generalizes, and on 1-dimensional Hilbert space coincides with, Boolean propositional logic. We introduce the weak and strong satisfiability problem for quantum logic terms. It turns out that in dimension two both are also NP-complete. For higher-dimensional spaces R^d and C^d with d>2 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale model of real computation. This provides a unified view on both Turing and real BSS complexity theory; and extends the still relatively scarce family of NP_R-complete problems with one perhaps closest in spirit to the classical Cook-Levin Theorem. Our investigations on the dimensions a term is weakly/strongly satisfiable in lead to satisfiability problems in indefinite finite and finally in infinite dimension. Here, strong satisfiability turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations
We introduce a twisted fiber bundle construction of quantum CSS codes over group algebras R=F2[G]R=\mathbb F_2[G]R=F2​[G], where each base generator carries a generator-dependent RRR-linear fiber twist satisfying a flatness condition. This construction extends the untwisted lifted product code, recovered when all twists are identities. We show that invertible twists (satisfying a flatness condition) give a complex chain-isomorphic to the untwisted one, so the resulting binary CSS codes have the same blocklength nnn and encoded dimension kkk. In contrast, singular chain-compatible twists can lower boundary ranks and increase the number of logical qubits. Examples over R=F2[D3]R=\mathbb F_2[D_3]R=F2​[D3​] show that singular chain-compatible twists can increase the encoded dimension kkk at fixed blocklength nnn, and in these finite examples the minimum distance ddd remains unchanged. This provides evidence that singular twisting enlarges the design space beyond the ordinary lifted product construction.