Michele Mosca

Public-key cryptography has proved to be an indispensable tool in the modern information security infrastructure. We prove that an identification scheme based on bounded quantum reference frames is secure against a computationally-unbounded adversary (only restricted by finite cheating strategies), demonstrating for the first time that unconditionally-secure and reusable public-key authentication is possible in principle. To prove security of our protocol, we employ elements of the polynomial method, the theory of estimation of black-box group transformations, and the theory of bounded quantum reference frames. We also use the quantum Fourier transform in a new and rather surprising way.

I will review the main quantum algorithms using new insights obtained over the past few years. This will include the quantum Fourier transform, Shor's algorithms, the eigenvalue estimation approach of Kitaev, relations to other algorithms and connections between them. Quantum amplitude estimation (a generalisation of quantum counting) will also be discussed.

We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti et al (2008 Phys. Rev. Lett.100 160501). Due to a result of Regev and Schiff (ICALP '08 733), we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order $o({2}^{-n/2})$ (where $N={2}^{n}$ is the size of the memory) whenever the memory is used as an oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. By contrast, for algorithms such as matrix inversion Harrow et al (2009 Phys. Rev. Lett.103 150502) or quantum machine learning Rebentrost et al (2014 Phys. Rev. Lett.113 130503) that only require a polynomial number of queries, the error rate only needs to be polynomially small and quantum error correction may not be required. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of 'active' gates, since all components have to be actively error corrected.