PhD Position F/M Determinism and circuit extraction beyond flow

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.

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 Theoretical Computer Science 343, pp. 50–101, doi:10.4204/EPTCS.343.4.

The candidate will:

• Familiarise themself with the relevant literature
• Develop new formal descriptions of flow
• Prove properties related to these descriptions 

The candidate must have a background in at least one of the fields relevant to theoretical quantum computing: computer science, physics, or mathematics. Previous knowledge of quantum computing is advantageous but not required.

• Subsidized meals
• Partial reimbursement of public transport costs
• Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
• Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
• Professional equipment available (videoconferencing, loan of computer equipment, etc.)
• Social, cultural and sports events and activities
• Access to vocational training
• Social security coverage

€2300 gross/month