Improvements to quantum search, with applications to cryptanalysis

Abstract

The quadratic advantage in query-complexity that Grover's algorithm offers for the unstructured search problem is well-known by the cryptographic community and the security estimates for many cryptosystems are based upon quantum resource estimates for Grover's algorithm. In essence, Grover's algorithm consists of the repeated application of a quantum oracle, unique to the instance of the search problem, and some less costly circuitry. This quantum oracle is essentially a reversible boolean circuit, implemented via quantum gates. This thesis examines the optimisation of quantum search routines in the noise-free quantum circuit model of computation, with the goal of negating a portion of the cost associated with the necessity to implement quantum oracles in Grover's algorithm. The importance of such gains is illustrated by considering the approximate circuit-size of Grover's algorithm for the single-target search problem, $\frac{\pi}{4} \cdot 2^{\frac{n}{2}} \cdot \text{poly}(n)$ where $\text{poly}(n)$ is the cost of implementing the quantum oracle. If $n = 100$ and $\text{poly}(n) =n^3$, then the approximate quantum circuit-size is $2^{70}$ compared to the lower bound implied by query-complexity of $2^{50}$ and this overhead of $2^{20}$ has an associated real-world cost in terms of the number of quantum gates which must be implemented. Reduction of this overhead can therefore result in gains for any potential implementation. Optimisation of the reversible circuitry which implements the quantum oracle can achieve this and this thesis demonstrates that this can also be achieved by other methods for certain problems by using modifications of Grover's algorithm. As a motivating example throughout this thesis, we apply these techniques to lower quantum resource estimates for cryptanalysis of the {\it Multivariate Quadratic problem} over $\mathbb{F}_2$ and later in cryptanalysis of the {\it Advanced Encryption Standard} (AES).

Date of Award	20 Nov 2019
Original language	English
Awarding Institution	University of Bath
Supervisor	James Davenport (Supervisor), Anthony Power (Supervisor) & Christophe Petit (Supervisor)