Nonlocal games, distributed storage, and quantum error correction : excursions in fault-tolerant computation
Abstract/Contents
- Abstract
- In this thesis, we consider three computing systems afflicted by noise, which causes their behavior to deviate unpredictably from idealized theoretical models. In each system, we model the effects of noise, and characterize the extent to which fault-tolerance techniques allow the computation to proceed efficiently despite the presence of the noise. First, we consider two parties who wish to implement a computation with little communication by making use of nonlocal correlations, a task called nonlocal computation. Second, we investigate a data center computing scenario where data are stored across many nodes in an error-correcting code, and we wish to evaluate functions of this data despite unpredictable node failures. Third, we consider building a fault-tolerant quantum computer using near-term hardware, in which qubits are afflicted by a high rate of noise, and two-qubit gates are constrained to act on pairs of nearby qubits in a planar layout. A common theme in these three settings is that, in each case, the data are encoded in some code. In the nonlocal computation setup, this encoding takes the form of linear shares or distributed bits, and arises as a result of the distributed nature of the computation. In the data center computing setting, the encoding is a Reed-Solomon or other linear error-correcting code, whose purpose is to protect against catastrophic data loss due to worst-case node failures. In the fault-tolerant quantum computer, the data are encoded in quantum error-correcting codes, which protect the encoded quantum information from the unpredictable noise of the underlying hardware. We measure our fault-tolerance techniques by various notions of efficiency. In the first two systems, we aim to minimize the communication cost. In the third system, we aim to minimize the space and time overhead cost. We show both positive and negative results that better characterize the trade-off between noise level and efficiency in these three systems.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Shutty, Noah John |
|---|---|
| Degree supervisor | Hayden, Patrick (Patrick M.) |
| Degree supervisor | Wootters, Mary |
| Thesis advisor | Hayden, Patrick (Patrick M.) |
| Thesis advisor | Wootters, Mary |
| Thesis advisor | Rubinstein, Aviad |
| Thesis advisor | Tan, Li-Yang |
| Degree committee member | Rubinstein, Aviad |
| Degree committee member | Tan, Li-Yang |
| Associated with | Stanford University, Department of Physics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Noah John Shutty. |
|---|---|
| Note | Submitted to the Department of Physics. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/qc195dh8879 |
Access conditions
- Copyright
- © 2022 by Noah John Shutty
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...