Picturing Counting Reductions with the ZH-Calculus
arXiv:2304.02524 · doi:10.4204/EPTCS.384.6
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 FP^#P. Our results show that graphical calculi represent an intuitive and useful framework for reasoning about counting problems.
arXiv commentIn Proceedings QPL 2023, arXiv:2308.15489
References in corpus (25)
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- Improved Simulation of Stabilizer Circuits
- Interacting Quantum Observables: Categorical Algebra and Diagrammatics
- Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
- Hyper-optimized tensor network contraction
- Reducing T-count with the ZX-calculus
- Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
- Phase groups and the origin of non-locality for qubits
- Phase Gadget Synthesis for Shallow Circuits
- The ZX calculus is a language for surface code lattice surgery
- There and back again: A circuit extraction tale
- ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity
- Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
- Verifying the Steane code with Quantomatic
- Fast counting with tensor networks
- The Topology of Quantum Algorithms
- Quantum picturalism for topological cluster-state computing
- Universal MBQC with generalised parity-phase interactions and Pauli measurements
- Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus
- Tensor Network Rewriting Strategies for Satisfiability and Counting
- Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections
- Superdense Coding with GHZ and Quantum Key Distribution with W in the ZX-calculus
- Simplification Strategies for the Qutrit ZX-Calculus
- VyZX : A Vision for Verifying the ZX Calculus
- Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array