MEZHER Rawad
This thesis is focused on the generation and understanding of particular kinds of quantum randomness. Randomness is useful for many tasks in physics and information processing, from randomized benchmarking , to black hole physics , as well as demonstrating a socalled quantum speedup , and many other applications. On the one hand we explore how to generate a particular form of random evolution known as a tdesign. On the other we show how this can also give instances for quantum speedup  where classical computers cannot simulate the randomness efficiently. We also show that this is still possible in noisy realistic settings.
More specifically, this thesis is centered around three main topics. The first of these being the generation of epsilonapproximate unitary tdesigns. In this direction, we first show that nonadaptive, fixed measurements on a graph state composed of poly(n,t,log(1/epsilon)) qubits, and with a regular structure (that of a brickwork state) effectively give rise to a random unitary ensemble which is a epsilonapproximate tdesign. Before this work, it was known that nonadaptive fixed XY measurements on a graph state give rise to unitary tdesigns , however the graph states used there were of complicated structure and were therefore not natural candidates for measurement based quantum computing (MBQC), and the circuits to make them were complicated. The novelty in our work is showing that tdesigns can be generated by fixed, nonadaptive measurements on graph states whose underlying graphs are regular 2D lattices. These graph states are universal resources for MBQC. Therefore, our result allows the natural integration of unitary tdesigns, which provide a notion of quantum pseudorandomness which is very useful in quantum algorithms, into quantum algorithms running in MBQC. Moreover, in the circuit picture this construction for tdesigns may be viewed as a constant depth quantum circuit, albeit with a polynomial number of ancillas.
We then provide new constructions of epsilonapproximate unitary tdesigns both in the circuit model and in MBQC which are based on a relaxation of technical requirements in previous constructions.
The second topic of this thesis deals with sampling from the output probabilities of quantum devices which demonstrate a quantum speedup, in the sense that no classical polynomial time algorithm can sample from these probabilities given some complexity theoretic conjectures  which are widely held to be true  hold. In this direction, we present new examples of such sampling problems defined by nonadaptive fixed angle measurements on 2D graph states with a regular structure. Our sampling problems possess desirable properties for experimental implementation such as nearest neighbor interactions, fixed nonadaptive measurements.
The third topic of this thesis concerns observing quantum speedup in a realistic, noisy setting. We present a new example of a sampling problem defined by measurements on a poly(n) sized 2D graph state with ninput qubits. Again, we show that this sampling problem cannot be performed efficiently on a classical computer unless complexitytheoretic conjectures which are widely believed to be true, turn out to be false. Crucially, this sampling problem is robust against general noise models, by virtue of quantum error correction, and also posseses desirable properties for experimental implementation such as low overhead, nearest neighbor interactions, regular structure, and fixed angle, nonadaptive Pauli measurements. Furthermore, when viewed in the circuit model, this result can be understood as constant depth circuits giving rise to a fault tolerant quantum speedup.
More specifically, this thesis is centered around three main topics. The first of these being the generation of epsilonapproximate unitary tdesigns. In this direction, we first show that nonadaptive, fixed measurements on a graph state composed of poly(n,t,log(1/epsilon)) qubits, and with a regular structure (that of a brickwork state) effectively give rise to a random unitary ensemble which is a epsilonapproximate tdesign. Before this work, it was known that nonadaptive fixed XY measurements on a graph state give rise to unitary tdesigns , however the graph states used there were of complicated structure and were therefore not natural candidates for measurement based quantum computing (MBQC), and the circuits to make them were complicated. The novelty in our work is showing that tdesigns can be generated by fixed, nonadaptive measurements on graph states whose underlying graphs are regular 2D lattices. These graph states are universal resources for MBQC. Therefore, our result allows the natural integration of unitary tdesigns, which provide a notion of quantum pseudorandomness which is very useful in quantum algorithms, into quantum algorithms running in MBQC. Moreover, in the circuit picture this construction for tdesigns may be viewed as a constant depth quantum circuit, albeit with a polynomial number of ancillas.
We then provide new constructions of epsilonapproximate unitary tdesigns both in the circuit model and in MBQC which are based on a relaxation of technical requirements in previous constructions.
The second topic of this thesis deals with sampling from the output probabilities of quantum devices which demonstrate a quantum speedup, in the sense that no classical polynomial time algorithm can sample from these probabilities given some complexity theoretic conjectures  which are widely held to be true  hold. In this direction, we present new examples of such sampling problems defined by nonadaptive fixed angle measurements on 2D graph states with a regular structure. Our sampling problems possess desirable properties for experimental implementation such as nearest neighbor interactions, fixed nonadaptive measurements.
The third topic of this thesis concerns observing quantum speedup in a realistic, noisy setting. We present a new example of a sampling problem defined by measurements on a poly(n) sized 2D graph state with ninput qubits. Again, we show that this sampling problem cannot be performed efficiently on a classical computer unless complexitytheoretic conjectures which are widely believed to be true, turn out to be false. Crucially, this sampling problem is robust against general noise models, by virtue of quantum error correction, and also posseses desirable properties for experimental implementation such as low overhead, nearest neighbor interactions, regular structure, and fixed angle, nonadaptive Pauli measurements. Furthermore, when viewed in the circuit model, this result can be understood as constant depth circuits giving rise to a fault tolerant quantum speedup.
Defence : 11/15/2019  13h30  Campus Jussieu, salle Jacques Pitrat (2526/105)
Jury members :
M. Ashley MONTANARO, The University of Bristol [Rapporteur]
M. Peter TURNER, The University of Bristol [Rapporteur]
Mme. Elham KASHEFI , Sorbonne Université; The University of Edinburgh
Mme. Nancy RAHBANY, Université NotreDamedeLouaizé
M. Damian MARKHAM
M. Joseph DGHEIM
M. Joe GHALBOUNI
20182020 Publications

2020
 R. Mezher, J. Ghalbouni, J. Dgheim, D. Markham : “Faulttolerant quantum speedup from constant depth quantum circuits”, Physical Review Research, vol. 2 (3), pp. 033444, (American Physical Society) (2020)

2019
 R. Mezher : “Randomness for quantum information processing”, thesis, defence 11/15/2019, supervision Markham, joseph dgheim, Damian, rapporteurs : GHALBOUNI Joe (2019)
 R. Mezher, J. Ghalbouni, J. Dgheim, D. Markham : “Unitary $t$designs from $relaxed$ seeds”, (2019)
 R. Mezher, J. Ghalbouni, J. Dgheim, D. Markham : “Efficient approximate unitary tdesigns from partially invertible universal sets and their application to quantum speedup”, (2019)

2018
 R. Mezher, J. Ghalbouni, J. Dgheim, D. Markham : “Efficient quantum pseudorandomness with simple graph states”, Physical Review A, (American Physical Society) (2018)