Accuracy Guarantees and Quantum Advantage for Analog Quantum Simulators