Accelerating linear algebra and machine learning with quantum computers

Thesis

In this thesis, I develop the theory required to use quantum computers to accelerate linear algebra and machine learning, in a manner akin to how GPUs are used today. I begin by analysing quantum random access memory (QRAM), the mechanism by which quantum algorithms can access classical (non-quantum) data. When used for linear algebra applications, I show that QRAM has substantial challenges making it harder to construct than an error-corrected quantum computer. Should QRAM prove to be unrealistic, I ask what types of classical data can be efficiently loaded into quantum computers, and prove that discretized continuous functions are one such option. Next, I introduce a framework for manipulating vectors with quantum computers. The primary result of this framework is a technique allowing for the non-linear transformations of vectors to be enacted efficiently for a broad class of functions, despite the underlying unitary (and thus linear) nature of quantum algorithms. In the final chapter, utilizing the preceding results and further developing the vector encoding framework, I demonstrate that quantum computers can accelerate inference for multilayer neural networks under a range of scenarios of QRAM feasibility. This chapter also notes a plausible path towards constructing a practically useful QRAM.

Authors: Rattew, AG

• DOI: 10.5287/ora-ozgvoo5rb
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: quantum machine learning; quantum non-linear amplitude transformation; accelerating multi-layer neural networks with quantum computers; quantum state preparation; quantum random access memory; quantum algorithms
• Subjects: Algorithms; Quantum computing