CaltechTHESIS
  A Caltech Library Service

Random Quantum Circuits and Their Simulation Complexity: An Analysis With Statistical Mechanics

Citation

Dalzell, Alexander M. (2022) Random Quantum Circuits and Their Simulation Complexity: An Analysis With Statistical Mechanics. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/3ntn-n574. https://resolver.caltech.edu/CaltechTHESIS:10292021-071119947

Abstract

Random circuit simulation, the task of replicating the output of a randomly chosen noiseless quantum computation, has been proposed as a path toward achieving quantum advantage: it is believed to be easy for quantum devices, but hard for classical ones. This thesis scrutinizes both sides of this belief. On the one hand, we investigate whether the task is classically hard—we find that, in certain non-trivial cases, it can actually be easy, complicating a potential general proof of hardness. On the other hand, we investigate whether the task can be easily accomplished on realistic quantum devices, which are subject to substantial noise rates—we find that, indeed, a version of the circuit simulation task can be salvaged even on a noisy quantum device performing the computation with low fidelity, as long as the noise meets certain conditions. Thus, this thesis emphasizes that, to construct a strong argument of quantum advantage via random circuit simulation on noisy quantum hardware, the core theoretical challenge remains proving lower bounds on the classical complexity of the task; doing so will require new ideas to circumvent the barriers presented by our work.

A key analytical technique we utilize for each of our results is the statistical mechanics method for random quantum circuits, which maps random quantum circuits made from local Haar-random gates to partition functions of classical statistical mechanical systems. This thesis demonstrates the utility of this method by applying it in several new ways. In some cases, we use it for heuristic reasoning about the behavior of random quantum circuits. In others, we go further and perform rigorous calculations of the resulting partition function, leading to precise technical conclusions about random quantum circuits, such as sharp bounds on the number of random gates needed to achieve the anti-concentration property.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:quantum computation; quantum information; random quantum circuits; computational complexity; statistical mechanics
Degree Grantor:California Institute of Technology
Division:Physics, Mathematics and Astronomy
Major Option:Physics
Awards:2021 Conference on Quantum Information Processing (QIP) Best Student Paper Prize - for article upon which Chapter 3 is based
Thesis Availability:Restricted to Caltech community only
Research Advisor(s):
  • Brandao, Fernando (advisor)
  • Preskill, John P. (co-advisor)
Thesis Committee:
  • Painter, Oskar J. (chair)
  • Vidick, Thomas Georges
  • Brandao, Fernando
  • Preskill, John P.
Defense Date:31 August 2021
Funders:
Funding AgencyGrant Number
NSF Graduate Research Fellowship ProgramDGE-1745301
Dominic Orr FellowshipUNSPECIFIED
Record Number:CaltechTHESIS:10292021-071119947
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:10292021-071119947
DOI:10.7907/3ntn-n574
Related URLs:
URLURL TypeDescription
https://doi.org/10.1103/PhysRevX.12.021021DOI​Journal article with content from Chapter 3.
https://doi.org/10.1103/PRXQuantum.3.010333DOI​Journal article with content from Chapter 4.
https://arxiv.org/abs/2111.14907arXivPre-print of article containing content from Chapter 5.
ORCID:
AuthorORCID
Dalzell, Alexander M.0000-0002-3756-8500
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14411
Collection:CaltechTHESIS
Deposited By: Alexander Dalzell
Deposited On:12 Mar 2022 00:11
Last Modified:09 Jun 2022 19:21

Thesis Files

[img] PDF - Final Version
Restricted to Caltech community only until 11 September 2022.
See Usage Policy.

3MB

Repository Staff Only: item control page