In this talk, I will present some of my past and current works on quantum algorithms. The first part of the talk will be on quantum algorithms for far-future quantum computers with large-scale and perfectly functioning components. The second part will be on employing machine-learning methods for analyzing the average-case complexity of algorithms and our vision for applying them to current and near-future noisy quantum computers.
Specifically, in the first part, I will talk about simulating quantum field theories on a quantum computer and an optimal approach for extracting information encoded in a quantum state. Along the way, I will describe how representing quantum fields in multiple scales using wavelets enables more efficient preparation of certain states of a quantum field and dealing with nonlinearities in a system. In the second part, I will discuss empirical hardness models, their various applications, and our vision to bring them to the quantum domain. These models allow us to characterize the difficulty of solving a given family of problems using the best available algorithms. These algorithms typically have exponentially varying performances and no attractive theoretical guarantees but work astonishingly well in practice.