Hamiltonian simulation for low-energy states with optimal time dependence
Alexander Zlokapa, Rolando D. Somma
Abstract
We consider the task of simulating time evolution under a Hamiltonian <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>H</mml:mi></mml:math> within its low-energy subspace. Assuming access to a block-encoding of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>H</mml:mi><mml:mo>&#x2032;</mml:mo></mml:msup><mml:mo>:=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>H</mml:mi><mml:mo>&#x2212;</mml:mo><mml:mi>E</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&#x03BB;</mml:mi></mml:math>, for some <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03BB;</mml:mi><mml:mo>&#x003E;</mml:mo><mml:mn>0</mml:mn></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>E</mml:mi><mml:mo>&#x2208;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">R</mml:mi></mml:mrow></mml:math>, the goal is to implement an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03F5;</mml:mi></mml:math>-approximation to the evolution operator <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>e</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&#x2212;</mml:mo><mml:mi>i</mml:mi><mml:mi>t</mml:mi><mml:mi>H</mml:mi></mml:mrow></mml:msup></mml:math> when the initial state is confined to the subspace corresponding to eigenvalues <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo stretchy="false">[</mml:mo><mml:mo>&#x2212;</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>&#x2212;</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi mathvariant="normal">&#x0394;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&#x03BB;</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:math> of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>H</mml:mi><mml:mo>&#x2032;</mml:mo></mml:msup></mml:math>, for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x0394;</mml:mi><mml:mo>&#x2264;</mml:mo><mml:mi>&#x03BB;</mml:mi></mml:math>. We present a quantum algorithm that requires <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>t</mml:mi><mml:msqrt><mml:mi>&#x03BB;</mml:mi><mml:mi mathvariant="normal">&#x0393;</mml:mi></mml:msqrt><mml:mo>+</mml:mo><mml:msqrt><mml:mi>&#x03BB;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi mathvariant="normal">&#x0393;</mml:mi></mml:msqrt><mml:mi>log</mml:mi><mml:mo>&#x2061;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math> queries to the block-encoding for any choice of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x0393;</mml:mi></mml:math> such that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x0394;</mml:mi><mml:mo>&#x2264;</mml:mo><mml:mi mathvariant="normal">&#x0393;</mml:mi><mml:mo>&#x2264;</mml:mo><mml:mi>&#x03BB;</mml:mi></mml:math>. When the parameters satisfy <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>log</mml:mi><mml:mo>&#x2061;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>t</mml:mi><mml:mi>&#x03BB;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x0394;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&#x03BB;</mml:mi><mml:mo>=</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:math>, this result improves over generic methods with query complexity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x03A9;</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>t</mml:mi><mml:mi>&#x03BB;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>. Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform.For a given <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>H</mml:mi></mml:math>, the block-encoding of its <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>H</mml:mi><mml:mo>&#x2032;</mml:mo></mml:msup></mml:math> must be prepared efficiently to achieve an asymptotic speedup in simulating the low-energy subspace; we refer to these Hamiltonians as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>g</mml:mi><mml:mi>a</mml:mi><mml:mi>p</mml:mi><mml:mo>&#x2212;</mml:mo><mml:mi>a</mml:mi><mml:mi>m</mml:mi><mml:mi>p</mml:mi><mml:mi>l</mml:mi><mml:mi>i</mml:mi><mml:mi>f</mml:mi><mml:mi>i</mml:mi><mml:mi>a</mml:mi><mml:mi>b</mml:mi><mml:mi>l</mml:mi><mml:mi>e</mml:mi></mml:math>. We show necessary and sufficient conditions for gap amplifiability in terms of an operationally useful decomposition of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>H</mml:mi></mml:math> into a sum of squares. Gap-amplifiable Hamiltonians include physically relevant examples such as frustration-free systems, and it encompasses all previously considered settings of low energy simulation algorithms. Any Hamiltonian can be expressed as a gap-amplifiable Hamiltonian after simple transformations, and our algorithm retains the asymptotic improvement over generic methods as long as the conditions on the parameters are met.We also provide lower bounds for simulating dynamics of low-energy states. In the worst case, we show that the low-energy condition cannot be used to improve the runtime of Hamiltonian simulation methods. For gap-amplifiable Hamiltonians, we prove that our algorithm is tight in the query model with respect to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>t</mml:mi></mml:math>, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x0394;</mml:mi></mml:math>, and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03BB;</mml:mi></mml:math>. In the practically relevant regime where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>log</mml:mi><mml:mo>&#x2061;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>t</mml:mi><mml:mi mathvariant="normal">&#x0394;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="normal">&#x0394;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&#x03BB;</mml:mi><mml:mo>=</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:math>, we also prove a matching lower bound in gate complexity (up to logarithmic factors). To establish the query lower bounds, we consider oracular problems including search and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">P</mml:mi><mml:mi mathvariant="normal">A</mml:mi><mml:mi mathvariant="normal">R</mml:mi><mml:mi mathvariant="normal">I</mml:mi><mml:mi mathvariant="normal">T</mml:mi><mml:mi mathvariant="normal">Y</mml:mi></mml:mrow><mml:mo>&#x2218;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="normal">O</mml:mi><mml:mi mathvariant="normal">R</mml:mi></mml:mrow></mml:math>, and also bounds on the degrees of trigonometric polynomials. To establish the lower bound on gate complexity, we use a circuit-to-Hamiltonian reduction, where a “clock Hamiltonian'' acting on a low-energy state can simulate any quantum circuit.