Picturing Counting Reductions with the ZH-Calculus

DOI10.4204/EPTCS.384.6MaRDI QIDQ6200526zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)