PhD Position – Determinism and circuit extraction beyond flow

Type de contrat : CDD Contexte et atouts du poste Over the last years, there has been significant progress in quantum computing, on both the theoretical and practical sides. The first experimental demonstrations of quantum error correction provide evidence that large-scale quantum computing will be achievable. Nevertheless, quantum computational resources will remain limited for some time to come. It is therefore important to minimise use of these resources through optimising quantum computations and developing efficient quantum error-correcting codes. Different approaches to implementing quantum computations are being pursued in parallel. The most widely-used approach is that of quantum circuits, a generalisation of classical logic circuits. Another approach is the one-way model of measurement-based quantum computing, which exploits quantum entanglement and the property that quantum measurements change the state being measured. Measurement-based quantum computing has advantages on both the theoretical and experimental side: for example it links well with quantum error correction, which also makes use of successive quantum measurements. At the same time, measurement-based quantum computing brings new challenges: for example, quantum measurements are generally non-deterministic and care is therefore needed to construct a deterministic computation out of these non-deterministic operations. Flow properties mathematically certify that a measurement-based computation is deterministic in a suitable sense known as ‘robust determinism’. Translation between different models of quantum computing (such as quantum circuits or the one-way model) are necessary to ensure that computations can be implemented on any desired physical quantum computer. They have also shown themselves highly useful for optimisation as certain kinds simplifications are easier to perform in one model than another. Yet while translation from circuits to the measurement-based model is easy, translation in the other direction – known as ‘circuit extraction’ – is computationally hard in general [3]. At the same time, polynomial-time circuit extraction algorithms are know for measurement-based computations with flow [4, 1, 6]. A recent completeness result for flow-preserving rewriting proved that, starting from a computation with flow, it is possible to locally optimise or modify this computation while preserving both the overall effect and the existence of flow [2]. Simultaneously, the definition of a new property called ZX-flow [5] showed that it is possible to generalise the class of computations for which efficient circuit extraction is possible beyond those that are robustly deterministic. Mission confiée The goal of this thesis is to explore how the definition of robust determinism can be weakened while keeping circuit extraction efficient. A first step would be to find one (or more) ways of characterising how far a computation is from having flow. These characterisations will then be used to find ways of transforming computations that are ‘close’ to having flow into computations with flow. Next, the candidate will generalise the set of flow-preserving rewrite rules by looking for rules that do not increase the new notion of distance. The graphical formalism called ZX-calculus may be useful for these tasks. A second step is to apply these techniques to quantum error correcting codes and fault-tolerant quantum computation on encoded data. Both the one-way model and error-correcting codes distinguish physical qubits and logical qubits: in the former case, the logical qubits are given by the flow whereas in the latter case they represent the encoded data. The candidate will develop a unified description that can handle both measurement-based quantum computing and quantum error correction with their different approaches to measurement and corrections, as well as the physical-logical distinction. References [1] 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, p. 421, doi:10.22331/q-2021-03-25-421.  [2] Miriam Backens & Simon Perdrix (2026): Completeness for Flow-Preserving Rewrite Rules, arXiv:2608.13035. [3] N. de Beaudrap, Aleks Kissinger & John van de Wetering (2022): Circuit Extraction for ZX-Diagrams Can Be #P-Hard. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Dagstuhl, Germany, pp. 119:1–119:19, doi:10.4230/LIPIcs.ICALP.2022.119. [4] Ross Duncan, Aleks Kissinger, Simon Perdrix & John van de Wetering (2020): Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum 4, p. 279, doi:10.22331/q-2020-06-04-279. [5] Aleks Kissinger & John van de Wetering (2026): ZX-Flow: A Flexible Criterion for Deterministic Computation with ZX-Diagrams. arXiv:2603.09580. [6] Will Simmons (2021): Relating Measurement Patterns to Circuits via Pauli Flow. Electronic Proceedings in Theoreti