Algorithms and Architectures for Practical Quantum Simulators

In the 1980s, Feynman, Manin, and others envisioned a computer harnessing quantum phenomena to perform computations — a quantum computer. Originally proposed to simulate physics, quantum computers can evade the curse of dimensionality that plagues classical simulations of quantum systems. Quantum simulations could efficiently elucidate fundamental natural processes that otherwise would be prohibitively costly to probe experimentally or intractable to simulate classically. Now, over four decades later, we are closer than ever to realizing quantum computers: experimentalists have advanced a variety of modalities for quantum computation, while theorists have steadily improved algorithms in asymptotic and constant terms.
But, despite substantial progress at the top and bottom of the quantum computing stack, the computational model and architecture of practical quantum simulators remain nascent and ambiguous. 

In this thesis, we pursue improvements in both algorithms and architectures: first, we propose a qubit-efficient algorithm for quantum linear algebra enabling efficient simulation of the Double Factorized Tensor HyperContracted (DFTHC) electronic Hamiltonian. This algorithm has significantly simpler circuits than the typical arithmetic subroutines required by qubitization, paving the way for RISC-like instances for quantum simulation. Second, we study quantum Boolean logic, which is critical for implementing qubitization and other quantum algorithms. We contribute techniques to compile fast Boolean logic in error-corrected quantum architectures and characterize the notion of reaction depth in quantum programs. Finally, we introduce a new in situ scheme for learning pulses controlling analog quantum simulators. Analogous to post-silicon validation, this scheme could enable improved accuracy guarantees when simulating systems on analog quantum computers.