@article(achlioptas_rigorous_2005, author = {Dimitris Achlioptas and Assaf Naor and Yuval Peres}, year = {2005}, title = {Rigorous Location of Phase Transitions in Hard Optimization Problems}, journal = {Nature}, volume = {435}, number = {7043}, pages = {759--764}, doi = {10.1038/nature03602}, ) @article(Backens1, author = {Miriam Backens}, year = {2014}, title = {{The ZX-calculus is complete for stabilizer quantum mechanics}}, journal = {New Journal of Physics}, volume = {16}, number = {9}, pages = {093021}, doi = {10.1088/1367-2630/16/9/093021}, ) @article(backens_zh_2019, author = {Miriam Backens and Aleks Kissinger}, year = {2019}, title = {{{ZH}}: {{A Complete Graphical Calculus}} for {{Quantum Computations Involving Classical Non-linearity}}}, journal = {Electronic Proceedings in Theoretical Computer Science}, volume = {287}, pages = {23--42}, doi = {10.4204/EPTCS.287.2}, eprint = {1805.02175}, ) @misc(backens_completeness_2021, author = {Miriam Backens and Aleks Kissinger and {Miller-Bakewell}, Hector and {van de Wetering}, John and Sal Wolffs}, year = {2021}, title = {Completeness of the {{ZH-calculus}}}, doi = {10.48550/arXiv.2103.06610}, eprint = {2103.06610}, ) @article(Backens2020extraction, author = {Miriam Backens and Miller-Bakewell, Hector and Giovanni de Felice and Leo Lobski and John van de Wetering}, year = {2021}, title = {{There and back again: A circuit extraction tale}}, journal = {{Quantum}}, volume = {5}, pages = {421}, doi = {10.22331/q-2021-03-25-421}, ) @inproceedings(deBeaudrap2020Techniques, author = {Niel de Beaudrap and Xiaoning Bian and Quanlong Wang}, year = {2020}, title = {{Techniques to Reduce $\pi/4$-Parity-Phase Circuits, Motivated by the ZX Calculus}}, editor = {Bob Coecke and Matthew Leifer}, booktitle = {Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019}, series = {Electronic Proceedings in Theoretical Computer Science}, volume = {318}, publisher = {Open Publishing Association}, pages = {131--149}, doi = {10.4204/EPTCS.318.9}, ) @book(biere_handbook_2009, author = {A. Biere and M. Heule and {van Maaren}, H.}, year = {2009}, title = {Handbook of {{Satisfiability}}}, publisher = {{IOS Press, Incorporated}}, doi = {10.3233/FAIA336}, ) @article(birnbaum_good_1999, author = {E. Birnbaum and E. L. Lozinskii}, year = {1999}, title = {The {{Good Old Davis-Putnam Procedure Helps Counting Models}}}, journal = {Journal of Artificial Intelligence Research}, volume = {10}, pages = {457--477}, doi = {10.1613/jair.601}, eprint = {1106.0218}, ) @inproceedings(Boisseau2022Graphical, author = {Guillaume Boisseau and Robin Piedeleu}, year = {2022}, title = {Graphical Piecewise-Linear Algebra}, editor = {Patricia Bouyer and Lutz Schr{\"o}der}, booktitle = {Foundations of Software Science and Computation Structures}, publisher = {{Springer International Publishing}}, address = {{Cham}}, pages = {101--119}, doi = {10.1007/978-3-030-99253-8\_6}, ) @article(Bonchi2019Diagrammatic, author = {Filippo Bonchi and Joshua Holland and Robin Piedeleu and Pawe\l{} Soboci\'{n}ski and Fabio Zanasi}, year = {2019}, title = {Diagrammatic Algebra: From Linear to Concurrent Systems}, journal = {Proc. ACM Program. Lang.}, volume = {3}, number = {POPL}, doi = {10.1145/3290338}, ) @inproceedings(Bonchi2019Graphical, author = {Filippo Bonchi and Robin Piedeleu and Pawel Sobociński and Fabio Zanasi}, year = {2019}, title = {Graphical Affine Algebra}, booktitle = {2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}, pages = {1--12}, doi = {10.1109/LICS.2019.8785877}, ) @inproceedings(Bonchi2014Categorical, author = {Filippo Bonchi and Pawe{\l} Soboci{\'n}ski and Fabio Zanasi}, year = {2014}, title = {A {{Categorical Semantics}} of {{Signal Flow Graphs}}}, editor = {Paolo Baldan and Daniele Gorla}, booktitle = {{{CONCUR}} 2014 \textendash{} {{Concurrency Theory}}}, publisher = {{Springer Berlin Heidelberg}}, address = {{Berlin, Heidelberg}}, pages = {435--450}, doi = {10.1007/978-3-662-44584-6\_30}, ) @article(BONCHI2017144, author = {Filippo Bonchi and Pawe{\l} Soboci{\'n}ski and Fabio Zanasi}, year = {2017}, title = {Interacting {{Hopf}} Algebras}, journal = {Journal of Pure and Applied Algebra}, volume = {221}, number = {1}, pages = {144--184}, doi = {10.1016/j.jpaa.2016.06.002}, ) @article(cerveromartin2022barren, author = {Cervero Martín, Enrique and Kirill Plekhanov and Michael Lubasch}, year = {2022}, title = {{Barren plateaus in quantum tensor network optimization}}, doi = {10.48550/arXiv.2209.00292}, eprint = {2209.00292}, ) @inproceedings(CD1, author = {Bob Coecke and Ross Duncan}, year = {2008}, title = {Interacting quantum observables}, booktitle = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)}, series = {Lecture Notes in Computer Science}, doi = {10.1007/978-3-540-70583-3\_25}, ) @article(coecke_interacting_2011, author = {Bob Coecke and Ross Duncan}, year = {2011}, title = {Interacting {{Quantum Observables}}: {{Categorical Algebra}} and {{Diagrammatics}}}, journal = {New Journal of Physics}, volume = {13}, number = {4}, pages = {043016}, doi = {10.1088/1367-2630/13/4/043016}, eprint = {0906.4725}, ) @article(damm_complexity_2002, author = {Carsten Damm and Markus Holzer and Pierre McKenzie}, year = {2002}, title = {The Complexity of Tensor Calculus}, journal = {Computational Complexity}, volume = {11}, number = {1/2}, pages = {54--89}, doi = {10.1007/s00037-000-0170-4}, ) @article(davis_machine_1962, author = {Martin Davis and George Logemann and Donald Loveland}, year = {1962}, title = {A Machine Program for Theorem-Proving}, journal = {Communications of the ACM}, volume = {5}, number = {7}, pages = {394--397}, doi = {10.1145/368273.368557}, ) @article(de_beaudrap_tensor_2021, author = {{de Beaudrap}, Niel and Aleks Kissinger and Konstantinos Meichanetzidis}, year = {2021}, title = {Tensor {{Network Rewriting Strategies}} for {{Satisfiability}} and {{Counting}}}, journal = {Electronic Proceedings in Theoretical Computer Science}, volume = {340}, pages = {46--59}, doi = {10.4204/EPTCS.340.3}, eprint = {2004.06455}, ) @article(dubois_counting_1991, author = {Olivier Dubois}, year = {1991}, title = {Counting the Number of Solutions for Instances of Satisfiability}, journal = {Theoretical Computer Science}, volume = {81}, number = {1}, pages = {49--64}, doi = {10.1016/0304-3975(91)90315-S}, ) @article(cliffsimp, author = {Ross Duncan and Aleks Kissinger and Simon Perdrix and John van de Wetering}, year = {2020}, title = {{Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus}}, journal = {{Quantum}}, volume = {4}, pages = {279}, doi = {10.22331/q-2020-06-04-279}, ) @article(d.p.east2021spinnetworks, author = {Richard D. P. East and Martin-Dussaud, Pierre and John van de Wetering}, year = {2021}, title = {{Spin-networks in the ZX-calculus}}, doi = {10.48550/arXiv.2111.03114}, eprint = {2111.03114}, ) @article(fenner_gap-definable_1994, author = {Stephen A Fenner and Lance J Fortnow and Stuart A Kurtz}, year = {1994}, title = {Gap-Definable Counting Classes}, journal = {Journal of Computer and System Sciences}, volume = {48}, number = {1}, pages = {116--148}, doi = {10.1016/S0022-0000(05)80024-8}, ) @misc(fichte_model_2020, author = {Johannes K. Fichte and Markus Hecher and Florim Hamiti}, year = {2020}, title = {The {{Model Counting Competition}} 2020}, doi = {10.48550/arXiv.2012.01323}, eprint = {2012.01323}, ) @inproceedings(furer_algorithms_2007, author = {Martin F{\"u}rer and Shiva Prasad Kasiviswanathan}, year = {2007}, title = {Algorithms for {{Counting}} 2-{{Sat Solutions}} and {{Colorings}} with {{Applications}}}, editor = {Ming-Yang Kao and Xiang-Yang Li}, booktitle = {Algorithmic {{Aspects}} in {{Information}} and {{Management}}}, series = {Lecture {{Notes}} in {{Computer Science}}}, publisher = {{Springer}}, address = {{Berlin, Heidelberg}}, pages = {47--57}, doi = {10.1007/978-3-540-72870-2\_5}, ) @article(magicFactories, author = {Craig Gidney and Austin G. Fowler}, year = {2019}, title = {{Efficient magic state factories with a catalyzed {$|CCZ\rangle$} to {$2|T\rangle$} transformation}}, journal = {{Quantum}}, volume = {3}, pages = {135}, doi = {10.22331/q-2019-04-30-135}, ) @article(gu2022complete, author = {Tao Gu and Robin Piedeleu and Fabio Zanasi}, year = {2022}, title = {A Complete Diagrammatic Calculus for Boolean Satisfiability}, doi = {10.48550/arXiv.2211.12629}, eprint = {2211.12629}, ) @inproceedings(hadzihasanovic2015diagrammatic, author = {Amar Hadzihasanovic}, year = {2015}, title = {A diagrammatic axiomatisation for qubit entanglement}, booktitle = {2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science}, organization = {IEEE}, pages = {573--584}, doi = {10.1109/LICS.2015.59}, ) @inproceedings(HarnyAmarCompleteness, author = {Amar Hadzihasanovic and Kang Feng Ng and Quanlong Wang}, year = {2018}, title = {{Two Complete Axiomatisations of Pure-state Qubit Quantum Computing}}, booktitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science}, series = {LICS '18}, publisher = {ACM}, address = {New York, NY, USA}, pages = {502--511}, doi = {10.1145/3209108.3209128}, ) @article(hanks2019effective, author = {Michael Hanks and P. Estarellas, Marta and J. Munro, William and Kae Nemoto}, year = {2020}, title = {{Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus}}, journal = {Physical Review X}, volume = {10}, pages = {041030}, doi = {10.1103/PhysRevX.10.041030}, ) @inproceedings(SimonCompleteness, author = {Emmanuel Jeandel and Simon Perdrix and Renaud Vilmart}, year = {2018}, title = {{A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum Mechanics}}, booktitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science}, series = {LICS '18}, publisher = {ACM}, address = {New York, NY, USA}, pages = {559--568}, doi = {10.1145/3209108.3209131}, ) @article(kissinger2019tcount, author = {Aleks Kissinger and John van de Wetering}, year = {2020}, title = {{Reducing the number of non-Clifford gates in quantum circuits}}, journal = {Physical Review A}, volume = {102}, pages = {022406}, doi = {10.1103/PhysRevA.102.022406}, ) @article(kissinger2021simulating, author = {Aleks Kissinger and John van de Wetering}, year = {2022}, title = {{Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions}}, journal = {Quantum Science and Technology}, volume = {7}, number = {4}, pages = {044001}, doi = {10.1088/2058-9565/ac5d20}, ) @inproceedings(kissinger2022classical, author = {Aleks Kissinger and John van de Wetering and Renaud Vilmart}, year = {2022}, title = {{Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions}}, editor = {Le Gall, Fran\c{c}ois and Tomoyuki Morimae}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, volume = {232}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, pages = {5:1--5:13}, doi = {10.4230/LIPIcs.TQC.2022.5}, ) @article(kutzkov_new_2007, author = {Konstantin Kutzkov}, year = {2007}, title = {New Upper Bound for the \#3-{{SAT}} Problem}, journal = {Information Processing Letters}, volume = {105}, number = {1}, pages = {1--5}, doi = {10.1016/j.ipl.2007.06.017}, ) @mastersthesis(laakkonen_graphical_2022, author = {Tuomas Laakkonen}, year = {2022}, title = {Graphical {{Stabilizer Decompositions For Counting Problems}}}, school = {University of Oxford}, url = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/laakkonen-thesis.pdf}, ) @article(laakkonen_2023, author = {Tuomas Laakkonen and Konstantinos Meichanetzidis and John van de Wetering}, year = {2023}, title = {Picturing Counting Reductions with the ZH-Calculus}, journal = {Electronic Proceedings in Theoretical Computer Science}, volume = {384}, pages = {89–113}, doi = {10.4204/eptcs.384.6}, ) @misc(ng_completeness_2018, author = {Kang Feng Ng and Quanlong Wang}, year = {2018}, title = {Completeness of the {{ZX-calculus}} for {{Pure Qubit Clifford}}+{{T Quantum Mechanics}}}, doi = {10.48550/arXiv.1801.07993}, eprint = {1801.07993}, ) @article(orus_practical_2014, author = {Rom{\'{a}}n Or{\'{u}}s}, year = {2014}, title = {A practical introduction to tensor networks: Matrix product states and projected entangled pair states}, journal = {Annals of Physics}, volume = {349}, pages = {117--158}, doi = {10.1016/j.aop.2014.06.013}, ) @misc(peng_further_2021, author = {Junqiang Peng and Mingyu Xiao}, year = {2021}, title = {Further Improvements for SAT in Terms of Formula Length}, doi = {10.48550/arXiv.2105.06131}, eprint = {2105.06131}, ) @inproceedings(Piedeleu2021stringdiagrammatic, author = {Robin Piedeleu and Fabio Zanasi}, year = {2021}, title = {A String Diagrammatic Axiomatisation of Finite-State Automata}, editor = {Stefan Kiefer and Christine Tasson}, booktitle = {Foundations of Software Science and Computation Structures}, publisher = {{Springer International Publishing}}, address = {{Cham}}, pages = {469--489}, doi = {10.1007/978-3-030-71995-1\_24}, ) @inproceedings(sang_combining_2004, author = {Tian Sang and Fahiem Bacchus and Paul Beame and Henry A. Kautz and Toniann Pitassi}, year = {2004}, title = {Combining {{Component Caching}} and {{Clause Learning}} for {{Effective Model Counting}}}, booktitle = {{{SAT}} 2004 - {{The Seventh International Conference}} on {{Theory}} and {{Applications}} of {{Satisfiability Testing}}, 10-13 {{May}} 2004, {{Vancouver}}, {{BC}}, {{Canada}}, {{Online Proceedings}}}, ) @inproceedings(thurley_sharpsat_2006, author = {Marc Thurley}, year = {2006}, title = {{{sharpSAT}} \textendash{} {{Counting Models}} with {{Advanced Component Caching}} and {{Implicit BCP}}}, editor = {Armin Biere and Carla P. Gomes}, booktitle = {Theory and {{Applications}} of {{Satisfiability Testing}} - {{SAT}} 2006}, series = {Lecture {{Notes}} in {{Computer Science}}}, publisher = {{Springer}}, address = {{Berlin, Heidelberg}}, pages = {424--429}, doi = {10.1007/11814948\_38}, ) @article(toda_pp_1991, author = {Seinosuke Toda}, year = {1991}, title = {{{PP}} Is as {{Hard}} as the {{Polynomial-Time Hierarchy}}}, journal = {SIAM Journal on Computing}, volume = {20}, number = {5}, pages = {865--877}, doi = {10.1137/0220053}, ) @article(townsend-teague2021classifying, author = {Townsend-Teague, Alex and Konstantinos Meichanetzidis}, year = {2021}, title = {{Classifying Complexity with the ZX-Calculus: Jones Polynomials and Potts Partition Functions}}, doi = {10.48550/arXiv.2103.06914}, eprint = {2103.06914}, ) @article(valiant_complexity_1979, author = {Leslie G. Valiant}, year = {1979}, title = {The {{Complexity}} of {{Enumeration}} and {{Reliability Problems}}}, journal = {SIAM Journal on Computing}, volume = {8}, number = {3}, pages = {410--421}, doi = {10.1137/0208032}, ) @inproceedings(vilmarteulercompleteness, author = {Renaud Vilmart}, year = {2019}, title = {{A Near-Minimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics}}, booktitle = {2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}, pages = {1--10}, doi = {10.1109/LICS.2019.8785765}, ) @article(vilmart_zx-calculus_2019, author = {Renaud Vilmart}, year = {2019}, title = {A {{ZX-Calculus}} with {{Triangles}} for {{Toffoli-Hadamard}}, {{Clifford}}+{{T}}, and {{Beyond}}}, journal = {Electronic Proceedings in Theoretical Computer Science}, volume = {287}, pages = {313--344}, doi = {10.4204/EPTCS.287.18}, eprint = {1804.03084}, ) @inproceedings(vilmart2021quantum, author = {Renaud Vilmart}, year = {2021}, title = {{Quantum Multiple-Valued Decision Diagrams in Graphical Calculi}}, editor = {Filippo Bonchi and Simon J. Puglisi}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, volume = {202}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, pages = {89:1--89:15}, doi = {10.4230/LIPIcs.MFCS.2021.89}, ) @inproceedings(pathsRenaud, author = {Renaud Vilmart}, year = {2021}, title = {The Structure of Sum-over-Paths, Its Consequences, and Completeness for Clifford}, editor = {Stefan Kiefer and Christine Tasson}, booktitle = {Foundations of Software Science and Computation Structures}, publisher = {{Springer International Publishing}}, address = {{Cham}}, pages = {531--550}, doi = {10.1007/978-3-030-71995-1\_27}, ) @inproceedings(wahlstrom_tighter_2008, author = {Magnus Wahlstr{\"o}m}, year = {2008}, title = {A {{Tighter Bound}} for {{Counting Max-Weight Solutions}} to {{2SAT Instances}}}, editor = {Martin Grohe and Rolf Niedermeier}, booktitle = {Parameterized and {{Exact Computation}}}, series = {Lecture {{Notes}} in {{Computer Science}}}, publisher = {{Springer}}, address = {{Berlin, Heidelberg}}, pages = {202--213}, doi = {10.1007/978-3-540-79723-4\_19}, ) @inproceedings(wang_worst_2013, author = {Honglin Wang and Wenxiang Gu}, year = {2013}, title = {The {{Worst Case Minimized Upper Bound}} in \#2-{{SAT}}}, editor = {Wei Lu and Guoqiang Cai and Weibin Liu and Weiwei Xing}, booktitle = {Proceedings of the 2012 {{International Conference}} on {{Information Technology}} and {{Software Engineering}}}, series = {Lecture {{Notes}} in {{Electrical Engineering}}}, publisher = {{Springer}}, address = {{Berlin, Heidelberg}}, pages = {675--682}, doi = {10.1007/978-3-642-34522-7\_72}, ) @inproceedings(Wang2019Algebraic, author = {Quanlong Wang}, year = {2021}, title = {{An Algebraic Axiomatisation of ZX-calculus}}, editor = {Beno\^it Valiron and Shane Mansfield and Pablo Arrighi and Prakash Panangaden}, booktitle = {Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020}, series = {Electronic Proceedings in Theoretical Computer Science}, volume = {340}, publisher = {Open Publishing Association}, pages = {303--332}, doi = {10.4204/EPTCS.340.16}, ) @article(vandewetering2020zxcalculus, author = {John van de Wetering}, year = {2020}, title = {{ZX-calculus for the working quantum computer scientist}}, doi = {10.48550/arXiv.2012.13966}, eprint = {2012.13966}, ) @inproceedings(williams_computing_2004, author = {Ryan Williams}, year = {2004}, title = {On {{Computing K-CNF Formula Properties}}}, editor = {Enrico Giunchiglia and Armando Tacchella}, booktitle = {Theory and {{Applications}} of {{Satisfiability Testing}}}, series = {Lecture {{Notes}} in {{Computer Science}}}, publisher = {{Springer}}, address = {{Berlin, Heidelberg}}, pages = {330--340}, doi = {10.1007/978-3-540-24605-3\_25}, ) @inproceedings(yamamoto_improved_2005-1, author = {Masaki Yamamoto}, year = {2005}, title = {An {{Improved O}}(1.234{\^m})-{{Time Deterministic Algorithm}} for {{SAT}}}, editor = {Xiaotie Deng and Ding-Zhu Du}, booktitle = {Algorithms and {{Computation}}}, series = {Lecture {{Notes}} in {{Computer Science}}}, publisher = {{Springer}}, address = {{Berlin, Heidelberg}}, pages = {644--653}, doi = {10.1007/11602613\_65}, ) @phdthesis(zanasi2015thesis, author = {Fabio Zanasi}, year = {2015}, title = {Interacting Hopf Algebras: the theory of linear systems}, school = {Ecole Normale Superieure de Lyon}, doi = {10.48550/arXiv.1805.03032}, note = {Available at \url{https://arxiv.org/abs/1805.03032}}, ) @inproceedings(zhou_new_2010, author = {Junping Zhou and Minghao Yin and Chunguang Zhou}, year = {2010}, title = {New Worst-Case Upper Bound for \#2-{{SAT}} and \#3-{{SAT}} with the Number of Clauses as the Parameter}, booktitle = {Proceedings of the {{Twenty-Fourth AAAI Conference}} on {{Artificial Intelligence}}}, series = {{{AAAI}}'10}, publisher = {{AAAI Press}}, address = {{Atlanta, Georgia}}, pages = {217--222}, doi = {10.48550/arXiv.1006.1537}, )