Internships
Optimising MBQC Patterns
Description: Minimising space, depth or lifetime of MBQC patterns are combinatorial optimisation problems that are NP-hard in general. This internship focuses on discovering heuristics and subclasses that make these problems tractable in practice in the context of the Graphix project.
Supervisors: Maxime Garnier, Thierry Martinez
Formalising MBQC
Description: Formalising the MBQC theory is an ongoing work, and there are several results in the literature that would be worth formalising. These results involve combinatorial theory (pattern optimisation), graph theory (flow-finding and determinism), or cryptography (e.g., protocols for delegated computation). Depending on the intern’s preferences, the intership will consist in formalising one or several of these results in Rocq on top of the current MBQC formalisation.
Supervisors: Maxime Garnier, Thierry Martinez
