Physics & Astronomy ETDs

Publication Date

Spring 5-1-2023

Abstract

Quantum computers offer new avenues to approach difficult problems by taking advantage of the strange and often nonintuitive phenomena present in quantum physics. Though many quantum algorithms are believed or known to outperform the best known classical algorithms, the fundamental mechanism granting them their power remains elusive. In measurement-based quantum computation (MBQC), two key resources have been show to enable universal and provably nonclassical quantum computations, respectively. These are symmetry-protected topological order (SPTO), a notion describing a class of quantum magnets with hidden long-range correlations in their entanglement structure, and quantum contextuality, the fact that a quantum measurement outcome inherently depends on the commuting observables simultaneously measured alongside it. In this dissertation, we deepen the connection between these concepts and MBQC, showing how properties of MBQC resource states can be used to make new statements about computational universality of generic resources with SPTO as well as near-term demonstrations of computational advantages that leverage contextuality. We also shed new light on an inherent connection between these two resources by demonstrating how contextuality can manifest itself in systems with SPTO.

We first elaborate on the SPTO-MBQC correspondence. In particular, we first show how certain many-body systems called graph states can possess a variety of exotic “subsystem symmetries” when placed on lattices with different geometries,. Traditionally, many-body systems with SPTO have been studied in terms of a global symmetry that acts uniformly on every site in the lattice; however, recent work has highlighted the importance of subsystem symmetries for their quantum computational utility, which act on special subsets of the lattice. We show that the subsystem symmetry inherent in these graph states extends to large families of many-body systems that posses a common subsystem SPTO, ensuring that any such system is a resource for universal MBQC. This demonstrates that resources for MBQC extend far beyond what was previously known.

Next, we relate the detection of a SPTO in one dimension to an unconditional demonstration of the superior power that quantum computers have over their classical counterparts by leveraging their inherent quantum contextuality. Namely, we invent a Bell-type test to measure a macroscopic order parameter (called a string order parameter) that characterizes the presence of SPTO in a many-body system, which produces highly correlated measurement outcomes. Reproducing these correlations classically requires a circuit whose depth grows with the system size, whereas the quantum many-body states utilized can be prepared with constant-depth circuits. This work broadens the class of quantum states that are useful for demonstration of quantum computational advantage to a wide class of states in a symmetry-protected topological phase, which have been of interest in near-term experiments for simulating exotic phases of quantum matter.

Finally, we elaborate on the MBQC-contextuality correspondence. It is well understood that contextuality can be used as a resource for computing nonlinear Boolean functions via MBQC assisted by a subuniversal classical computer that can only add bits modulo 2. Meanwhile, in the nonadaptive setting, which is the case for most traditional Bell tests, the size of the quantum resource needed can be exponential in the computational input. We leverage adaptivity to overcome this exponential overhead and formulate efficient MBQCs for Boolean functions with the best known scaling in the required spacetime resources (i.e., qubit count, quantum circuit depth, classical memory size, and number of calls to the side-processor). While our algorithms are nonclassical in the sense of contextuality, we also show how they can be used to make more powerful statements that separate the power of classical and quantum computers. Namely, our results constitute an alternative proof of an earlier theorem regarding an oracular separation between the power of constant-depth quantum circuits and constant-depth classical circuits with unbounded fan-in NAND and mod-$p$ gates for any prime $p$.

Degree Name

Physics

Level of Degree

Doctoral

Department Name

Physics & Astronomy

First Committee Member (Chair)

Akimasa Miyake

Second Committee Member

Ivan Deutsch

Third Committee Member

Andrew Landahl

Fourth Committee Member

Milad Marvian

Language

English

Keywords

Quantum computing, SPTO, MBQC, contextuality

Document Type

Dissertation

Download

Share

COinS