Quantum computation will likely provide significant advantages relative to classical architectures for certain computational problems in number theory and physics, and potentially in other areas such as optimization and machine learning. While some key theoretical and engineering problems remain to be solved, experimental advances in recent years have demonstrated the first beyond-classical quantum computation as well as the first experiments in error-corrected quantum computation. In this thesis, we focus on quantum computers with around one hundred qubits that can implement around one thousand operations, the so-called noisy-intermediate scale quantum (NISQ) regime or kilo-scale quantum (KSQ) regime, and develop algorithms tailored to these devices as well as techniques for error mitigation that require significantly less overhead than fault-tolerant quantum computation. In the first part, we develop quantum algorithms for diagonalizing quantum states (density matrices) and compiling quantum circuits. These algorithms use a quantum computer to evaluate a cost function which is classically hard to compute and a classical computer to adjust parameters of an ansatz circuit, similar to the variational principle in quantum mechanics and other variational quantum algorithms for chemistry and optimization. In the second part, we extend an error mitigation technique known as zero-noise extrapolation and introduce a new framework for error mitigation which we call logical shadow tomography. In particular, we adapt zero-noise extrapolation (ZNE) to the gate model and introduce new methods for noise scaling and (adaptive) extrapolation. Further, we analyze ZNE in the presence of time-correlated noise and experimentally show ZNE increases the effective quantum volume of various quantum computers. Finally, we develop a simple framework for error mitigation that enables (the composition of) several error mitigation techniques with significantly fewer resources than prior methods, and numerically show the advantages of our framework.
Read
