References

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