Hamiltonian Simulation by Qubitization

By Guang Hao Low, Isaac L. Chuang. Quantum, 2016

1,196 citations recorded by the source corpus.

<jats:p>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.</jats:p>

Subfields: Computational Theory and Mathematics, Numerical Analysis, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/8bfe198cc4b6f4d1b74e87baf60c145d2f0ae072

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

In Statistical and Nonlinear Physics

Citations in the corpus

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “(Flexible) Quantum Signal Processing [44] [43] [41] [42] Quantum Singular Value Transf.”
Generalized Quantum Signal Processing (2023, methodology): “…the gate and query complexity of the underlying simulation method by on average a factor of 2 relative to the method described in Theorem 2 of [3] owing to the fact that each iteration in the circuit of Figure 1 requires queries to both controlled-U and controlled-U † ; whereas, each…”
Improved techniques for preparing eigenstates of fermionic Hamiltonians (2017, background): “Next, we summarize how qubitization works.(37) One assumes black-box access to a signal oracle V that encodes H in the form:”
A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery (2018, methodology): “In the speciﬁc case of quantum chemistry simulations, their T count can be reduced signiﬁcantly by using more advanced algorithms [45–47], which also proﬁt from arbitrary-angle rotations.”
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, methodology): “The essential simulation primitive deployed here (a quantum walk operator based on select and prepare) was first introduced as a subroutine to the qubitization approach for Hamiltonian time-evolution [25].”
Potential of quantum computing for drug discovery (2018, background): “More recently, an alternative approach called qubitization [175–177], where the evolution employs a quantum walk operator, has been proposed with near-optimal asymptotic performance.”
The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation (2018, methodology): “, U, combined with amplitude ampliﬁcation, can be used to generate the state A|ψi/ A|ψi given a circuit for generating |ψi. The main motivation for using block-encodings is that Low and Chuang showed [LC16] how to perform optimal Hamiltonian simulation given a block-encoded Hamiltonian A. In Ref. [K”
Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision (2017, background): “More recent work has streamlined these algorithms and improved their dependence on other parameters [6, 7, 15, 8, 14, 16].”
Hamiltonian Simulation in the Interaction Picture (2018, methodology): “In contrast, the cost of simulation in the plane-wave dual basis [14] applies the ‘Qubitization’ technique [10] and has gate complexity that scales like Õ((‖ζ‖1+N)Nt), and also has a polynomial dependence on the nuclear charges ζj .”