Quasi-probability representations of quantum computing
File(s)
Author(s)
Koukoulekidis, Nikolaos
Type
Thesis
Abstract
If universal quantum computing is Tartarus, the mythical underworld where Titans are tormented, then magic is Charon, the ferryman tasked to get you there.
Shifting perspective often reveals simpler solutions to hard problems. In this the- sis, we shift our view of quantum computing from the Hilbert space picture to a geometric picture of a discrete phase space on which computational elements can be represented through quasi-probability distributions. In this new picture, we recog- nize new ways to refine the theory of quantum computing.
Magic states play a crucial role in upgrading fault-tolerant computational frame- works beyond classically efficient capabilities and simulation techniques. Theories of magic have so far attempted to quantify this computational element via coarse- grained monotones and determine how these states may be efficiently transformed into useful forms. Using a quasi-probability representation of quantum states on a discrete phase space, it is known that we can identify useful magic states by the presence of negative probabilities. This thesis utilizes this representation to develop a novel statistical mechanical framework that provides a more fine-grained descrip- tion of magic state transformations as well as to develop classical algorithms that simulate quantum circuits containing magic states more efficiently.
We show that majorization allows us to quantify disorder in the Wigner repre- sentation, leading to entropic bounds on magic distillation rates. The bounds are shown to be more restraining than previous bounds based on monotones and can be used to incorporate features of the distillation protocol, such as invariances of CSS protocols, as well as hardware physics, such as temperature dependence and sys- tem Hamiltonians. We also show that a subset of single-shot R ́enyi entropies remain well-defined on quasi-probability distributions, are fully meaningful in terms of data processing and can acquire negative values that signal magic.
Moreover, we propose classical sub-routines that reduce the sampling overhead for important classical samplers with run-times that depend on the negativity present in the Wigner representation. We show that the run-times of our sub-routines scale polynomially in circuit size and gate depth. We also demonstrate numerically that our methods provide improved scaling in the sampling overhead for random circuits with Clifford+T and Haar-random gates, while the performance of our methods compares favorably with prior simulators based on quasi-probability representations as the number of non-Clifford gates increases.
Shifting perspective often reveals simpler solutions to hard problems. In this the- sis, we shift our view of quantum computing from the Hilbert space picture to a geometric picture of a discrete phase space on which computational elements can be represented through quasi-probability distributions. In this new picture, we recog- nize new ways to refine the theory of quantum computing.
Magic states play a crucial role in upgrading fault-tolerant computational frame- works beyond classically efficient capabilities and simulation techniques. Theories of magic have so far attempted to quantify this computational element via coarse- grained monotones and determine how these states may be efficiently transformed into useful forms. Using a quasi-probability representation of quantum states on a discrete phase space, it is known that we can identify useful magic states by the presence of negative probabilities. This thesis utilizes this representation to develop a novel statistical mechanical framework that provides a more fine-grained descrip- tion of magic state transformations as well as to develop classical algorithms that simulate quantum circuits containing magic states more efficiently.
We show that majorization allows us to quantify disorder in the Wigner repre- sentation, leading to entropic bounds on magic distillation rates. The bounds are shown to be more restraining than previous bounds based on monotones and can be used to incorporate features of the distillation protocol, such as invariances of CSS protocols, as well as hardware physics, such as temperature dependence and sys- tem Hamiltonians. We also show that a subset of single-shot R ́enyi entropies remain well-defined on quasi-probability distributions, are fully meaningful in terms of data processing and can acquire negative values that signal magic.
Moreover, we propose classical sub-routines that reduce the sampling overhead for important classical samplers with run-times that depend on the negativity present in the Wigner representation. We show that the run-times of our sub-routines scale polynomially in circuit size and gate depth. We also demonstrate numerically that our methods provide improved scaling in the sampling overhead for random circuits with Clifford+T and Haar-random gates, while the performance of our methods compares favorably with prior simulators based on quasi-probability representations as the number of non-Clifford gates increases.
Version
Open Access
Date Issued
2023-01
Date Awarded
2023-09
Copyright Statement
Creative Commons Attribution NonCommercial Licence
License URL
Advisor
Jennings, David
Kim, Myungshik
Publisher Department
Physics
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)