Raul Garcia-Patron

Abstract Recent technological developments have focused the interest of the quantum computing community on investigating how near-term devices could outperform classical computers for practical applications. A central question that remains open is whether their noise can be overcome or it fundamentally restricts any potential quantum advantage. We present a transparent way of comparing classical algorithms to quantum ones running on near-term quantum devices for a large family of problems that include optimization problems and approximations to the ground state energy of Hamiltonians. Our approach is based on the combination of entropic inequalities that determine how fast the quantum computation state converges to the fixed point of the noise model, together with established classical methods of Gibbs state sampling. The approach is extremely versatile and allows for its application to a large variety of problems, noise models and quantum computing architectures. We use our results to provide estimates for a variety of problems and architectures that have been the focus of recent experiments, such as quantum annealers, variational quantum eigensolvers, and quantum approximate optimization. The bounds we obtain indicate that substantial quantum advantages are unlikely for classical optimization unless the current noise rates are decreased by orders of magnitude or the topology of the problem matches that of the device. This is the case even if the number of qubits increases substantially. We reach similar but less stringent conclusions for quantum Hamiltonian problems.

Estimating quantum time-series such as the Loschmidt echo $f(t)=\langle\psi|\mathrm{e}^{-\mathrm{i}Ht}|\psi\rangle$ is central to spectroscopy and Hamiltonian analysis. Direct estimation via the Hadamard test requires controlled implementations of $\mathrm{e}^{-\mathrm{i}Ht}$, and the depth of these controlled circuits grows with $t$, making long-time estimation challenging on near-term hardware. Inspired by the classical Phaselift approach to phase retrieval, we introduce Quantum Phaselift, a lifting-based framework that estimates the rank-one matrix $Z = f f^\dagger$ sampled at discrete times instead of $f$ directly. We propose quantum circuits for estimating the entries of $Z$ and prove that measuring only a narrow band of this matrix around the diagonal provides sufficient data for unique signal reconstruction. This reformulation reduces the depth of required controlled circuits to scale with the width of the measured band, rather than with the total evolution time. We then show that generic signals can be recovered from a band of width $O(1)$, providing a substantial savings in controlled operations compared to naïve algorithms. We develop three robust estimators to recover the signal from the noisy measurements of the entries on this narrow band: a block-by-block algebraic estimator, a block-by-block eigenvector estimator, and a least-squares estimator. We rigorously prove exact recovery for all three estimators in the noiseless setting and establish stability guarantees and sample complexity bounds for the block-by-block algebraic estimator in the presence of measurement noise. Finally, we numerically demonstrate that high-quality signal recovery is possible for the 2D Fermi-Hubbard and 2D transverse-field Ising model time-series with more than 100 points using only a few million samples and reasonable post-processing time, making our recovery techniques efficient and effective for near-term implementations.