Exponentially faster implementations of Select(H) for fermionic Hamiltonians
Kianna Wan
Abstract
We present a simple but general framework for constructing quantum circuits that implement the multiply-controlled unitary <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>Select</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mi>H</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>:=</mml:mo><mml:munder><mml:mo>∑</mml:mo><mml:mi>ℓ</mml:mi></mml:munder><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mi>ℓ</mml:mi><mml:mo fence="false" stretchy="false">⟩</mml:mo><mml:mo fence="false" stretchy="false">⟨</mml:mo><mml:mi>ℓ</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">|</mml:mo></mml:mrow><mml:mo>⊗</mml:mo><mml:msub><mml:mi>H</mml:mi><mml:mi>ℓ</mml:mi></mml:msub></mml:math>, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>H</mml:mi><mml:mo>=</mml:mo><mml:munder><mml:mo>∑</mml:mo><mml:mi>ℓ</mml:mi></mml:munder><mml:msub><mml:mi>H</mml:mi><mml:mi>ℓ</mml:mi></mml:msub></mml:math> is the Jordan-Wigner transform of an arbitrary second-quantised fermionic Hamiltonian. <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>Select</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mi>H</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> is one of the main subroutines of several quantum algorithms, including state-of-the-art techniques for Hamiltonian simulation. If each term in the second-quantised Hamiltonian involves at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> spin-orbitals and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> is a constant independent of the total number of spin-orbitals <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> (as is the case for the majority of quantum chemistry and condensed matter models considered in the literature, for which <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> is typically 2 or 4), our implementation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>Select</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mi>H</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> requires no ancilla qubits and uses <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>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> Clifford+T gates, with the Clifford gates applied in <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>l</mml:mi><mml:mi>o</mml:mi><mml:msup><mml:mi>g</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> layers and the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> gates in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>l</mml:mi><mml:mi>o</mml:mi><mml:mi>g</mml:mi><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> layers. This achieves an exponential improvement in both Clifford- and T-depth over previous work, while maintaining linear gate count and reducing the number of ancillae to zero.