Picturing Counting Reductions with the ZH-Calculus

DOI10.4204/EPTCS.384.6arXiv2304.02524OpenAlexW4386095710MaRDI QIDQ6200526FDOQ6200526

Authors: Konstantinos Meichanetzidis, John van de Wetering 

Publication date: 22 March 2024

Published in: Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

Abstract: Counting the solutions to Boolean formulae defines the problem #SAT, which is complete for the complexity class #P. We use the ZH-calculus, a universal and complete graphical language for linear maps which naturally encodes counting problems in terms of diagrams, to give graphical reductions from #SAT to several related counting problems. Some of these graphical reductions, like to #2SAT, are substantially simpler than known reductions via the matrix permanent. Additionally, our approach allows us to consider the case of counting solutions modulo an integer on equal footing. Finally, since the ZH-calculus was originally introduced to reason about quantum computing, we show that the problem of evaluating ZH-diagrams in the fragment corresponding to the Clifford+T gateset, is in $$. Our results show that graphical calculi represent an intuitive and useful framework for reasoning about counting problems.

Full work available at URL: https://arxiv.org/abs/2304.02524

Recommendations

• Holant problems and counting CSP
• scientific article
• scientific article; zbMATH DE number 1759419
• Subtractive reductions and complete problems for counting complexity classes
• Complexity of generalized satisfiability counting problems

Mathematics Subject Classification ID

Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)

Cites Work

• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• The complexity of counting problems
• Title not available (Why is that?)
• Quantum computing, postselection, and probabilistic polynomial-time
• The complexity of computing the permanent
• Phase groups and the origin of non-locality for qubits
• Quantum computation and quantum information. 10th anniversary edition
• Interacting Quantum Observables
• The Complexity of Enumeration and Reliability Problems
• Planar Formulae and Their Uses
• Quantum Complexity Theory
• Interacting quantum observables: categorical algebra and diagrammatics
• The complexity of theorem-proving procedures
• The computational complexity of propositional STRIPS planning
• On the hardness of approximate reasoning
• The complexity of tensor calculus
• NP is as easy as detecting unique solutions
• A practical introduction to tensor networks: Matrix product states and projected entangled pair states
• The nature of computation
• Rewriting measurement-based quantum computations with generalised flow
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Superdense coding with GHZ and quantum key distribution with \(W\) in the \textsc{zx}-calculus
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hybrid quantum-classical circuit simplification with the ZX-calculus
• Picturing quantum processes. A first course in quantum theory and diagrammatic reasoning
• Quantum picturalism for topological cluster-state computing
• Theory and Applications of Models of Computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Verifying the Steane code with Quantomatic
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Picturing Counting Reductions with the ZH-Calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6200526)