UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Exploring Quantum Computation Through the Lens of Classical Simulation

Calpin, Padraic; (2020) Exploring Quantum Computation Through the Lens of Classical Simulation. Doctoral thesis (Ph.D), UCL (University College London). Green open access

[thumbnail of Thesis_Corrected_PCalpin.pdf]
Thesis_Corrected_PCalpin.pdf - Accepted Version

Download (2MB) | Preview


It is widely believed that quantum computation has the potential to offer an ex- ponential speedup over classical devices. However, there is currently no definitive proof of this separation in computational power. Such a separation would in turn imply that quantum circuits cannot be efficiently simulated classically. However, it is well known that certain classes of quantum computations nonetheless admit an efficient classical description. Recent work has also argued that efficient classical simulation of quantum circuits would imply the collapse of the Polynomial Hierarchy, something which is commonly invoked in clas- sical complexity theory as a no-go theorem. This suggests a route for studying this ‘quantum advantage’ through classical simulations. This project looks at the problem of classically simulating quantum circuits through decompositions into stabilizer circuits. These are a restricted class of quantum computation which can be efficiently simulated classically. In this picture, the rank of the decomposition determines the temporal and spatial complexity of the simulation. We approach the problem by considering classical simulations of stabilizer circuits, introducing two new representations with novel features compared to previous meth- ods. We then examine techniques for building these so-called ‘stabilizer rank’ decom- positions, both exact and approximate. Finally, we combine these two ingredients to introduce an improved method for classically simulating broad classes of circuits using the stabilizer rank method.

Type: Thesis (Doctoral)
Qualification: Ph.D
Title: Exploring Quantum Computation Through the Lens of Classical Simulation
Event: UCL
Open access status: An open access version is available from UCL Discovery
Language: English
Additional information: Copyright © The Author 2020. Original content in this thesis is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) Licence (https://creativecommons.org/licenses/by-nc/4.0/). Any third-party copyright material present remains the property of its respective owner(s) and is licensed under its existing terms. Access may initially be restricted at the author’s request.
Keywords: quantum, computing, classical, simulation
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
URI: https://discovery.ucl.ac.uk/id/eprint/10091573
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item