<link rel="stylesheet" href="styles.cf390c6bfbe7555f.css">

THE BOUNDARIES OF COMPUTATIONAL HARDNESS IN NOISY QUANTUM CIRCUITS

Loading...
Thumbnail Image

Publication or External Link

External Link to Data Files

Date

Advisor

Liu, Yi-Kai

Citation

Abstract

Many families of quantum circuits, when run on an ideal (or fault-tolerant) quantum computer, produce outputs that cannot be efficiently reproduced using classical computers, assuming standard complexity-theoretic or cryptographic conjectures. Examples include Shor's algorithm for factoring integers and the simulation of quantum systems. This is called ``quantum advantage."However, current/near-term quantum computers are inherently noisy and often lack key features needed for fault-tolerant quantum computation, such as the ability to reset qubits quickly or adapt based on measurement outcomes. Without these tools to correct errors, the outputs of noisy quantum circuits quickly become indistinguishable from uniform randomness under realistic noise models. This raises an important question: are there families of noisy quantum circuits that remain hard to classically simulate, at least for short time-scales, before noise drives them to complete randomness? %This question has significance beyond the near-term regime, because even when large fault-tolerant devices become available, simpler noisy circuits may be more space and time efficient for some use cases. This also gets at a question about nature: without irreversible resources (such as qubit reset and measurement), is there a fundamental limit on how long quantum mechanical processes can remain non-simulable by classical computers, when affected by a constant rate of noise?

In this thesis, we explore how practical constraints, such as limited connectivity between qubits and restricted gate sets, further limit the computational power of noisy quantum circuits. We clearly delineate regimes in which quantum advantage is or isn't possible in the presence of noise. An overarching idea behind our results is that the output states of noisy quantum circuits resemble thermal states (quantum systems in equilibrium with an environment at a finite temperature). This mapping allows computational hardness results for quantum circuits to be imported to the thermal state setting, and classical simulation techniques to be imported from the thermal state setting to quantum circuits. Thus, we present results on both fronts, establishing quantum advantage in some settings while establishing no-go theorems in others.

Notes

Rights

Endorsement

Review

Supplemented By

Referenced By