Supervision : Damian MARKHAM, Joseph DGHEIM

Co-supervision : GHALBOUNI Joe

Randomness for quantum information processing

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 so-called quantum speedup , and many other applications. On the one hand we explore how to generate a particular form of random evolution known as a t-design. 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 epsilon-approximate unitary t-designs. In this direction, we first show that non-adaptive, 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 epsilon-approximate t-design. Before this work, it was known that non-adaptive fixed XY measurements on a graph state give rise to unitary t-designs , 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 t-designs can be generated by fixed, non-adaptive 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 t-designs, 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 t-designs may be viewed as a constant depth quantum circuit, albeit with a polynomial number of ancillas.
We then provide new constructions of epsilon-approximate unitary t-designs 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 non-adaptive 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 non-adaptive 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 n-input qubits. Again, we show that this sampling problem cannot be performed efficiently on a classical computer unless complexity-theoretic 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, non-adaptive 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.

2018-2021 Publications

• 2021
  • N. Kumar, R. Mezher, E. Kashefi : “Efficient Construction of Quantum Physical Unclonable Functions with Unitary t-designs”, (2021)
  • R. Mezher, J. Mills, E. Kashefi : “Mitigating errors by quantum verification and post-selection”, (2021)
  • E. Derbyshire, R. Mezher, Th. Kapourniotis, E. Kashefi : “Randomized Benchmarking with Stabilizer Verification and Gate Synthesis”, (2021)
• 2020
  • R. Mezher, J. Ghalbouni, J. Dgheim, D. Markham : “Fault-tolerant 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, phd defence 11/15/2019, supervision Markham, Damian Dgheim, Joseph, co-supervision : 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 t-designs 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)