A Caltech Library Service

Random Quantum Circuits and Their Simulation Complexity: an Analysis with Statistical Mechanics


Dalzell, Alexander Moos (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.


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:The Lucy Guernsey Service Award, 2021. 2021 Conference on Quantum Information Processing (QIP) Best Student Paper Prize - for article upon which Chapter 3 is based.
Thesis Availability:Public (worldwide access)
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
Funding AgencyGrant Number
NSF Graduate Research Fellowship ProgramDGE-1745301
Dominic Orr FellowshipUNSPECIFIED
Record Number:CaltechTHESIS:10292021-071119947
Persistent URL:
Related URLs:
URLURL TypeDescription​Journal article with content from Chapter 3.​Journal article with content from Chapter 4. article with content from Chapter 5.
Dalzell, Alexander Moos0000-0002-3756-8500
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14411
Deposited By: Alexander Dalzell
Deposited On:12 Mar 2022 00:11
Last Modified:29 Mar 2024 17:31

Thesis Files

[img] PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page