Quantum Simulation Algorithms with Applications to Quantum Error Correction and Topological Data Analysis

This thesis presents three results of relevance to the simulation of quantum dynamics on quantum computers. The first is the development of hybridized methods of quantum simulation with Alessandro Roggero and Nathan Wiebe. Conventional methods of quantum simulation, such as qDRIFT, Trotterization, and qubitization, involve trade-offs that limit their applicability to specific contexts where their use is optimal. We develop a framework that allows different simulation methods to be hybridized via the interaction picture and thereby improve performance for interaction picture simulations over known algorithms. These approaches show asymptotic improvements over the individual methods that comprise them and further make interaction picture simulation methods practical in the near term. Physical applications of these hybridized methods yield a gate complexity scaling as $\log^2 \Lambda$ in the electric cutoff $\Lambda$ for the Schwinger model and independent of the electron density for collective neutrino oscillations, outperforming the scaling for all current algorithms with these parameters. For the general problem of Hamiltonian simulation subject to dynamical constraints, these methods yield a query complexity independent of the penalty parameter $\lambda$ used to impose an energy cost on time-evolution into an unphysical subspace. Our second result concerns fault-tolerant error correction procedures developed with Alessandro Roggero and Nathan Wiebe for certain lattice gauge theories (LGTs) with a view towards simulating their dynamics on quantum computers. Quantum simulations of LGTs are often formulated on an enlarged Hilbert space containing both physical and unphysical sectors in order to retain a local Hamiltonian. We provide simple fault-tolerant procedures that exploit such redundancy by combining a phase flip error correction code with the intrinsic Gauss' law gauge symmetry to correct one-qubit errors for a $\mathbb{Z}_2$ or truncated U(1) LGT in 1+1 and 2+1 dimensions with a link flux cutoff of $1$. Unlike existing work on detecting violations of Gauss' law, our circuits are fault tolerant and the overall error correction scheme outperforms a na\"{i}ve application of the $[5,1,3]$ code. The constructions outlined can be extended to LGT systems with larger cutoffs and can be used in understanding how to hybridize error correction and quantum simulation for LGTs in higher space-time dimensions and with different symmetry groups. Lastly, we present a classical randomized algorithm developed with Nathan Wiebe for topological data analysis, the problem of determining the approximate Betti numbers of simplicial complexes constructed from data sets. This problem has attracted considerable interest in recent years due to claims of exponential advantage for this task on quantum computers over classical methods such as Gaussian elimination or the Lanczos algorithm that scale exponentially with the size of the input. Our algorithm demonstrates a partial dequantization of this problem via the classical simulation of the imaginary time-evolution of the combinatorial Laplacian with the path integral Monte Carlo method. We show this algorithm can extract approximate Betti numbers in polynomial time in some of the same regimes where quantum computers were claimed to provide exponential advantage over classical computers. This implies that having exponentially large dimension and Betti number are necessary but not sufficient conditions for super-polynomial advantage on quantum computers.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.