PofoliaShared via Pofolia

Quantum· 2019Q1

Hamiltonian Simulation by Qubitization

Guang Hao Low, Isaac L. Chuang

Short summary

A new quantum algorithm, 'qubitization', enables Hamiltonian simulation with optimal query complexity and low overhead, improving precision simulations quadratically.

AI-generated from the title and abstract; the full text is not read.

Key points

  • Introduces 'qubitization' for approximating $e^{-iHt}$.
  • Achieves optimal query complexity: $O(t + \log(1/\epsilon))$ to oracles.
  • Requires at most two additional ancilla qubits.
  • Offers quadratic speed-up for precision simulations compared to prior art.

AI-generated from the title and abstract; the full text is not read.

Abstract

We present the problem of approximating the time-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>−</mml:mo><mml:mi>i</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>H</mml:mi><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow><mml:mi>t</mml:mi></mml:mrow></mml:msup></mml:math>to error<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ϵ</mml:mi></mml:math>, where the Hamiltonian<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>H</mml:mi><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mo fence="false" stretchy="false">⟨</mml:mo><mml:mi>G</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mo>⊗</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">I</mml:mi></mml:mrow><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>U</mml:mi><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>G</mml:mi><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mo>⊗</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">I</mml:mi></mml:mrow><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math>is the projection of a unitary oracle<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>U</mml:mi><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow></mml:math>onto the state<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>G</mml:mi><mml:mo fence="false" stretchy="false">⟩</mml:mo></mml:math>created by another unitary oracle. Our algorithm solves this with a query complexity<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:mrow class="MJX-TeXAtom-ORD"><mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo></mml:mrow><mml:mi>t</mml:mi><mml:mo>+</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>ϵ</mml:mi></mml:mrow><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo></mml:mrow></mml:math>to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math>-sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>H</mml:mi><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow></mml:math>is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>H</mml:mi><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow></mml:math>in an invariant<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>SU</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:math>subspace. A large class of operator functions of<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>H</mml:mi><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow></mml:math>can then be computed with optimal query complexity, of which<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>−</mml:mo><mml:mi>i</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>H</mml:mi><mml:mo stretchy="false">^</mml:mo></mml:mover></mml:mrow><mml:mi>t</mml:mi></mml:mrow></mml:msup></mml:math>is a special case.

The authors' abstract, as published at the source. Quantum, 2019 · DOI ↗

TakeawaysPremium
Ask the paperFree account

Continue with a free account

Ask the paper: 3 free questions a day about this paper; save it, get its citation, new summaries every day for your field. Takeaways are Premium.

Continue free on the web

Sign in with Google or Apple; no card needed. You come back to this paper.

On your phone:

Get it on Google Play Download on the App Store

Related papers

Field: Numerical Analysis

Numerical AnalysisMathematics