QSI PhD Defense: Reece Robertson

TITLE:  Quantum Anti-Fragility: Case Studies in Error-Assisted Quantum Algorithms

ABSTRACT:  

All quantum algorithms experience error, but this inevitability need not interfere with an algorithm’s operation. The early days of quantum computation introduced algorithms like Simon's algorithm and Shor's algorithm—fragile quantum routines with exponential speedups predicated on fault-tolerance. Many recent algorithms, including the Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolvers (VQE), overcome error through iterative solution refinement using noise-resilient hybrid quantum-classical routines. A third, largely unexplored, class of algorithms uses error for computational advantage, an approach that will be termed quantum anti-fragility.

This dissertation, after a motivating examination of quantum noise, introduces the foundation for the class of anti-fragile quantum algorithms through four case studies. Each case study is described below in order.

First, fragility is eliminated from Simon's gate-based algorithm through a novel adaptation of the algorithm for adiabatic computers. This demonstrates that modifying an algorithm for execution on a different quantum hardware paradigm changes the noise characteristics present in the algorithm, which can create an opportunity for error utilization.

Second, two new quantum algorithms, one for job shop problems and the other for scheduling problems, are introduced that use error as a free resource for modeling stochastic processes. The algorithm compilation step plays a significant role in the resultant noise processes, allowing for informed shaping of the error distribution to match a target distribution

Third, better-than-physical error suppression is demonstrated through the judicious co-compilation of a quantum algorithm and an error-correcting code. This original method of code-optimal algorithm compilation is useful for tuning the amount of error within an anti-fragile algorithm. Moreover, results suggest that this type of compilation may be necessary for general fault-tolerant quantum computation.

Lastly, a novel protocol based on Simon's algorithm that protects the integrity of a quantum network is introduced. The protocol allows a quantum server to verify the quantumness and fault-tolerant capacity of several client devices and construct a network including only verified fault-tolerant quantum machines. In this instance, errors in the client machine are exploited by the remote server to preserve the integrity of the network.