Quantum annealing and digital quantum ground state preparation algorithms

The recent advances in the world of quantum technologies have prompted the development of various quantum-based algorithms, some of which are suitable to run on available quantum devices. Two leading candidates in this area are Quantum Annealing (QA) and hybrid quantum-classical variational algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA). In the first part of the Thesis, we re-examine the issue of whether Simulated Quantum Annealing (SQA) with Path Integral Monte Carlo has anything to do with the coherent QA Schrödinger dynamics. We do that by studying the random quantum Ising Chain in a transverse field. In the second part of the Thesis we address the issue of schedule optimization in both {em digitized}-QA and QAOA. Traditional schedule optimization in QA requires spectral information on the problem (e.g., location of the minimum gaps), which is in most cases inaccessible. On the other hand, in QAOA, the issue of schedule optimization --- alias, the optimization of the variational parameters --- is often an expensive task that constitutes a bottleneck for the algorithm. We show that, by combining the framework of QAOA and digitized-QA, optimal digitized-QA protocols can be constructed efficiently. When using this approach, the computational cost of schedule optimization is also significantly reduced, leading to a computational advantage both over a linear-schedule QA, and over an unstructured QAOA search. While studying these issues, we also developed rigorous variational bounds that provide insight on the best possible performance that one can hope to obtain from a digital QAOA circuit.