Optimal precision dependence of low-energy Hamiltonian simulation

Unsolved ID op_25d9dee5435ea835 Last edited 25 September 2026

Edit

Field: Quantum Algorithm
Topics: Hamiltonian simulation
Computational complexity and computability

Problem

What is the tight precision dependence of worst-case query complexity for low-energy simulation in the regime (2)? Let \(A\in\mathbb{C}^{N\times N}\), \(\lVert A\rVert\leq1\), \(H=\lambda A^\dagger A\), and \(P_\Delta=\mathbf{1}_{[0,\Delta]}(H)\), where \(\lambda>0\) and \(0<\Delta\leq\lambda\). Assume an exact block encoding \((\langle0^m\rvert\otimes I_N)V_A(\lvert0^m\rangle\otimes I_N)=A\), with controlled and inverse calls. Count these queries; input-state preparation is excluded. For known \(t>0\) and \(0<\epsilon<1/2\), a unitary simulator \(W\) must satisfy (1) uniformly on the promised subspace:

\begin{equation} \sup_{\substack{\lVert\psi\rVert=1\\P_\Delta\lvert\psi\rangle=\lvert\psi\rangle}} \left\lVert W(\lvert0^a\rangle\lvert\psi\rangle) -\lvert0^a\rangle e^{-itH}\lvert\psi\rangle\right\rVert\leq\epsilon. \tag{1} \end{equation}

Here \(a\) counts workspace qubits. Consider asymptotic families with \(\epsilon\to0\) satisfying

\begin{equation} \epsilon=o(t\Delta),\qquad t\Delta=o\bigl(\log(1/\epsilon)\bigr),\qquad \log(1/\epsilon)=o(t\lambda). \tag{2} \end{equation}

Determine whether the known \(O(\sqrt{t\lambda\log(1/\epsilon)})\) upper bound has optimal precision dependence.

Source

Zlokapa and Somma explicitly leave the intermediate-regime precision gap open in Sections 1 and 7 [ZS24]. The error convention and nontrivial-regime restriction are made explicit here.

Progress

Reports do not certify correctness or automatically change the problem's status. Progress policy.

Lemma 1.2 and Section 2.2 give \(O(t\sqrt{\lambda\Gamma}+\sqrt{\lambda/\Gamma}\log(1/\epsilon))\) queries for \(\Delta\leq\Gamma\leq\lambda\). Choosing \(\Gamma=\log(1/\epsilon)/t\) gives the stated upper bound; polynomial tolerance \(O(\epsilon^2)\) suffices for (1) [ZS24].
Section 5.5 proves \(\Omega(\sqrt{t\lambda})\) on explicit nontrivial intermediate-regime families, without matching the precision factor [ZS24].
Reported progress: Issue #96.

Comment

This formulation fixes vector-norm error and excludes the identity-accurate regime \(t\Delta\leq\epsilon\). Factor access is essential. The cited lower bound is not asserted uniformly throughout (2).

References

[ZS24]: A. Zlokapa and R. D. Somma, “Hamiltonian simulation for low-energy states with optimal time dependence,” Quantum 8, 1449 (2024).DOI arXiv

Optimal precision dependence of low-energy Hamiltonian simulation

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems