Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2404.03644 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908028809248768 |
|---|---|
| author | Zlokapa, Alexander Somma, Rolando D. |
| author_facet | Zlokapa, Alexander Somma, Rolando D. |
| contents | We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. Assuming access to a block-encoding of $H'=(H-E)/λ$ for some $E \in \mathbb R$, the goal is to implement an $ε$-approximation to $e^{-itH}$ when the initial state is confined to the subspace corresponding to eigenvalues $[-1, -1+Δ/λ]$ of $H'$. We present a quantum algorithm that uses $O(t\sqrt{λΓ} + \sqrt{λ/Γ}\log(1/ε))$ queries to the block-encoding for any $Γ$ such that $Δ\leq Γ\leq λ$. When $\log(1/ε) = o(tλ)$ and $Δ/λ= o(1)$, this result improves over generic methods with query complexity $Ω(tλ)$. Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform. Using standard access models for $H$, we show that the ability to efficiently block-encode $H'$ is equivalent to $H$ being what we refer to as a "gap-amplifiable" Hamiltonian. This includes physically relevant examples such as frustration-free systems, and it encompasses all previously considered settings of low-energy simulation algorithms. We also provide lower bounds for low-energy simulation. In the worst case, we show that the low-energy condition cannot be used to improve the runtime of Hamiltonian simulation. For gap-amplifiable Hamiltonians, we prove that our algorithm is tight in the query model with respect to $t$, $Δ$, and $λ$. In the practically relevant regime where $\log (1/ε) = o(tΔ)$ and $Δ/λ= o(1)$, we also prove a matching lower bound in gate complexity (up to log factors). To establish the query lower bounds, we consider $\mathrm{PARITY}\circ\mathrm{OR}$ and degree bounds on trigonometric polynomials. To establish the lower bound on gate complexity, we use a circuit-to-Hamiltonian reduction acting on a low-energy state. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03644 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hamiltonian simulation for low-energy states with optimal time dependence Zlokapa, Alexander Somma, Rolando D. Quantum Physics We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. Assuming access to a block-encoding of $H'=(H-E)/λ$ for some $E \in \mathbb R$, the goal is to implement an $ε$-approximation to $e^{-itH}$ when the initial state is confined to the subspace corresponding to eigenvalues $[-1, -1+Δ/λ]$ of $H'$. We present a quantum algorithm that uses $O(t\sqrt{λΓ} + \sqrt{λ/Γ}\log(1/ε))$ queries to the block-encoding for any $Γ$ such that $Δ\leq Γ\leq λ$. When $\log(1/ε) = o(tλ)$ and $Δ/λ= o(1)$, this result improves over generic methods with query complexity $Ω(tλ)$. Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform. Using standard access models for $H$, we show that the ability to efficiently block-encode $H'$ is equivalent to $H$ being what we refer to as a "gap-amplifiable" Hamiltonian. This includes physically relevant examples such as frustration-free systems, and it encompasses all previously considered settings of low-energy simulation algorithms. We also provide lower bounds for low-energy simulation. In the worst case, we show that the low-energy condition cannot be used to improve the runtime of Hamiltonian simulation. For gap-amplifiable Hamiltonians, we prove that our algorithm is tight in the query model with respect to $t$, $Δ$, and $λ$. In the practically relevant regime where $\log (1/ε) = o(tΔ)$ and $Δ/λ= o(1)$, we also prove a matching lower bound in gate complexity (up to log factors). To establish the query lower bounds, we consider $\mathrm{PARITY}\circ\mathrm{OR}$ and degree bounds on trigonometric polynomials. To establish the lower bound on gate complexity, we use a circuit-to-Hamiltonian reduction acting on a low-energy state. |
| title | Hamiltonian simulation for low-energy states with optimal time dependence |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2404.03644 |