Complexity of Fermionic 2-SAT

Maarten Stroeks; Barbara M. Terhal

doi:10.22331/q-2025-10-31-1900

Complexity of Fermionic 2-SAT

Maarten Stroeks and Barbara M. Terhal

Delft Institute of Applied Mathematics, Delft University of Technology, The Netherlands
QuTech, Delft University of Technology, The Netherlands

Published:	2025-10-31, volume 9, page 1900
Editor:	Anurag Anshu
Eprint:	arXiv:2412.06383v3
Doi:	https://doi.org/10.22331/q-2025-10-31-1900
Citation:	Quantum 9, 1900 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We introduce the fermionic satisfiability problem, Fermionic $k$-SAT: this is the problem of deciding whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on $n$ fermionic modes, where each fermionic projector involves at most $k$ fermionic modes. We prove that this problem can be solved efficiently classically for $k=2$. In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA$_1$-hard.

Featured image: Cluster product form of solutions to Fermionic 2-SAT.

► BibTeX data

@article{Stroeks2025complexityof,
  doi = {10.22331/q-2025-10-31-1900},
  url = {https://doi.org/10.22331/q-2025-10-31-1900},
  title = {Complexity of {F}ermionic 2-{SAT}},
  author = {Stroeks, Maarten and Terhal, Barbara M.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1900},
  month = oct,
  year = {2025}
}

► References

[1] Bengt Aspvall, Michael F. Plass, and Robert Tarjan. ``A linear-time algorithm for testing the truth of certain quantified Boolean formulas''. Information Processing Letters 8, 121–123 (1979).
https://doi.org/10.1016/0020-0190(79)90002-4

[2] Sergey Bravyi. ``Efficient algorithm for a quantum analogue of 2-SAT''. In Contemporary Mathematics. Volume 536. American Mathematical Society (2011). arXiv:quant-ph/0602108.
arXiv:quant-ph/0602108

[3] Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang. ``Linear-time algorithm for ${Quantum 2-SAT}$''. Theory of Computing 14, 1–27 (2018).
https://doi.org/10.4086/toc.2018.v014a001

[4] Niel de Beaudrap and Sevag Gharibian. ``A Linear Time Algorithm for Quantum 2-SAT''. In 31st Conference on Computational Complexity (CCC 2016). Volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:21. Dagstuhl, Germany (2016). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CCC.2016.27

[5] David Gosset and Daniel Nagaj. ``Quantum 3-SAT is ${QMA_{1}}$-Complete''. In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. Page 756–765. FOCS '13USA (2013). IEEE Computer Society.
https://doi.org/10.1109/FOCS.2013.86

[6] Dorian Rudolph. ``Towards a universal gateset for ${QMA_{1}}$'' (2024). arXiv:2411.02681.
arXiv:2411.02681

[7] Sergey B. Bravyi and Alexei Yu. Kitaev. ``Fermionic quantum computation''. Annals of Physics 298, 210–226 (2002).
https://doi.org/10.1006/aphy.2002.6254

[8] Fernando de Melo, Piotr Cwiklinski, and Barbara M Terhal. ``The power of noisy fermionic quantum computation''. New Journal of Physics 15, 013015 (2013).
https://doi.org/10.1088/1367-2630/15/1/013015

[9] Christina V. Kraus, Michael M. Wolf, J. Ignacio Cirac, and Géza Giedke. ``Pairing in fermionic systems: A quantum-information perspective''. Physical Review A 79 (2009).
https://doi.org/10.1103/physreva.79.012306

[10] Jacopo Surace and Luca Tagliacozzo. ``Fermionic gaussian states: an introduction to numerical approaches''. SciPost Physics Lecture Notes (2022).
https://doi.org/10.21468/scipostphyslectnotes.54

[11] Zhengfeng Ji, Zhaohui Wei, and Bei Zeng. ``Complete characterization of the ground-space structure of two-body frustration-free Hamiltonians for qubits''. Phys. Rev. A 84, 042338 (2011).
https://doi.org/10.1103/PhysRevA.84.042338

[12] Aram W. Harrow. ``The church of the symmetric subspace'' (2013). arXiv:1308.6595.
arXiv:1308.6595

[13] Yaroslav Herasymenko, Anurag Anshu, Barbara M. Terhal, and Jonas Helsen. ``Fermionic Hamiltonians without trivial low-energy states''. Phys. Rev. A 109, 052431 (2024).
https://doi.org/10.1103/PhysRevA.109.052431

[14] Nikolas P Breuckmann and Barbara M Terhal. ``Space-time circuit-to-Hamiltonian construction and its applications''. Journal of Physics A: Mathematical and Theoretical 47, 195304 (2014).
https://doi.org/10.1088/1751-8113/47/19/195304

[15] Bryan O'Gorman, Sandy Irani, James Whitfield, and Bill Fefferman. ``Intractability of electronic structure in a fixed basis''. PRX Quantum 3, 020322 (2022).
https://doi.org/10.1103/PRXQuantum.3.020322

[16] Robbie King and Tamara Kohler. `` Gapped Clique Homology on Weighted Graphs is QMA1-Hard and Contained in QMA ''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 493–504. Los Alamitos, CA, USA (2024). IEEE Computer Society.
https://doi.org/10.1109/FOCS61266.2024.00039

[17] Marijn J. H. Heule, Oliver Kullmann, and Victor W. Marek. ``Solving and verifying the Boolean Pythagorean triples problem via cube-and-conquer''. In Nadia Creignou and Daniel Le Berre, editors, Theory and Applications of Satisfiability Testing – SAT 2016. Pages 228–245. Cham (2016). Springer International Publishing.
https://doi.org/10.1007/978-3-319-40970-2_15

[18] Alexei Kitaev. ``Periodic table for topological insulators and superconductors''. AIP Conference Proceedings 1134, 22–30 (2009).
https://doi.org/10.1063/1.3149495

[19] Robert Tarjan. ``Depth-first search and linear graph algorithms''. SIAM Journal on Computing 1, 146–160 (1972).
https://doi.org/10.1137/0201010

[20] Robert Tarjan. ``Edge-disjoint spanning trees and depth-first search''. Acta Informatica 6, 171–185 (1976).
https://doi.org/10.1007/BF00268499

[21] Tomás Feder. ``Network flow and 2-satisfiability''. Algorithmica 11, 291–319 (1994).
https://doi.org/10.1007/BF01240738

[22] Tomoyuki Morimae, Daniel Nagaj, and Norbert Schuch. ``Quantum proofs can be verified using only single-qubit measurements''. Physical Review A 93 (2016).
https://doi.org/10.1103/physreva.93.022326

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2026-07-15 16:24:15). On SAO/NASA ADS no data on citing works was found (last attempt 2026-07-15 16:24:18).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.