This thesis covers three different and largely unrelated projects from my time as a Ph.D. student studying quantum information and computation.
In the first chapter, we construct a Hamiltonian whose dynamics simulate the dynamics of every other Hamiltonian up to exponentially long times in the system size. The Hamiltonian is time independent, local, one dimensional, and translation invariant. As a consequence, we show (under plausible computational complexity assumptions) that the circuit complexity of the unitary dynamics under this Hamiltonian grows steadily with time up to an exponential value in system size. This result makes progress on a recent conjecture by Susskind, in the context of the AdS/CFT correspondence, that the time evolution of the thermofield double state of two conformal field theories with a holographic dual has circuit complexity increasing linearly in time, up to exponential time.
In the second chapter, we study approximate quantum low-density parity-check (QLDPC) codes, which are approximate quantum error-correcting codes specified as the ground space of a frustration-free local Hamiltonian, whose terms do not necessarily commute. Such codes generalize stabilizer QLDPC codes, which are exact quantum error-correcting codes with sparse, low-weight stabilizer generators (i.e. each stabilizer generator acts on a few qubits, and each qubit participates in a few stabilizer generators). Our investigation is motivated by an important question in Hamiltonian complexity and quantum coding theory: do stabilizer QLDPC codes with constant rate, linear distance, and constant-weight stabilizers exist?
We show that obtaining such optimal scaling of parameters (modulo polylogarithmic corrections) is possible if we go beyond stabilizer codes: we prove the existence of a family of [[N, k, d, ε]] approximate QLDPC codes that encode k = Ω̃(N) logical qubits into N physical qubits with distance d = Ω̃(N) and approximation infidelity ε = ℴ(1/polylog(N)). The code space is stabilized by a set of 10-local noncommuting projectors, with each physical qubit only participating in ℴ(polylogN) projectors. We prove the existence of an efficient encoding map and show that the spectral gap of the code Hamiltonian scales as Ω̃(N-3.09). We also show that arbitrary Pauli errors can be locally detected by circuits of polylogarithmic depth.
Our family of approximate QLDPC codes is based on applying a recent connection between circuit Hamiltonians and approximate quantum codes (Nirkhe, et al., ICALP 2018) to a result showing that random Clifford circuits of polylogarithmic depth yield asymptotically good quantum codes (Brown and Fawzi, ISIT 2013). Then, in order to obtain a code with sparse checks and strong detection of local errors, we use a spacetime circuit Hamiltonian construction in order to take advantage of the parallelism of the Brown-Fawzi circuits.
The analysis of the spectral gap of the code Hamiltonian is the main technical contribution of this work. We show that for any depth D quantum circuit on n qubits there is an associated spacetime circuit-to-Hamiltonian construction with spectral gap Ω(n-3.09D-2log-6(n)). To lower bound this gap we use a Markov chain decomposition method to divide the state space of partially completed circuit configurations into overlapping subsets corresponding to uniform circuit segments of depth log n, which are based on bitonic sorting circuits. We use the combinatorial properties of these circuit configurations to show rapid mixing between the subsets, and within the subsets we develop a novel isomorphism between the local update Markov chain on bitonic circuit configurations and the edge-flip Markov chain on equal-area dyadic tilings, whose mixing time was recently shown to be polynomial (Cannon, Levin, and Stauffer, RANDOM 2017). Previous lower bounds on the spectral gap of spacetime circuit Hamiltonians have all been based on a connection to exactly solvable quantum spin chains and applied only to 1+1 dimensional nearest-neighbor quantum circuits with at least linear depth.
In the third and final chapter, we study the problem of maximum-likelihood (ML) decoding of stabilizer codes under circuit level noise. As progress in the design of proposed fault-tolerant quantum computing architectures moves forward, it is becoming essential to achieve the highest noise suppression possible from the underlying quantum error correcting code. The decoder, which ultimately decides which correction to apply to an encoded state that has suffered an error, is an essential part of this design. So-called maximum likelihood decoders achieve optimal error suppression, but using such a decoder becomes intractable as the size of code grows, therefore sub-optimal decoders which achieve good performance and favorable implementation complexity are used instead. Circuit level noise presents a particular challenge for achieving good performance and practical complexity. We present the construction of a subsystem code called the Circuit History Code which provides an algebraic structure for understanding and classifying circuit level errors. We use this structure to formulate maximum likelihood decoding under circuit level noise as a tensor network contraction. This in turn allows the implementation of approximate maximum likelihood decoders which we expect could provide near optimal decoding performance with considerably lower complexity. Using tensor network ML decoders can be useful for benchmarking the performance of efficient decoders being designed for implementation in real experiments, as well as providing options for implementing decoders for codes that would be difficult to decode with conventional methods.
}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Brandao, Fernando}, } @phdthesis{10.7907/3ntn-n574, author = {Dalzell, Alexander Moos}, title = {Random Quantum Circuits and Their Simulation Complexity: an Analysis with Statistical Mechanics}, school = {California Institute of Technology}, year = {2022}, doi = {10.7907/3ntn-n574}, url = {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.
}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Brandao, Fernando}, }