# Dr Miriam Backens

## Lecturer

# Research Interests

I am a member of the Theory of Computation group. My research interests are in quantum computation and quantum information theory, as well as algorithms and computational complexity. Within quantum computation, my main focus is on properties and applications of different representations of quantum computations, in particular graphical formalisms such as the ZX-calculus. Within algorithms and computational complexity, I am particularly interested in the complexity of counting problems in the holant and counting CSP frameworks (which are closely related to certain notions of classical simulation of quantum computations).

I am an editor for the open-access Quantum Journal.

I am also interested in equality and diversity issues in computer science teaching.

# PhD students

- Tommy McElvanney (2020-)
- Piotr Mitosek (2021-)
- George Kaye (2020-)

# Upcoming events

- Recruitment for participants in my education research project "Co-creating an 'EDI in computer science teaching' toolkit".

# Teaching

- Spring 2023: Quantum Computing (and extended version)
- Autumn 2021: Mathematical and Logical Foundations of Computer Science
- Autumn 2021: Object-Oriented Programming / Software Workshop 1 / YiCS Software Workshop 1
- Spring 2021: Full Stack Application Development / Software Workshop 2 / YiCS Software Workshop 2
- Autumn 2020: Object-Oriented Programming / Software Workshop 1 / YiCS Software Workshop 1
- Spring 2020: MSc Software workshop (semester 2) / ICY Software Workshop (semester 2)

# Publications

- Tommy McElvanney and Miriam Backens (2023), Flow-preserving ZX-calculus rewrite rules for optimisation and obfuscation. arXiv:2304.08166.
- Tommy McElvanney and Miriam Backens (2022), Complete flow-preserving rewrite rules for MBQC patterns with Pauli measurements, to appear in QPL 2022. arXiv:2205.02009.
- Miriam Backens (2021), A full dichotomy for Holant
^{c}, inspired by quantum computation. SIAM Journal on Computing 50(6), pp. 1739-1799. arXiv:2201.03375. - Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering, and Sal Wolffs (2021), Completeness of the ZH-calculus, to appear in Compositionality. arXiv:2103.06610.
- Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering (2021), There and back again: A circuit extraction tale. Quantum 5, p. 421. arXiv:2003.01664.
- Miriam Backens and Leslie Ann Goldberg (2020), Holant clones and the approximability of conservative holant problems. ACM Transactions on Algorithms 16(2), pp. 23:1-23:55. arXiv:1811.00817.
- Miriam Backens and Aleks Kissinger (2018), ZH: A complete graphical calculus for quantum computations involving classical non-linearity. In
*Proceedings of the 15th Workshop on Quantum Physics and Logic*(QPL 2018),*EPTCS*287, 2019, pp. 23-42. arXiv:1805.02175. - Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan and Stanislav Živný (2020), Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. Journal of Computer and Systems Sciences 109, pp. 95-125. arXiv:1804.04993.
- Miriam Backens, Simon Perdrix, and Qualong Wang (2020), Towards a Minimal Stabilizer ZX-calculus. Logical Methods in Computer Science 16(4), pp. 19:1-19:30. arXiv:1709.08903.
- Miriam Backens (2018), A complete dichotomy for complex-valued Holant
^{c}. In*Proceedings of the 45th International Colloquium on Automata, Languages, and Programming*(ICALP 2018),*LIPIcs*107, pp. 12:1-12:14. arXiv:1704.05798. - Miriam Backens (2017), A new Holant dichotomy inspired by quantum computation. In
*Proceedings of the 44th International Colloquium on Automata, Languages, and Programming*(ICALP 2017),*LIPIcs*80, pp. 16:1-16:14. arXiv:1702.00767. - Miriam Backens (2017), Number of superclasses of four-qubit entangled states under the inductive entanglement classification. Physical Review A 95, p. 022329. arXiv:1611.02076.
- Miriam Backens, Simon Perdrix and Quanlong Wang (2016), A Simplified Stabilizer ZX-calculus. In
*Proceedings of the 13th Workshop on Quantum Physics and Logic*(QPL 2016),*EPTCS*236, pp. 1-20. arXiv:1602.04744. - Miriam Backens (2015), Making the stabilizer ZX-calculus complete for scalars. In
*Proceedings of the 12th Workshop on Quantum Physics and Logic*(QPL 2015),*EPTCS*195, pp. 17-32. arXiv:1507.03854. - Miriam Backens (2015), The ZX-calculus is complete for the single-qubit Clifford+T group. In
*Proceedings of the 11th Workshop on Quantum Physics and Logic*(QPL 2014),*EPTCS*172, pp. 293-303. arXiv:1412.8553. - Miriam Backens and Ali Nabi Duman (2015), A complete graphical calculus for Spekkens' toy bit theory. Foundations of Physics 46(1), pp. 70-103. arXiv:1411.1618.
- Miriam Backens (2014), The ZX-calculus is complete for stabilizer quantum mechanics. New Journal of Physics 16(9), p. 093021. arXiv:1307.7025.

# Talks

- March 2023: "Co-creating an 'EDI in computer science teaching' toolkit", lightning talk at the SIGCSE 2023 Technical Symposium
- November 2022: "Holant clones and approximation of holant problems". Dagstuhl Seminar 22482, Counting and Sampling: Algorithms and Complexity
- March 2022: "Optimisation of quantum computations using the graphical ZX-calculus". Journées Nationales de l'Informatique Mathématique, Université de Lille, France (invited).
- January 2022: "Quantum computing and the classical complexity of computational counting". CQIF Seminar, University of Cambridge (invited).
- May 2021: "Counting complexity and quantum information theory". Combinatorics Seminar, University of Birmingham (invited).
- November 2020: "There and back again: A circuit extraction tale". Q-Turn: changing paradigms in quantum science.
- October 2020: "Classical complexity of counting problems via quantum computing". London Hopper Colloquium (invited).
- April 2020: "Counting complexity and quantum information theory". DIMAP seminar, University of Warwick (invited).
- November 2019: "Categorical quantum computing using the ZX-calculus" Postgraduate Conference in Category Theory and its Applications, Leicester (invited).
- September 2019: "Optimising quantum computations using the ZX-calculus". Symposium on Quantum Computing and AI: Technology, Techniques and Ethics, Birmingham (invited).
- September 2019: "Holant problems and quantum information theory". Theoretical Computer Science Seminar, Shanghai University of Finance and Economics, Shanghai, China (invited).
- May 2019: "Using the completeness of the ZX-calculus to classify the complexity of computational counting problems". Quantum Group Workshop, University of Oxford.
- November 2018: "Quantum computing and holant problems". Q-Turn: changing paradigms in quantum science, Florianópolis, Brazil (invited).
- November 2018, "Classifying the computational complexity of counting problems". Seminar at the School of Mathematics, Statistics, and Applied Mathematics, National University of Ireland Galway, Ireland (invited).
- October 2018, "Quantum computing and holant problems". Quantum Innovators in computer science and mathematics, Institute for Quantum Computing, University of Waterloo, Canada (invited).
- October 2018, "Completing the ZX-calculus". Theoretical computer science seminar, School of Computer Science, University of Birmingham (invited).
- July 2018, "Holant problems and quantum information theory". Queen Mary Algorithms Day, Queen Mary University of London (invited).
- July 2018, "A complete dichotomy for complex-valued Holant
^{c}", 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic. - May 2018, "The future of the ZX-calculus". Oxford Advanced Seminar on Informatic Structures, Department of Computer Science, University of Oxford (invited).
- May 2018, "The ZH-calculus". Workshop Celebrating 10 Years of the ZX-calculus, University of Oxford.
- January 2018, "Quantum computing and holant problems". 21st Annual Conference on Quantum Information Processing (QIP 2018), Delft University of Technology, Delft, the Netherlands.
- October 2017, "Holant problems and quantum information theory". Algorithms and Complexity Theory Seminar, Department of Computer Science, University of Oxford (invited).
- August 2017, "Holant problems and quantum information theory". Dagstuhl Seminar 17341 "Computational Counting", Schloss Dagstuhl — Leibniz-Zentrum für Informatik, Dagstuhl, Germany (invited).
- July 2017, "The ZX-calculus and completeness". Joint talk at the 14th Workshop on Quantum Physics and Logic (QPL 2017) and the Workshop on Quantum Structures organised by the International Quantum Structures Association (IQSA), Nijmegen, the Netherlands (invited).
- July 2017, "A new holant dichotomy inspired by quantum computation". 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), University of Warsaw, Poland.
- June 2017, "A new holant dichotomy inspired by quantum computation". 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), Université Pierre et Marie Curie, Paris, France.
- May 2017, "A new holant dichotomy inspired by quantum computation". 14th Central European Quantum Information Processing Workshop (CEQIP 2017), Smolenice, Slovakia.
- April 2017, "The holant problem and classical simulation of quantum computations". Quantum Information Theory Group Seminar, University of Bristol (invited).
- November 2016, "The holant problem and classical simulation of quantum computations". Oxford Advanced Seminar on Informatic Structures, Department of Computer Science, University of Oxford (invited).
- June 2016, "A simplified stabilizer ZX-calculus". 13th Workshop on Quantum Physics and Logic (QPL 2016), University of Strathclyde, Glasgow.
- October 2015, "Completeness Results for Graphical Quantum Process Languages". Centre for Quantum Information and Foundations Seminar, Department of Applied Mathematics and Theoretical Physics, University of Cambridge (invited).
- July 2015, "Making the stabilizer ZX-calculus complete for scalars". 12th Workshop on Quantum Physics and Logic (QPL 2015), University of Oxford.
- December 2014, "Completeness Results for Graphical Quantum Process Languages". Perimeter Institute Quantum Discussions, Perimeter Institute, Waterloo, Ontario, Canada (invited).
- October 2014, "(In)Completeness results for the ZX-calculus". Workshop Celebrating 10 Years of Categorical Quantum Mechanics, University of Oxford.
- June 2014, "Completeness results for the ZX-calculus for quantum computation". Department of Computer Science Student Conference, University of Oxford (joint winner of prize for best talk).
- June 2014, "The ZX-calculus is approximately complete for single qubits". 11th Workshop on Quantum Physics and Logic (QPL 2014), Kyoto University, Kyoto, Japan.
- April 2013, "The ZX-calculus is complete for stabilizer quantum mechanics". Postgraduate Conference on Quantum Fields, Gravity and Information, University of Nottingham.
- March 2013, "The ZX-calculus is complete for stabilizer quantum mechanics". Second Workshop on Quantum Foundations, Bellairs Research Centre, McGill University, Holetown, Barbados (invited).
- October 2012, "The ZX-calculus is complete for stabilizer quantum mechanics". 9th Workshop on Quantum Physics and Logic (QPL 2012), Université Libre de Bruxelles, Brussels, Belgium.

# Outreach

- February 2018: Talk on "Quantum Computing in Science and Fiction" to the Oxford University Speculative Fiction Group.
- May 2017: Scientific guest speaker in two events of "This Moment Now" by Sylvia Rimat, an interactive art project and workshop on perceptions of time.
- January-April 2017: Participant/trainee in "Participatory Engagement with Scientific and Technological Research through Performance (PERFORM)".

# Miscellaneous

- Slides from the "Introduction to quantum computing" talk for CSS on 23rd November 2022.