- Abstract : The existence of practically useful quantum algorithms is uncertain yet, but the cost of running quantum computers is real. Do we really always need to rely on expensive quantum computers to compute the same functions? For certain quantum circuit–generated functions, the answer is no. Instead, one can actively learn (surrogate) these circuits and construct efficient classical representations of them. This approach differs from direct quantum circuit simulation and can even go beyond it.

In this talk, we specifically consider functions $f_Q(x) = \langle0|U(x)^{\dagger}OU(x)|0\rangle$, where classical inputs $x \in \mathbb{R}^n$ are encoded via $e^{-iG_k\phi_k(x_k)}$ for some generators $G_k$ and pre-processing functions $\phi_k$, and O represents arbitrary observable including POVM elements. By observing that all such functions $f_Q$s inherit a natural tensor-product structure, we adopt the well-developed tensor reconstruction algorithm—tensor cross interpolation (TCI)—to construct efficient MPS representations of $f_Q$, using a number of function evaluations that scales efficiently with the input dimension n. Finally, we discuss the assumptions, limitations, and implications of this approach for understanding quantum advantage.