Efficient Simulation of Pre-Born-Oppenheimer Dynamics on a Quantum Computer Matthew Pocrnic, Ignacio Loaiza, Juan Miguel Arrazola, Nathan Wiebe, Danial Motlagh Abstract In this work, we present a quantum algorithm for direct first-principles simulation of electron-nuclear dynamics on a first-quantized real-space grid. Our algorithm achieves best-in-class efficiency for block-encoding the pre-Born-Oppenheimer molecular Hamiltonian by harnessing the linear scaling of swap networks for implementing the quadratic number of particle interactions, while using a novel alternating sign implementation of the Coulomb interaction that exploits highly optimized arithmetic routines. We benchmark our approach for a series of scientifically and industrially relevant chemical reactions. We demonstrate over an order-of-magnitude reduction in costs compared to previous state-of-the-art for the NH 3 + BF 3 \rm NH_{3}+BF_{3} reaction, achieving a Toffoli cost of 8.7 × 10 9 8.7\times 10^{9} per femtosecond using 1362 1362 logical qubits (system + ancillas). Our results significantly lower the resources required for fault-tolerant simulations of photochemical reactions, while providing a suite of algorithmic primitives that are expected to serve as foundational building blocks for a broader class of quantum algorithms. I Introduction As hardware developments bring fault-tolerant quantum computing closer to reality, the need for expanding the pool of useful applications of quantum computers intensifies. Quantum chemistry has long been viewed as a natural domain for such applications, offering a rich landscape of industrially relevant problems whose classical scaling is prohibitive. However, algorithmic development has overwhelmingly focused on solving the electronic structure problem within the Born-Oppenheimer approximation, with little attention given to development of quantum algorithms for dynamical problems. Although reaction rates and other dynamical observables can sometimes be inferred indirectly from electronic structure calculations through models such as transition state theory, their accuracy fundamentally relies on the validity of the Born–Oppenheimer approximation within the given physical context. Cases where this approximation breaks down are pervasive in chemistry 3 ; 11 ; 18 ; 30 ; 87 ; 5 ; 14 , particularly in photochemistry and reactions involving highly reactive radical species, where multiple electronic states are closely coupled. In these scenarios, non-adiabatic effects become dominant, rendering transition state theory and other methods based on a single potential energy surface insufficient; this necessitates going beyond the Born-Oppenheimer approximation for accurately obtaining quantities like reaction rates. Despite the existence of heuristics for including non-adiabatic effects on transition state calculations, their accurate treatment requires information from a full non-adiabatic dynamical treatment 86 ; 61 . Simulating pre-Born-Oppenheimer chemistry classically is a formidable challenge with a long history of developments, resulting in a wide array of approximations that typically trade accuracy for computational efficiency 18 ; 87 ; 5 ; 14 ; 59 ; 15 ; 28 . Despite the major successes of many methods, no single, efficient classical method exists that is applicable to general systems; the varying degrees of approximations translate into a mishandling of potentially critical quantum phenomena, such as electronic decoherence 85 , zero-point leakage 60 ; 89 , and non-adiabatic branching ratios 93 ; 43 , while also relying on the quality of the underlying electronic structure calculations. In contrast, exact classical methods that propagate the full molecular wavefunction suffer from the curse of dimensionality, exhibiting exponential cost scaling with the number of particles 30 ; 5 ; 54 . For an arbitrary reaction without prior knowledge of which effects are dominant, a method accounting for all effects is required. Such comprehensive classical methods are computationally intractable for all but the smallest systems. This establishes the simulation of non-adiabatic dynamics as a high-value frontier where quantum computers could greatly impact current computational workflows. Figure 1: Quantum simulation of chemical reactions on a real-space grid. The Coulomb interaction 1/r is implemented as a linear combination of unitaries using the alternating sign technique: an auxiliary register \ket{m} is prepared in an equal superposition over M values and flagged with \pm 1 phases depending on the value of r , such that the resulting sum approximates 1/r up to \mathcal{O}(1/M) accuracy. The flagging routine is efficiently implemented using quantum arithmetic. Quantum algorithms that go beyond the Born-Oppenheimer approximation have been proposed 64 ; 19 ; 69 . One avenue is the simulation of vibronic Hamiltonians, for which efficient low-cost quantum algorithms have been developed 64 . However, the construction of vibronic Hamiltonians requires prior knowledge of the relevant chemical space, while also relying on complex fitting procedures based on underlying electronic structure calculations 38 ; 92 . As such, the quality of this approach hinges on the quality of the electronic structure calculations and of the polynomial fit of the associated potential energy surfaces. Photochemical processes which typically exhibit large amplitude motion of nuclei require construction of highly anharmonic surfaces, with a steep increase in the required number of electronic structure calculations for vibronic model construction. In contrast, first-principles simulations of molecular dynamics bypass the need for electronic structure calculations when building a model Hamiltonian. Notably, Ref. 19 presented, to the best of our knowledge, the first full resource estimates for such simulations, using a plane-wave basis for both electronic and nuclear degrees of freedom in a first-quantized qubitization framework. While attractive for periodic systems like surfaces, this approach has two major drawbacks: the resource requirements remain outside the reach of early fault-tolerant quantum computers, and the periodic basis is ill-suited for non-periodic chemistry, especially for systems with a non-neutral electric charge, since the periodic boundary conditions cause a net infinite charge. In this work, we present a first-principles algorithm for simulating chemical dynamics on a first-quantized real-space grid, treating electrons and nuclei on equal footing. The amplitudes of the many-body wavefunction are encoded in a Cartesian grid, while the electrostatic Coulomb interaction is directly implemented in Cartesian coordinates. This approach is ideal for organic and photo-organic systems, avoiding the complexities of plane-wave bases. One of the main technical contributions of this work is a “swap network” block-encoding architecture, which generalizes the “swap up” technique from Ref. 19 . This framework allows us to recursively build block-encodings of multi-particle operators with a linear complexity in the number of particles \eta . Specifically, we evaluate all \mathcal{O}(\eta^{2}) pairwise electrostatic interactions with only \mathcal{O}(\eta) cost and reduce the required quantum Fourier transform (QFT) applications for kinetic terms from 6\eta to only 2 . To address the 1/r Coulomb bottleneck, we implement an efficient linear combination of unitaries (LCU) -based approach utilizing an alternating sign technique for block-encoding diagonal operators, as illustrated in Fig. 1 . By combining this with quantum-arithmetic-based comparators, we bypass the need for costly evaluation of inverse functions. Furthermore, we introduce two techniques to minimize the 1-norm: a spectral shifting technique that achieves a twofold reduction without altering the dynamics, and a saturation technique that exploits statistical bounds for the minimum nuclear-nuclear distance. These combined innovations achieve over an order-of-magnitude reduction in Toffoli counts for the \rm NH_{3}+BF_{3} reaction compared to previous benchmarks 19 , while maintaining a small ancilla footprint. Overall, our results bring the first-principles simulation of organic chemistry within closer reach of the first generations of fault-tolerant quantum computers. This paper is organized as follows. In Section II we give an overview of the molecular Coulomb Hamiltonian and the real-space encoding of the associated wavefunction, alongside a high-level summary of our approach for qubitizing this Hamiltonian. We then present our qubitization-based quantum algorithm in Section III . Resource estimates for a series of reactions of industrial relevance are presented in Section IV , alongside a discussion of our results. Finally, we present our conclusions in Section V . Reactants Number of particles (electrons) Toffolis per fs Toffolis per \mathcal{W} Logical qubits 1-norm \rm NH_{3}+BF_{3} 50\ (42) 8.72\times 10^{9} 8.2\times 10^{3} 1362\ (312) 1.88\times 10^{4} \rm 2NO_{2} 52\ (46) 1.05\times 10^{10} 8.6\times 10^{3} 1419\ (327) 2.15\times 10^{4} \rm C_{2}H_{4}+O_{2} 40\ (32) 7.07\times 10^{10} 8.5\times 10^{3} 1453\ (373) 1.46\times 10^{5} \rm C_{2}H_{4}+O_{3} 49\ (40) 8.05\times 10^{9} 8.1\times 10^{3} 1341\ (312) 1.76\times 10^{4} \rm C_{23}H_{20}N_{3}O 234\ (187) 2.73\times 10^{11} 2.2\times 10^{4} 6198\ (582) 2.16\times 10^{5} Table 1: Cost estimates for performing 1\ \rm fs of time evolution for various reactions using our algorithm, as detailed in Section IV . Logical qubits are reported in the format x\,(y) , where x is the total number of qubits (system + ancilla) with y being the number of ancillas, and x-y the number qubits required for encoding the problem. Due to the linear scaling of our algorithm in evolution time, the associated Toffoli cost for t femtoseconds of evolution can be estimated by multiplying the numbers presented by t . II Preliminaries We start by introducing the pre-Born-Oppenheimer molecular Hamiltonian. Given a system with \eta_{e} electrons and \eta_{n} nuclei, the full non-relativistic Coulomb Hamiltonian in position basis written in atomic units corresponds to H=\frac{1}{2}\left(-\sum_{l=1}^{\eta_{e}}\nabla^{2}_{l}-\sum_{\ell=1}^{\eta_{n}}\frac{\nabla^{2}_{\ell}}{m_{\ell}}\right)+\sum_{l\neq k}^{\eta_{e}}\frac{1}{2\|\vec{r_{l}}-\vec{r_{k}}\|}+\sum_{\ell\neq\kappa}^{\eta_{n}}\frac{\zeta_{\ell}\zeta_{\kappa}}{2\|\vec{R_{\ell}}-\vec{R_{\kappa}}\|}-\sum_{l=1}^{\eta_{e}}\sum_{\ell=1}^{\eta_{n}}\frac{\zeta_{\ell}}{\|\vec{r_{l}}-\vec{R_{\ell}}\|}. (1) Since both electrons and nuclei are treated on the same footing, we write the Hamiltonian more compactly H=\underbrace{\sum_{i=1}^{\eta}\frac{-\nabla^{2}_{i}}{2m_{i}}}_{T}+\underbrace{\sum_{i\neq j}(-1)^{\sigma_{i}+\sigma_{j}}\frac{\zeta_{i}\zeta_{j}}{2r_{ij}}}_{V}, (2) where i runs over all \eta=\eta_{e}+\eta_{n} particles with r_{ij}=\|\vec{r}_{i}-\vec{r}_{j}\| . Here m_{i} and \zeta_{i} correspond to particle i ’s mass and magnitude of its charge correspondingly, and \sigma_{i} encodes the sign of the particle’s charge \sigma_{i}=\begin{cases}1,\textup{ if particle }i\textup{ is an electron }\\ 0,\textup{ if particle }i\textup{ is a nucleus}.\end{cases} (3) Considering a cubic simulation box of volume \Omega=L^{3} , where each dimension has a width of L , we represent our wavefunction using a first-quantized real-space grid. We allocate 3 registers of size n_{g} for each particle, where the position of the particle along the x , y , and z axes are encoded in computational basis states of each register using a two’s complement encoding. Using n_{g} qubits to discretize each Cartesian coordinate induces the 3-dimensional grid G=[-2^{n_{g}-1},2^{n_{g}-1}-1]^{3} (4) with spacing \Delta=\frac{L}{2^{n_{g}}-1}. (5) The position of each particle is encoded by computational basis states \ket{\vec q}=\ket{q_x}\ket{q_y}\ket{q_z}\in G , giving the physical position and momentum of the particle via the transformation r_{q}=q\Delta,\;\;k_{p}=\frac{2\pi p}{\Delta}, (6) where position and momentum are related via the quantum Fourier transform (QFT) as \ket{p}=\textrm{QFT}\ket{q} . The associated molecular wavefunction will then be represented as \ket{\Psi}=\sum_{\vec{q}_{1},\vec{q}_{2},...,\vec{q}_{\eta}}\Psi(\vec{r}_{q_{1}},\cdots,\vec{r}_{q_{\eta}})\bigotimes_{i=1}^{\eta}\ket{\vec q_{i}}. (7) Since the Coulomb interaction from Eq. 2 could become unbounded if r_{ij}=0 , we define the discretized potential as V=\sum_{i\neq j}(-1)^{\sigma_{i}+\sigma_{j}}\zeta_{i}\zeta_{j}\sum_{\vec{q},\vec{s}}\frac{S(\|\vec{r}_{q}-\vec{r}_{s}\|)}{2}\outerproduct{\vec q}{\vec q}_{i}\otimes\outerproduct{\vec{s}}{\vec{s}}_{j}, (8) where S(r)=\begin{cases}\frac{1}{r},&\textrm{ if }r>\Delta\\[8.0pt] \frac{1}{\Delta},&\textrm{ if }r\leq\Delta.\end{cases} (9) To make this a faithful representation, n_{g} must be chosen such that the physical wavefunction for the problem of interest has negligible overlap with configurations where two particles come closer than \Delta . A discussion on how to choose the number of qubits n_{g} such that the induced grid spacing faithfully represents the molecular wavefunction is provided in Appendix D . Lastly, we define the momentum basis for each particle to be related to the position basis via a QFT of each of the Cartesian registers with associated discretized kinetic operator defined as T=\frac{2\pi^{2}}{L^{2}}\sum_{i}\sum_{\vec{q}}\frac{\|\vec{q}\|^{2}}{m_{i}}\textup{QFT}_{i}^{\dagger}\cdot\outerproduct{\vec q}{\vec q}_{i}\cdot\textup{QFT}_{i}. (10) III Quantum algorithm In this section, we describe our quantum signal processing (QSP) -based simulation algorithm for implementing the time evolution e^{-iHt} under the molecular Coulomb Hamiltonian Eq. 2 . The main contribution of this work is the development of a highly optimized block-encoding protocol for H that scales linearly with the number of particles in the system despite the quadratic number of interactions in the Hamiltonian. Our key results are summarized in the following theorems that state the time and space complexity of our algorithm for block-encoding and performing time evolution under H . Theorem 1 (Block-encoding with linear scaling) . Let H=T+V\in\mathcal{L}(\mathbb{C}^{2^{3\eta\cdot n_{g}}}) be the discretized Hamiltonian shown in Eqs.( 8 , 10 ). There exists an (\alpha_{H},n_{H},\epsilon) block-encoding of H (up to a constant shift) that can be constructed using \tilde{\mathcal{O}}\left(\eta+\log^{2}\frac{1}{\epsilon}\right) (11) Toffolis, and where we have used the following definitions for the 1-norm and number of block-encoding qubits respectively: \displaystyle\alpha_{H} \displaystyle=\frac{\lambda_{V}}{4\Delta}+\frac{3\pi^{2}2^{2(n_{g}-1)}}{L^{2}}\lambda_{T}\in\mathcal{O}(\eta^{2}), (12) \displaystyle n_{H} \displaystyle=2\left\lceil\log_{2}\eta\right\rceil+n_{M}+3\in\mathcal{O}\left(\log\eta+\log\frac{1}{\epsilon}\right), (13) and \epsilon corresponds to the overall error of this operation. Here n_{M}\in\mathcal{O}(\log\eta/\epsilon) is the number of ancillas for implementing the Coulomb interaction with the target accuracy. We simplify notation by defining the sum of charge interactions \lambda_{V}:=\sum_{j\neq k=1}^{\eta}\zeta_{j}\zeta_{k}\in\mathcal{O}(\eta^{2}) and the sum of reciprocal masses \lambda_{T}:=\sum_{j}m_{j}^{-1}\in\mathcal{O}(\eta) . Once the qubitized walk operator is constructed from the block-encoding of H/\alpha_{H} we can use the technique of QSP 51 ; 52 ; 8 ; 65 to implement the time-evolution operator using \mathcal{O}(\alpha_{H}t+\log(1/\epsilon)) calls to the walk operator. This gives us the following complexity for implementation of the e^{-iHt} operator using our algorithm. Theorem 2 (Time evolution) . Given a Hamiltonian H of the form defined in Eq. ( 2 ), a simulation time t , and error \epsilon , there exists a quantum algorithm to implement the time-evolution operator e^{-iHt} , up to a global phase, using \tilde{\mathcal{O}}\left(\eta^{3}t+\eta\log\frac{1}{\epsilon}\right) (14) Toffoli gates, while using \displaystyle\mathcal{O}\left(\log\eta+\log\frac{t}{\epsilon}\right) ancilla qubits. We now describe our quantum algorithm in more details, starting from our strategy for block-encoding the potential operator. III.1 Block-encoding the potential At a high-level, our algorithm block-encodes V via an linear combination of unitaries (LCU) of the block-encodings of each saturated Coulomb term \displaystyle V_{ij}=\frac{S(r_{ij})}{2} . Notice that \displaystyle V \displaystyle=\sum_{i\neq j}^{\eta}(-1)^{\sigma_{i}+\sigma_{j}}\zeta_{i}\zeta_{j}\,V_{ij}, \displaystyle=\sum_{i\neq j}^{\eta}(-1)^{\sigma_{i}+\sigma_{j}}\zeta_{i}\zeta_{j}\,\left({\textup{SWAP}_{1\leftrightarrow i,\,2\leftrightarrow j}}\right)V_{12}\left({\textup{SWAP}_{1\leftrightarrow i,\,2\leftrightarrow j}}\right), (15) where {\textup{SWAP}_{1\leftrightarrow i,\,2\leftrightarrow j}} is the operator that swaps the register corresponding to particle i with that of particle 1 , and particle j with particle 2 . Defining \bra{0}U_{12}^{(V)}\ket{0}=2\Delta\cdot V_{12} as the unitary block-encoding V_{12} , we can therefore implement the block-encoding \bra{0}V_{\text{BE}}\ket{0}=\Delta\cdot V/\lambda_{V} via \displaystyle V_{\text{BE}}=\text{PREP}_{V}^{\dagger}\cdot\text{SEL}_{V}\cdot\text{PREP}_{V}, (16) where \displaystyle\text{PREP}_{V}\ket{0}\ket{0}=\frac{1}{\sqrt{\lambda_{V}}}\sum_{i\neq j}^{\eta}\sqrt{\zeta_{i}\zeta_{j}}\,\ket{i}\ket{j},\quad\quad\lambda_{V}=\sum_{i\neq j}^{\eta}\zeta_{i}\zeta_{j}, (17) and \displaystyle\text{SEL}_{V}=\left(\sum_{i,j}^{\eta}(-1)^{\sigma_{i}+\sigma_{j}}\,\outerproduct{i}{i}\otimes\outerproduct{j}{j}\otimes{\textup{SWAP}_{1\leftrightarrow i,\,2\leftrightarrow j}}\right)U^{(V)}_{12}\left(\sum_{i,j}^{\eta}\outerproduct{i}{i}\otimes\outerproduct{j}{j}\otimes{\textup{SWAP}_{1\leftrightarrow i,\,2\leftrightarrow j}}\right). (18) Here the factor of 2 that multiplies \Delta comes from the fact that we are double counting the particle interactions in the sum. Note how the swap network above can be implemented with complexity linear in \eta due to its product form \displaystyle\sum_{i,j}^{\eta}\outerproduct{i}{i}\otimes\outerproduct{j}{j}\otimes{\textup{SWAP}_{1\leftrightarrow i,\,2\leftrightarrow j}}=\left(\sum_{i}^{\eta}\outerproduct{i}{i}\otimes\mathbb{I}\otimes{\textup{SWAP}_{1\leftrightarrow i}}\right)\left(\sum_{j}^{\eta}\,\mathbb{I}\otimes\outerproduct{j}{j}\otimes{\textup{SWAP}_{2\leftrightarrow j}}\right). (19) We now describe how the block-encoding U^{(V)}_{12} is implemented via the alternating sign technique. We start by considering the normalized saturated Coulomb interaction 2\Delta\cdot V_{12}=\Delta\cdot S(r_{12}) , which can take values between 0\leq\Delta\cdot S(r)\leq 1 . The idea is to partition this interval into M components with uniform weights 1/M , where each one will correspond to a different unitary in an LCU , recovering \Delta\cdot S(r) by adding all M components. This amounts to partitioning this interval as [0,1/M,2/M,\cdots,m/M,\cdots,1) . For a given component m , we flag it with a value of 1 if m/M<\Delta\cdot S(r) , and with an alternating (-1)^{m} otherwise. The alternating sign destructively cancels these (-1)^{m} components, while the constructive sum adds up to the target \Delta\cdot S(r) . This procedure is illustrated in Fig. 1 , which amounts to encoding the Coulomb interaction as the LCU \displaystyle 2\Delta\cdot V_{12} \displaystyle=\lim_{M\to\infty}\,\frac{1}{M}\sum_{m=0}^{M-1}\underbrace{\sum_{\vec{q}_{1},\vec{q}_{2}}u_{m}\left(\|\vec{q}_{1}-\vec{q}_{2}\|^{2}\right)\,\,\outerproduct{\vec q_1}{\vec q_1}\otimes\outerproduct{\vec q_2}{\vec q_2}}_{U_{m}}, (20) where u_{m}\left(x\right):=\begin{cases}1,&\textup{ if }\,\,m^{2}\cdot x\Gamma^{2}\cdot M^{2}, (23) whenever both particles are nuclei, which requires replacing the subtraction routine in Fig. 2 by its controlled counterpart in Lemma 12 . We then need to modify the PREPARE circuit for V such that \displaystyle\text{PREP}_{V,\Gamma}\ket{0}\ket{0}=\frac{1}{\sqrt{\tilde{\lambda}_{V}}}\sum_{i\neq j}^{\eta}\sqrt{\gamma(i,j)}\,\ket{i}\ket{j},\quad\quad\tilde{\lambda}_{V}=\sum_{i\neq j}^{\eta}\gamma(i,j), (24) where \displaystyle\gamma(i,j)=\begin{cases}\frac{\zeta_{i}\zeta_{j}}{\Gamma},&\textrm{ if particle }i\textrm{ and }j\textrm{ are both nuclei },\\[8.0pt] \zeta_{i}\zeta_{j}&\textrm{ otherwise }.\end{cases} (25) In principle, the constant \Gamma can also depend on which species of nuclei are interacting. For example, the average bond distance between carbon atoms is significantly larger than that of hydrogen atoms. However, such specifications require additional modifications for flagging different interaction types and controlling the inequality test, which is left as future work. Finally, we note that this technique can be combined with the previously mentioned shifting technique, reducing the 1-norm by a factor of two, with all details presented in Lemma 20 . III.2 Block-encoding the kinetic operator Similar to the potential, we block-encode T via an LCU of the block-encodings of each term \displaystyle T_{i}=\frac{\|\vec{p}_{i}\|^{2}}{2} , where \vec{p}_{i} is the momentum vector associated to the real-space coordinate \vec{q}_{i} via a discrete Fourier transform over each Cartesian direction. The kinetic energy is thus written as \displaystyle T \displaystyle=\sum_{i=1}^{\eta}\frac{1}{m_{i}}T_{i}, \displaystyle=\sum_{i=1}^{\eta}\frac{1}{m_{i}}\left({\textup{SWAP}_{1\leftrightarrow i}}\right)T_{1}\left({\textup{SWAP}_{1\leftrightarrow i}}\right) (26) Defining \bra{0}U_{1}^{(T)}\ket{0}=2\Delta^{2}\cdot T_{1} as the unitary block-encoding T_{1} , we can therefore implement the block-encoding \bra{0}T_{\text{BE}}\ket{0}=\Delta^{2}\,T/\lambda_{T} via \displaystyle T_{\text{BE}}=\text{PREP}_{T}^{\dagger}\cdot\text{SEL}_{T}\cdot\text{PREP}_{T}, (27) where \displaystyle\text{PREP}_{T}\ket{0}=\frac{1}{\sqrt{\lambda_{T}}}\sum_{i}^{\eta}\frac{1}{\sqrt{m_{i}}}\,\ket{i},\quad\quad\lambda_{T}=\sum_{i}^{\eta}\frac{1}{m_{i}}, (28) and \displaystyle\text{SEL}_{T}=\left(\sum_{i=1}^{\eta}\,\outerproduct{i}{i}\otimes{\textup{SWAP}_{1\leftrightarrow i}}\right)U_{1}^{(T)}\left(\sum_{i=1}^{\eta}\,\outerproduct{i}{i}\otimes{\textup{SWAP}_{1\leftrightarrow i}}\right). (29) We now describe how the block-encoding U_{1}^{(T)} is implemented. We can write \Delta^{2}\cdot T_{1} as an LCU by using a swap network to nest computation over different Cartesian indices w as: \displaystyle U_{1}^{(T)} \displaystyle=\sum_{w\in\{x,y,z\}}(\text{SWAP}_{x\leftrightarrow w})\textrm{QFT}_{1,x}^{\dagger}\left(\sum_{q_{1,x}}|q_{1,x}|^{2}\outerproduct{q_{1,x}}{q_{1,x}}\right)\textrm{QFT}_{1,x}(\text{SWAP}_{x\leftrightarrow w}), (30) \scriptstyle n_{g}+1 \scriptstyle n_{g} \scriptstyle n_{g} \scriptstyle n_{g} \ket{ctl} \ket{0} \text{PREP}_{W} \text{PREP}_{W} \text{PREP}^{\dagger}_{W} \text{PREP}^{\dagger}_{W} \ket{0} \ket{0} \ket{0} \ket{q_{x}} QFT QFT \mathtt{SQ} \mathtt{SQ} \text{QFT}^{\dagger} \text{QFT}^{\dagger} \ket{q_{y}} \ket{q_{z}} Figure 3: Controlled block-encoding of kinetic energy of single particle U_{1}^{(T)} in Eq. 30 , with squaring routine implementing \mathtt{SQ}\ket{q}\rightarrow(2q^{2}-1)\ket{q} . See Appendix A for a detailed explanation of all circuit directives. where the (1,x) indicates operations being done on the register encoding particle 1 ’s Cartesian direction x . We now require a routine squaring a two’s complement register for implementing the |q|^{2} component, which is done here by block-encoding the action \mathtt{SQ}\ket{q}=(2q^{2}-1)\ket{q} . This routine has the benefit of effectively reducing the associated 1-norm by a factor of 2 when compared to a direct block-encoding of \ket{q}\rightarrow q^{2}\ket{q} , while the identity causes a known constant shift in the Hamiltonian that can be effectively ignored. The basic idea for implementing this operation is to implement it by two repetitions of a walk operator block-encoding \mathtt{Amp}\ket{q}=q\ket{q} . To understand how the block-encoding \mathtt{Amp} works, note that for an n -bit unsigned (positive) integer a we can write a=\sum_{b=0}^{n-1}\bar{a}_{b}2^{b} , where \bar{a}_{b}=\{0,1\} is the value of the b th bit. We can encode the amplitudes of n -bit positive integers in a one-hot encoded state \mathtt{amp_{n}}\ket{0}^{n}:=\ket{\sqrt{\mathtt{amp_n}}}\propto\sum_{b=0}^{n-1}2^{b/2}X_{b}\ket{0}^{n} , where X_{b} is a Pauli X operator acting on qubit b . The idea is to then check the bit-wise product of this state with the bits encoding a , appending amplitudes to the block-encoding when the associated bit \bar{a}_{b}=1 and cancelling amplitudes when \bar{a}_{b}=0 . We thus obtain the block-encoding for unsigned integers: \sum_{a}a\outerproduct{a}{a}\rightarrow(\mathtt{Had}\otimes\mathtt{amp_{n}}\otimes\mathbb{I})^{\dagger}\Bigg(\sum_{h=0,1}\sum_{b=0}^{n-2}\outerproduct{h,b}{h,b}\otimes U_{h,b}\Bigg),(\mathtt{Had}\otimes\mathtt{amp_{n}}\otimes\mathbb{I}) (31) where we have defined U_{h,b}\outerproduct{a}{a}=k_{h}(\bar{a}_{b})\outerproduct{a}{a} (32) for k_{h}(x)=\begin{cases}1,\>&\textrm{if}\>x=1\\ (-1)^{h},\>&\textrm{if}\>x=0.\end{cases} (33) Note that some additional details are required due to how we are dealing with negative numbers, having the full specification of this block-encoding presented in Lemma 9 . On a high level, the circuit implementing T_{1} is shown in Fig. 3 , corresponding to the following steps: 1. Prepare a uniform superposition over three qubits \ket{W}=(\ket{100}+\ket{010}+\ket{001})/\sqrt{3} ( Lemma 14 ). Controlled on the associated one-hot encoding of \ket{w} , swap the Cartesian registers x\leftrightarrow w . 2. Apply QFT on the register \ket{q_{1,x}} , the x th Cartesian coordinate of the 1 st particle register that has been swapped in. 3. Apply the block-encoding for \mathtt{SQ}\ket{q}\rightarrow(2q^{2}-1)\ket{q} on the \ket{\cdot}_{1,x} register ( Lemma 9 ). 4. Uncompute steps 1-2. \scriptstyle\left\lceil\log_{2}\eta\right\rceil \scriptstyle\left\lceil\log_{2}\eta\right\rceil \scriptstyle 3n_{g} \scriptstyle 3n_{g} \scriptstyle 3n_{g} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} \ket{T/V}_{H} Z^{\sigma_{i}} Z^{\sigma_{i}} Z^{\sigma_{j}} Z^{\sigma_{j}} \ket{\vec 0} \textup{PREP}_{V} \textup{PREP}_{V} In(i) In(i) In(i) In(i) \textup{PREP}_{V}^{\dagger} \textup{PREP}_{V}^{\dagger} \ket{\vec 0} \textup{PREP}_{T} \textup{PREP}_{T} In(j) In(j) In(j) In(j) \textup{PREP}_{T}^{\dagger} \textup{PREP}_{T}^{\dagger} \ket{0}_{\mathcal{N}} U_{12}^{(V)} U_{12}^{(V)} \ket{\vec q_1} \textrm{SWAP}_{1\leftrightarrow i} \textrm{SWAP}_{1\leftrightarrow i} \textrm{SWAP}_{2\leftrightarrow j} \textrm{SWAP}_{2\leftrightarrow j} \textrm{SWAP}_{2\leftrightarrow j} \textrm{SWAP}_{2\leftrightarrow j} \textrm{SWAP}_{1\leftrightarrow i} \textrm{SWAP}_{1\leftrightarrow i} \ket{\vec q_2} U_{1}^{(T)} U_{1}^{(T)} \ket{\vec q_\eta} Figure 4: SEL operator for block-encoding full Hamiltonian in Eq. 35 . The block-encoding U_{12}^{(V)} is shown in Fig. 2 , while U_{1}^{(T)} corresponds to Fig. 3 . The \ket{\cdot}_{\mathcal{N}} register flags nuclear-nuclear interactions for the optimized potential energy implementation. III.3 Block-encoding the full Hamiltonian Equipped with a block-encoding of the kinetic and potential terms, we can now combine them with an LCU circuit as an outer-loop. This is achieved by summing the two block-encodings with relative weights proportional to their 1-norm, which can be done with the rotation R_{y}(\theta_{\alpha})\ket{0}_{H}=\cos(\theta_{\alpha}/2)\ket{0}_{H}+\sin(\theta_{\alpha}/2)\ket{1}_{H} for \theta_{\alpha}:=2\arccos\sqrt{\alpha_{T}/(\alpha_{V}+\alpha_{T})} up to some specified precision. Here we used \alpha_{T}=\lambda_{T}2^{2(n_{g}-1)}3\pi^{2}L^{-2} and \alpha_{V}=\lambda_{V}/4\Delta . We can now define the outer-loop PREPARE and SELECT circuits as follows: \textup{PREP}\ket{0}_{H}=\sqrt{\frac{\alpha_{T}}{\alpha_{V}+\alpha_{T}}}\ket{0}_{H}+\sqrt{\frac{\alpha_{V}}{\alpha_{V}+\alpha_{T}}}\ket{1}_{H}, (34) \textup{SEL}=\outerproduct{0}{0}_{H}\otimes O_{T}+\outerproduct{1}{1}_{H}\otimes O_{V}, (35) where O_{X} represents the block-encoding of the associated operator. Constructing these unitaries allows to sum the block-encodings provided by O_{V} and O_{T} as \bra{0}_{H}(\textup{PREP}^{\dagger}\otimes\mathbb{I})\textup{SEL}(\textup{PREP}\otimes\mathbb{I})\ket{0}_{H}=\frac{T+V}{\alpha_{V}+\alpha_{T}}=\frac{H}{\alpha_{H}}, (36) As expected, the subnormalization of the overall block-encoding is the sum of the 1-norms of each block-encoding in the sum, namely \alpha_{H}=\alpha_{V}+\alpha_{T} . We formalize this, as well as the other block-encoding parameters for a sum of distinct block-encodings in Lemma 16 in Appendix B . Note that the block-encodings for the kinetic and potential operator can here be chosen to be either of the different versions with or without optimizations (e.g. variable saturation, spectral shifts); the associated 1-norms \alpha_{T} and \alpha_{V} will depend on what version of the block-encoding is chosen. An additional optimization that can be done when performing this linear combination of block-encodings of V and T by noticing that both block-encodings use a swap network. This fact can be exploited to implement the swap network only once for both block-encodings simultaneously, as shown in Fig. 4 . The correct action of this circuit follows immediately from a case-by-case analysis over the control qubit, having that controlled on 0(1) it implements the block-encoding for T(V) . Note that some control logic has been added to include the electronic phases (-1) for encoding signs of charges in the potential energy, which as shown in Section A.1 can be done using only CZ operations for no additional non-Clifford cost. IV Application Having presented our algorithm for performing pre-Born-Oppenheimer dynamics on a quantum computer, we now discuss potential applications of our approach and report resource requirements for various industrially and scientifically relevant reactions. For chemical processes characterized by strong non-adiabatic effects and pronounced nuclear quantum effects, particularly in regimes where accurate electronic structure is unavailable, nuclear motion is large, or reaction pathways are not known a priori, black-box ab initio approaches such as the one proposed here provide the only systematic means of capturing the underlying physics without introducing uncontrolled approximations. This capability is essential for mechanistic studies and screening workflows, where prior identification of relevant nuclear configurations is often infeasible. By directly evolving the full molecular wavefunction in real time, our approach enables access to virtually any observable of interest throughout the reaction, thereby supporting a comprehensive elucidation of reaction mechanisms. We identify two primary cases where this rigorous treatment is essential for industrial and scientific applications. First are cases where the Born-Oppenheimer approximation fails, which generally happens as multiple electronic states become energetically accessible throughout a reaction and non-adiabatic effects play important roles. This is most often exemplified in photochemistry, with relevant applications in photolithography 90 ; 41 ; 16 , photocatalysis 32 ; 46 , light-harvesting processes 81 ; 22 , and atmospheric chemistry 63 ; 21 . Non-adiabatic effects also appear in radical chemistry due to small energy gaps in different electronic states, allowing thermal access to excited states in some biological 1 ; 33 ; 37 and combustion 2 ; 68 processes, while also having a pervasive appearance in organic synthesis reactions 55 ; 66 . Second, nuclear quantum effects such as zero-point energy and tunnelling are dominant in isotope separation 10 ; 35 and hydrogen transfer reactions 30 ; 36 ; 6 , which play central roles in green energy production 27 ; 44 . Perhaps most critical are coupled phenomena, such as proton-coupled electron transfer in fuel and solar cells 29 ; 91 and symmetry breaking (e.g., Peierls distortion) in organic electronics 31 ; 13 , which rely on a concerted interplay between electronic and nuclear quantum effects. We now present resource estimates for the simulation of selected chemical reactions with potential industrial impact. We start by providing a list of the reactions and a short discussion of their industrial relevance. Note that the addition of pseudopotentials could alleviate qubit requirements by both decreasing electron counts and relaxing grid spacings, while diminishing 1-norms and including relativistic effects for heavier elements. This is left as future work, where we expect large portions of the required machinery to be similar to the pseudoions implementations from Ref. 19 while working on a real-space grid. As such, we here focus on chemistry consisting of elements on the first two rows of the periodic table. 1. Ammonia and boron trifluoride Lewis acid-base reaction (\rm NH_{3}+BF_{3}) . This reaction contains electron transfer and bond stabilization, which are fundamental processes in many catalytic reactions. This system was used for benchmarking with Ref. 19 , while still exhibiting stereotypical chemistry of interest. 2. Nitrogen dioxide dimerization (\rm 2NO_{2}) . This reaction is related to nitric acid production in the Ostwald process 26 , as well as rocket propellants 77 and atmospheric chemistry 73 . Despite the dimerization itself being well described by Born-Oppenheimer approximation, it has been shown that in industrial and ignition settings the \rm N_{2}O_{4} dimer can isomerize while changing electronic character, which leads to non-adiabatic effects 62 ; 73 . 3. Hydrocarbon combustion (\rm C_{2}H_{4}+O_{2}) . The combustion of hydrocarbons remains a fundamental driver of global energy systems, having a large variety of radical species and strong non-adiabatic effects which make their classical simulation difficult. This reaction also appears during the Wacker process in presence of a catalyst, which is used for the production of acetaldehyde with a large impact in the production of specialty chemicals. The extreme conditions under which this process occurs make it extremely challenging to model, with the exact reaction mechanism being a highly debated topic 83 ; 34 . 4. Ozonolysis of ethene (\rm C_{2}H_{4}+O_{3}) . The ozone-based cleavage of carbon double bonds is used to produce a variety of high value specialty chemicals in the pharmaceutical industry 76 ; 88 , with ozonolysis reactions also appearing in atmospheric chemistry. The diradical character of ozone has a complex electronic structure, with a variety of competing decomposition pathways and low reaction barriers making classical simulations challenging. 5. Photoactivated double proton-coupled electron transfer (\rm C_{23}H_{20}N_{3}O) . Molecules with similar structures 78 ; 42 have been proposed for designing next-generation solar harvesting devices, potentially having unparalleled efficiencies by improving the electron transfer through a coupling with protons. Overall, proton-coupled electron transfer plays an important role in solar light harvesting processes. Having access to excited states through the photoactivation requires the inclusion of non-adiabatic effects, while the proton transfer needs a full quantum mechanical treatment of protons. Resource estimates for performing 1 femtosecond of time evolution for the discussed systems are presented in Table 1 . Our estimates were obtained by adding the costs of each component in our block-encoding subroutine ( Section B.3 ), multiplied by the number of calls made to the block-encoding of the Hamiltonian for implementing e^{-iHt} via QSP ( Appendix C ). The potential energy was implemented with the most optimal version as discussed in Lemma 20 , which incorporates both a variable saturation for the nuclear-nuclear interactions ( Appendix E ) alongside a spectral shift that halves the 1-norm of our block-encoding by introducing a global phase. All relevant hyperparameters for our estimations are presented in Appendix G . A maximum error of \epsilon=10^{-2} was used for the total time evolution, with the error allocation being optimized to minimize the cost while satisfying this total error budget. Note that the subdominant logarithmic dependence of resources with respect to errors translates to minor variations in the algorithmic costs even if \epsilon and the error allocation vary significantly. For instance, reducing the error by 9 orders of magnitude to \epsilon=10^{-11} , only increases the Toffoli count by less than a factor of 2.1 , requiring 1.76\times 10^{10} instead of 8.72\times 10^{9} Toffolis per femtosecond for the \rm NH_{3}+BF_{3} reaction, while requiring 4.13\times 10^{11} instead of 2.73\times 10^{11} for the \rm C_{23}H_{20}N_{3}O system, while increasing the ancilla counts from 312 and 582 to 612 and 700 respectively. Using the uniform allocation of errors in Table 3 instead of an optimized one modified the Toffoli counts by less than 5\% in all reactions. This minor dependence with respect to errors shows how for practical purposes a uniform error allocation is enough for close to optimal results. Figure 5: a) Toffoli cost decomposition per walk operator for different reactions. b) Toffoli cost decomposition of U^{(V)}_{12} operation implementing 1/r interaction for \rm NH_{3}+BF_{3} reaction. Note that cost profiles are extremely similar for different reactions. The Toffoli requirements for each walk operator are relatively modest, ranging from 8.1\times 10^{3} to 2.2\times 10^{4} for all systems studied in this work, making the 1-norms the significant amplifier of the algorithmic overhead. This is particularly noticeable for the higher cost of the \rm C_{2}H_{4}+O_{2} reaction, having that the high-temperature required a significantly finer grid, which in turn increased its 1-norm and total Toffoli cost by about an order of magnitude. Overall, we expect for techniques reducing the 1-norms, such as the variable saturations used in this work, to provide a direction for further algorithmic improvements. The inclusion of pseudopotentials could be used both for this purpose and for lowering the qubit counts, with their implementation left as future work. Finding additional ways to further lower the qubit counts will be important for making this type of black-box simulation of chemical reactions feasible for the first generation of fault-tolerant hardware. Note how the main contribution for the logical qubits comes from the first-quantized encoding of the molecular wavefunction, with ancilla qubits consisting of less than 26\% of the total qubit counts across all studied reactions. A profiling of the different factors contributing to the overall cost is presented in Fig. 5 a. It can be seen how the main contribution to the cost for smaller reactions comes from the alternating sign implementation of the 1/r interaction through the U_{12}^{(V)} operator. However, this cost remains mostly constant as the number of particles increases, having that the swap network becomes more expensive as the system size grows: this is the only component with a dominant contribution that has a linear scaling with respect to the number of particles, namely \mathcal{O}(\eta) . For the PREPARE routines, the utilization of QROM with dirty ancillas 7 ; 53 , often called QROAM, effectively decreases their Toffoli scaling by a quadratic factor as \tilde{\mathcal{O}}(\eta)\rightarrow\tilde{\mathcal{O}}(\sqrt{\eta}) , having that the optimal number of dirty ancillas for minimizing the Toffoli counts was always available throughout this work. Note that for the smaller reactions (e.g. \rm NH_{3}+BF_{3} ) it is more advantageous to use the PREPARE routine loading a symmetric matrix that directly loads \mathcal{O}(\eta^{2}) coefficients, while for larger systems (e.g. \rm C_{23}H_{20}N_{3}O ) the PREPARE routine based on amplitude amplification that only loads \mathcal{O}(\eta) coefficients becomes more advantageous, as expected from its better scaling. See Section A.8 for a more detailed discussion on the different PREPARE routines for the potential energy term. Finally, we note how the Toffoli cost contribution from the kinetic energy routine is completely subdominant for each individual oracle, having that the significant contribution from the kinetic term will only appear through the 1-norm. The cost profile for the operations implementing the 1/r interaction corresponding to the U_{12}^{(V)} operator is shown in Fig. 5 b. The main cost of this routine corresponds to the multiplication step before the inequality test, namely \ket{m^2}\ket{r^2}\rightarrow\ket{m^2}\ket{r^2}\ket{m^2r^2} , with the other large contribution being the squaring \ket{m}\rightarrow\ket{m}\ket{m^2} . The large cost from these routines comes from the number of qubits n_{M} that is required in the \ket{m} register for implementing the alternating sign technique. Overall, we expect for this kind of profiling of routine costs to provide guidance for focusing further algorithmic improvements. With a simulation cost per femtosecond of 8.72\times 10^{9} Toffolis for the \rm NH_{3}+BF_{3} reaction, our estimates present the lowest cost so far for a black-box quantum simulation of this chemical reaction. While efficient fully first-principles modelling remains a grand challenge, these results indicate that continued optimization could unlock this application on first-generation fault-tolerant devices. Furthermore, our framework could potentially be extended as to include thermodynamic environments 82 , with solvent effects being crucial for high-impact applications such as the modelling of homogeneous catalysis 20 . V Conclusion In this work we introduced a first-principles quantum algorithm for the direct simulation of chemical dynamics on a real-space grid. By treating electrons and nuclei on an equal footing, our approach goes beyond the Born-Oppenheimer approximation, providing a scalable framework for investigating radical reactions, photo-chemistry, and general non-adiabatic phenomena without the need for uncontrolled approximations. We presented a quantum signal processing (QSP) -based framework for simulating pre-Born-Oppenheimer dynamics with significantly reduced resource requirements compared to previous works 19 . Central to our approach is the “swap network” block-encoding, which enables the implementation of the potential energy operator with linear complexity \mathcal{O}(\eta) despite having \mathcal{O}(\eta^{2}) pairwise interactions, while reducing the required quantum Fourier transform (QFT) s for the kinetic energy implementation from 6\eta to only 2 . Furthermore, we address the 1/r electrostatic interaction bottleneck through an efficient implementation using the alternating sign technique for block-encoding diagonal operators. In addition, we introduced two 1-norm reduction techniques: a global energy shift that halves the 1-norm without modifying the dynamics, and a saturation technique leveraging statistical bounds on minimal nuclear-nuclear distances. Given a 1-norm that grows quadratically with the number of particles, our framework yields an overall complexity of \tilde{\mathcal{O}}(\eta^{3}t) for time evolution e^{-iHt} . Through the presented optimizations, we achieved over an order-of-magnitude reduction in Toffoli requirements compared to existing state-of-the-art 19 , while also requiring a smaller number of ancilla qubits. For the simulation of the ammonia and boron trifluoride \rm NH_{3}+BF_{3} reaction, 8.72\times 10^{9} Toffoli gates per femtosecond of simulation time were required, while algorithmic ancillas had a subdominant contribution to the overall qubit requirements: 1050 qubits were needed for the molecular wavefunction while only using 312 additional ancillas for the qubitization routine. While the Toffoli cost associated with individual walk operators remains relatively modest, the overall algorithmic complexity continues to be dominated by the magnitude of the 1-norms. This suggests that future improvements for lowering the 1-norms present a promising avenue for further optimizations, alongside the incorporation of pseudopotentials. We note that the preparation of initial states is expected to have a subdominant cost with respect to that of the time evolution, with our initial state preparation routine being identical to that from Ref. 19 up to a QFT . Detailed construction of initial state preparation routines and associated resource estimates are left as future work. By providing a highly optimized black-box algorithm that is particularly well-suited for organic and photo-organic chemistry, this work narrows the gap between fully first-principles simulations and the requirements of fault-tolerant hardware. Efficient first-principles simulations hold the potential to revolutionize the modelling of chemical reactions that remain intractable for classical methods, positioning quantum computers to address high-impact industrial and scientific challenges. Acknowledgements. We thank Tyler Kharazi for providing algorithmic suggestions and feedback that improved the quality of the paper. We also thank Diksha Dhawan, Jay Soni, and Torin Stetina for useful discussions, and Tarik El-Khateeb for producing the Fig. 1 graphic. MP acknowledges funding from Mitacs and the NSERC Post-Graduate Doctoral Scholarship. We acknowledge the Applied Quantum Computing Challenge program of the National Research Council of Canada for financial support (grant number AQC-103-2). NW’s work on this project was supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Co-design Center for Quantum Advantage (C2QA) under contract number DE- SC0012704 (PNNL FWP 76274) and PNNL’s Quantum Algorithms and Architecture for Domain Science (QuAADS) Laboratory Directed Research and Development (LDRD) Initiative. The Pacific Northwest National Laboratory is operated by Battelle for the U.S. Department of Energy under Contract DE-AC05-76RL01830. Appendix A Circuit details In this appendix we present the circuits and formal deductions of associated costs for the directives used in this work. These are summarized in Table 2 . Directive Action Reference \textup{PREP}_{\rm amp},\textup{SEL}_{\rm amp} \ket{a}\rightarrow a\ket{a} Lemma 8 \mathtt{SQ} \ket{a}\rightarrow(2a^{2}-1)\ket{a} Lemma 9 \textup{SWAP}_{1\leftrightarrow k} \ket{a_1}\ket{a_2}\cdots\ket{a_K}\rightarrow\ket{a_k}\ket{a_2}\cdots\ket{a_{k-1}}\ket{a_1}\ket{a_{k+1}}\cdots\ket{a_K} – \textup{PREP}_{W} \ket{000}\rightarrow\ket{W}=(\ket{001}+\ket{010}+\ket{100})/\sqrt{3} Ref. 58 and Fig. 16 \mathtt{Abs} \ket{a}\rightarrow\ket{|a|} Lemma 5 \mathtt{AbsDiff} \ket{a}\ket{b}\rightarrow\ket{|a-b|}\ket{b} Lemma 7 \mathtt{Square} \ket{a}\rightarrow\ket{a}\ket{a^2} Lemma 6 of Ref. 84 \mathtt{Sum\ of\ Squares} \ket{a,b,c}\rightarrow\ket{a,b,c}\ket{a^2+b^2+c^2} Lemma 8 of Ref. 84 \mathtt{Mult} \ket{a}\ket{b}\rightarrow\ket{a}\ket{b}\ket{ab} Lemma 10 \mathtt{Sub}[2^{n}] \ket{a}\rightarrow\ket{a-2^n} Fig. 15 of Ref. 7 with adder subunits of Ref. 79 Fig 17b \mathtt{IsEq} \ket{a}\ket{b}\rightarrow\ket{a}\ket{b}\ket{a=b} Proposition 11 \mathtt{cSub}[2^{n+\beta}] \ket{ctl}\ket{a}\rightarrow\ket{ctl}\ket{a-2^{n+ctl\cdot\beta}} Lemma 12 Table 2: Summary of algorithmic directives and associated actions used in this work. Only qubit registers where relevant action of the operator is encoded are shown for clarity. A.1 Swap networks We start by presenting formal theorems for the swap network technique, elucidating how these can be used for building block-encodings recursively. We expect for this generalization to be of general interest when constructing block-encodings of identical operators acting on different registers. A.1.1 One-dimensional swap network Lemma 3 (One-dimensional swap network block-encoding) . Let B\in L(\mathbb{C}^{2^{n}}) and let U_{B} be a unitary that provides an (\alpha_{B},n_{B},\epsilon_{B}) block-encoding with associated Toffoli cost of \mathcal{T}_{B} . Let \bar{B} be a weighted sum of applications of B acting on independent subsystems \bar{B}=\sum_{k=1}^{K}c_{k}\left(\mathbb{I}_{1}\otimes\cdots\otimes\mathbb{I}_{k-1}\otimes B\otimes\mathbb{I}_{k+1}\cdots\otimes\mathbb{I}_{K}\right) (37) and assume access to a subroutine \textup{PREP}(\vec{c})\ket{0}=\sum_{k}\sqrt{|c_{k}|/\alpha_{c}}\ket{k} that can be implemented with associated Toffoli cost of \mathcal{T}_{\vec{c}} , requires n_{c} ancillas in this implementation and has an associated error \epsilon_{c} . The operator \bar{B} then admits an (\alpha_{B}\alpha_{c},n_{B}+n_{c},\alpha_{c}\epsilon_{B}+\alpha_{B}\epsilon_{c}) block-encoding, where \alpha_{c}=\sum_{k}|c_{k}| , with an associated Toffoli cost of 2\mathcal{T}_{\vec{c}}+\mathcal{T}_{B}+2(K-1)(1+n)-4 (38) while using \left\lceil\log_{2}(K-3)\right\rceil temporary carry ancillas. Proof. The (one-dimensional) swap network block-encoding works as a regular linear combination of unitaries (LCU) block-encoding over the c_{k} coefficients, while its SELECT operator corresponds to a conjugation of the block-encoding for B operator with SWAP operations exchanging registers 1 and k . Note that the structure of this operation allows us to freely move the \textrm{PREP}_{B} oracle for the block-encoding of B either as part of the swap network’s PREPARE or SELECT oracle, having that for this part of the proof we consider it a part of PREPARE. Given that we can write \textup{PREP}=\textup{PREP}_{B}\otimes\textup{PREP}(\vec{c}) , where \textup{PREP}(\vec{c}) is a generic prepare circuit for the coefficient vector \vec{c} , the associated 1-norm becomes \alpha_{B}\alpha_{C} , with implementation cost of \mathcal{T}_{\rm PREP}^{(B)}+\mathcal{T}_{\vec{c}} . The SELECT operator then requires one call to the \textup{SEL}_{B} oracle, alongside two calls to a multiplexed \textup{SWAP}_{1\leftrightarrow k} operator. The latter consists of a unary iteration over K-1 indices corresponding to k=2,3,\cdots,K , alongside K-1 swaps of two n_{B} qubit registers (noting that for the k=1 index this operation becomes an identity). The overall cost of SELECT will then be given by 2(K-1)n_{B} Toffolis coming from the swaps and 2(K-3) Toffolis coming from the two (non-controlled) unary iterations each over K-1 indices, adding up to 2(K-1)(n_{B}+1)-4 , while requiring \left\lceil\log_{2}(K-3)\right\rceil temporary carry ancillas coming from the unary iterations, alongside the cost of \textrm{SEL}_{B} . Combining all of these costs together gives the overall Toffoli and ancilla counts shown in this lemma. For completeness Noting that the swap network is effectively a linear combination of block-encodings which all share the same 1-norm \alpha_{B} and error \epsilon_{B} , we can leverage Lemma 16 to recover an upper bound for the swap network error \alpha_{c}\epsilon_{B}+\alpha_{B}\epsilon_{c} . ∎ We note that the multiplexed SWAPs in this routine can also be implemented using no additional ancilla qubits as done in Ref. 53 . However, the overall Toffoli cost of this procedure will be usually higher when the associated number of registers to be swapped is not a power of 2 . Since the ancilla overheads are logarithmic with respect to the number of particles, we here chose to use a unary-iteration-based approach. Note that this swap network block-encoding can also be considered as a generalization of the technique used to block-encode the action of a second-quantized one-electron operator that acts identically on both spin sectors by acting on a single spin register that has been conjugated by swapping of both spin registers 49 . \scriptstyle\left\lceil\log_{2}K\right\rceil \ket{0} \textup{PREP}(\vec{c}) \textup{PREP}(\vec{c}) \ket{k} \scriptstyle n_{B} \scriptstyle\left\lceil\log_{2}K\right\rceil \scriptstyle n \scriptstyle n \scriptstyle n {\lx@inpgf@ignorespaces\vdots} \ket{\vec 0} \ket{k} In(k) In(k) In(k) In(k) \ket{\psi_1} \textup{SWAP}_{1\leftrightarrow k} \textup{SWAP}_{1\leftrightarrow k} B B \textup{SWAP}_{1\leftrightarrow k} \textup{SWAP}_{1\leftrightarrow k} \ket{\psi_2} \ket{\psi_K} Figure 6: PREP (left) and SEL (right) circuits for one-dimensional Swap network block-encoding discussed in Lemma 3 . These LCU oracles block-encode the operator \sum_{k=1}^{K}c_{k}\left(\mathbb{I}_{1}\otimes\cdots\otimes\mathbb{I}_{k-1}\otimes B\otimes\mathbb{I}_{k+1}\cdots\otimes\mathbb{I}_{K}\right) where B is its block-encoding oracle, and \textup{PREP}(\vec{c}) prepares the c_{k} coefficients. The multiplexed SWAP corresponds to a unary iteration 4 over index encoded in \ket{k} , with the associated control over the k -th index swapping all qubits as \ket{\psi_1}\ket{\psi_k}\rightarrow\ket{\psi_k}\ket{\psi_1} . Note that the PREPARE circuit used for block-encoding B could also be included as part of the swap network’s PREPARE instead. A.1.2 Two-dimensional swap network Lemma 4 (Two-dimensional swap network block-encoding) . Let B be an operator that acts on two registers, with an (\alpha_{B},n_{B},\epsilon_{B}) block-encoding with \mathcal{T}_{B} its associated Toffoli cost. Any operator of the form \sum_{j\neq k=1}^{K}C_{jk}B_{jk} (39) consisting of a linear combination of B acting simultaneously on 2 out of K n -qubit registers labelled by j\neq k=1,\cdots,K , namely B_{jk} , then admits an (\alpha_{B}\alpha_{C},n_{B}+n_{C},\alpha_{C}\epsilon_{B}+\alpha_{B}\epsilon_{C}) block-encoding, where \alpha_{C}=\sum_{j\neq k}|C_{jk}| , with an associated cost of 2\mathcal{T}_{C}+\mathcal{T}_{B}+4(K-1)(1+n)-8 (40) Toffolis and using \left\lceil\log_{2}(K-3)\right\rceil temporary carry ancillas. We have assumed access to an oracle \textup{PREP}_{\bm{C}}\ket{0}=\sum_{j\neq k}\sqrt{|C_{jk}|/\alpha_{C}}\ket{j,k} with Toffoli cost of \mathcal{T}_{C} , requiring n_{C} ancillas and with associated error \epsilon_{C} . Proof. The (two-dimensional) swap network block-encoding generalizes the result from the one-dimensional swap network in Lemma 3 . Note that no coefficients corresponding to j=k are prepared in this routine. We now provide a construction for the SELECT circuit (as shown in Fig. 7 ), corresponding to the following steps: 1. Apply the multiplexed \textup{SWAP}_{1\leftrightarrow k} operator on the \ket{k} register, followed by the same operation in the \ket{j} register. This uses 2(K-1)(1+n_{B})-4 Toffolis and \left\lceil\log_{2}(K-3)\right\rceil temporary carry ancillas, noting that these can be shared by both multiplexed swaps. 2. Apply the operator block-encoding B acting on qubit registers 1 and 2 for a cost of \mathcal{T}_{B} . 3. Uncompute step 1 , for a cost of 2(K-1)(1+n_{B})-4 Toffolis. Combining all of these costs together gives the overall Toffoli and ancilla counts shown in this lemma. Just as for the one-dimensional swap network, this block-encoding can be considered as a linear combination of block-encodings, each one with a 1-norm \alpha_{B} and error \epsilon_{B} . Using Lemma 16 for linear combination of block-encodings, the total error \alpha_{C}\epsilon_{B}+\alpha_{B}\epsilon_{C} for the swap network block-encoding is obtained. ∎ \scriptstyle n_{B} \scriptstyle\left\lceil\log_{2}K\right\rceil \scriptstyle\left\lceil\log_{2}K\right\rceil \scriptstyle B \scriptstyle n \scriptstyle n {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} \ket{\vec 0} \ket{j} In(j) In(j) In(j) In(j) \ket{k} In(k) In(k) In(k) In(k) \ket{\psi_1} \textup{SWAP}_{1\leftrightarrow j} \textup{SWAP}_{1\leftrightarrow j} \textup{SWAP}_{2\leftrightarrow k} \textup{SWAP}_{2\leftrightarrow k} \hat{B} \hat{B} \textup{SWAP}_{2\leftrightarrow k} \textup{SWAP}_{2\leftrightarrow k} \textup{SWAP}_{1\leftrightarrow j} \textup{SWAP}_{1\leftrightarrow j} \ket{\psi_2} \ket{\psi_K} Figure 7: SEL circuit for two-dimensional swap network block-encoding discussed in Lemma 4 . A.1.3 Swap network with controlled phases For completeness we here detail the implementation for the swap network with controlled phases shown in Fig. 4 . We show the detailed circuit in Fig. 8 . The basic idea is to implement the (-1) phase for electronic charges in the Coulomb interaction by adding a Pauli Z gate on the lowermost qubit during the unary iteration sawtooth expansion if the associated index being carried by that branch corresponds to an electron. See Ref. 4 for a more detailed description on the sawtooth expansion and unary iteration. Since this phase should only be added for the swap network coming for the potential term, the Z gate is controlled on the qubit encoding the control between potential and kinetic energy terms used for block-encoding the full Hamiltonian. Adding the controlled action of electronic phases (-1)^{\sigma} can thus be done by simply adding controlled Z gates to a regular unary iteration circuit for no additional non-Clifford cost. \scriptstyle n \scriptstyle 3n_{g}\eta \ket{T/V} Z^{\sigma_{i}} Z^{\sigma_{i}} \ket{i} In(i) In(i) \ket{\bm q} \text{SWAP}_{1\leftrightarrow i} \text{SWAP}_{1\leftrightarrow i} = \scriptstyle 3n_{g}\eta {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } \ket{T/V} \ket{\bar i_{0}} \ket{\bar i_{1}} \ket{\bar i_{n-1}} Z Z Z Z Z Z \ket{\bm q} \text{SWAP}_{1\leftrightarrow\eta_{n}} \text{SWAP}_{1\leftrightarrow\eta_{n}} \text{SWAP}_{1\leftrightarrow\eta_{n}+1} \text{SWAP}_{1\leftrightarrow\eta_{n}+1} \text{SWAP}_{1\leftrightarrow\eta_{n}+2} \text{SWAP}_{1\leftrightarrow\eta_{n}+2} \text{SWAP}_{1\leftrightarrow\eta_{n}+3} \text{SWAP}_{1\leftrightarrow\eta_{n}+3} Figure 8: Implementation of swap network with controlled phases from Fig. 4 . SWAP operations marked with 1\leftrightarrow n perform a SWAP between all the qubits of registers \ket{\vec q_1} and \ket{\vec q_n} encoding the system’s wavefunction, thus consisting of 3n_{g} SWAPs. Note how operations for electronic indices (i>\eta_{n}) include a controlled Z in the sawtooth expansion implementing the (-1) phases, while those for nuclear indices i\leq\eta_{n} perform the standard unary iteration. A.2 Absolute value We now show how to obtain the absolute value of some signed integer \ket{a} in the two’s complement representation. This corresponds to the operation \mathtt{Abs}\ket{a}\ket{0}=\ket{|a|}\ket{\textrm{sign}(a)}, (41) where one additional qubit is required for making this operation reversible, effectively storing the value of the sign. The circuit for this operation is shown in Fig. 9 , with its costs being summarized via a brief constructive proof in the following lemma. Lemma 5 (Absolute value in Two’s Complement Representation) . The \mathtt{Abs} unitary acting on a n -qubit register \ket{a} as described above can be implemented with n-1 Toffoli gates, 1 ancilla, and n-2 temporary carry qubits. Proof. We now present the steps required for implementing this operation, as shown in Fig. 9 . To understand how this works, we note that in general the n -bit integer a from the two’s complement representation, with associated bits \{\bar{a}_{i}\}_{i=0}^{n-1} , is encoded as a=\sum_{i=0}^{n-2}\bar{a}_{i}2^{i}-\bar{a}_{n-1}2^{n-1} . In the case where this is a negative number, namely when the sign bit \bar{a}_{n-1}=1 , its absolute value corresponds to |a|=2^{n-1}-\sum_{i=0}^{n-2}\bar{a}_{i}2^{i} . 1. Initialize an additional ancilla qubit, copying the sign of the \ket{a} register with a CNOT. 2. Controlled on this ancilla qubit, flip all qubits encoding the \ket{a} state. The qubit previously encoding the sign of a will always be returned to 0 after this operation. In the case where this flip occurs, the remaining n-1 qubits will correspond to their one’s complement, namely (2^{n-1}-1)-\sum_{i=0}^{n-2}\bar{a}_{i}2^{i}=|a|-1 . 3. If the ancilla qubit carrying the sign information is 1 , then add 1 to the (n-1) -qubit register, thus encoding the value of |a| . The qubit that had been returned to 0 can be used to store the overflow from this operation, associated with the case where we are adding 1 to the \ket{11\cdots 1} (n-1) -qubit state, which was produced for the most negative number a=-2^{n-1} . This is done by performing an addition of the ancilla qubit on the n -qubit register, requiring n-1 Toffolis and n-2 temporary carry ancillas 23 . One less temporary carry ancilla was needed here since we can directly use the n th qubit entering as 0 instead. Note that these operations will act as identity for the case where the input number is positive, with the ancilla qubit being returned as 0 : the first n-1 qubits from the \ket{a} register are here already encoding the absolute value \ket{|a|} . For the case of a negative integer, the above shows how the absolute value is returned by adding 1 to the one’s complement of the first n-1 bits. ∎ \scriptstyle n-1 \ket{0} \hskip 17.07182pt\mathtt{Abs}\hskip 17.07182pt \hskip 17.07182pt\mathtt{Abs}\hskip 17.07182pt \ket{a} 0 \textrm{sign}(a) a |a| = \scriptstyle n-1 \ket{0} \hskip 14.22636pt\mathtt{Add}\hskip 22.76228pt \hskip 14.22636pt\mathtt{Add}\hskip 22.76228pt \ket{\textrm{sign}(a)} \ket{a} \ket{|a|} a a b a+b Figure 9: Circuit for in-place calculation of absolute value. CNOT gate on multi-qubit register corresponds to applying a CNOT on each of the register’s qubits. Bottom qubit for \ket{a} input corresponds to sign qubit from two’s complement representation. Note how it only becomes 1 in the output for overflow case of most negative number a=-2^{n-1} . A.3 Absolute value of difference We now show the circuit for calculating in-place the absolute value between the difference between two signed integers q and s encoded in two associated n -bit registers in the two’s complement representation. This translates to performing the following operation: \mathtt{AbsDiff}\ket{a}\ket{b}\ket{0}=\ket{|a-b|}\ket{b}\ket{\textrm{sign}(a-b)}, (42) where we note that this operation requires one additional qubit that needs to be passed to its adjoint operation for uncomputation, besides temporary carry ancillas. A notable feature of this operation is that when computing the absolute value of the difference of two n -bit signed two’s complement integers, storing the absolute (unsigned) value of their difference can be achieved in n bits. This is proven in the following proposition. Proposition 6 . Let a and b be signed n -bit integers represented by two’s complement. If an unsigned representation is used to represent c=|a-b| , then only n bits are needed to exactly represent c , even when accounting for overflow. Proof. In two’s complement, a,b\in[-2^{n-1},2^{n-1}-1] . Taking the extremal values for their difference we get \min(a-b)=-2^{n}+1 and \max(a-b)=2^{n}-1 . So |a-b|\in[0,2^{n}-1] . This means that a-b can be encoded in two’s complement representation using n+1 bits, while its absolute value is encoded in an unsigned representation with n bits (ignoring the leading sign bit which is guaranteed to be 0 as a-b can never attain the most negative value -2^{n} ). ∎ \scriptstyle n \scriptstyle n \ket{0} \hskip 28.45274pt\mathtt{AbsDiff}\hskip 28.45274pt \hskip 28.45274pt\mathtt{AbsDiff}\hskip 28.45274pt \ket{a} \ket{b} 0 \textrm{sign}(a-b) a |a-b| b b = \scriptstyle n \scriptstyle n \ket{0} \hskip 22.76228pt\mathtt{Abs}\hskip 22.76228pt \hskip 22.76228pt\mathtt{Abs}\hskip 22.76228pt \ket{\textrm{sign}(a-b)} \ket{a} \hskip 22.76228pt\mathtt{Sub}\hskip 22.76228pt \hskip 22.76228pt\mathtt{Sub}\hskip 22.76228pt \ket{|a-b|} \ket{0} \ket{0} \ket{b} \ket{b} 0 \textrm{sign}(a) a a-b a |a| b b Figure 10: Circuit for computing the absolute value of the difference of two two’s complement registers, as discussed in Lemma 7 . For notational simplicity we here considered the single qubit register coming out of the subtraction operation to be carrying the sign information of the associated (n+1) -qubit register encoding a-b . The operation marked as \mathtt{Abs} computes the absolute value of a two’s complement register (see Lemma 5 ). Note that as proved in Proposition 6 , the overflow qubit from the absolute value routine will always be returned in 0 state, which we consider a temporary carry ancilla and do not explicitly include on the \mathtt{AbsDiff} routine on the left. The implementation of this \mathtt{AbsDiff} operation is presented via a brief constructive proof in the following lemma. Lemma 7 . The \mathtt{AbsDiff} unitary acting on two n -qubit registers \ket{a}\ket{b} as described above can be implemented with 2n Toffoli gates, 1 ancilla, and n+1 temporary carry qubits. Proof. We now present the steps required for implementing this operation, as shown in Fig. 10 . 1. Perform in-place subtraction of \ket{a} in the \ket{b} register, while initializing one ancilla to account for overflow. This uses n Toffolis, n temporary carry qubits, and 1 ancilla qubit to store the overflow. 2. Perform in-place operation for obtaining absolute value ( Lemma 5 ) over the (n+1) -qubit register encoding a-b . The Toffoli cost of this operation is n , while requiring n temporary carry ancillas and one additional ancilla. Note that after this operation, as show in Proposition 6 , the qubit used for overflow in the (n+1) -qubit register (corresponding to the overflow qubit for the absolute value routine) will always be returned to 0 , which can thus instead be considered as a temporary carry ancilla for the \mathtt{AbsDiff} routine. ∎ Note that this can easily be repeated over other Cartesian components with the carry qubits being reused when implementing the \mathtt{AbsDiff}^{\otimes 3} operation in Fig. 2 . A.4 Squaring block-encoding We now discuss how to implement the block-encoding for the squaring operation \ket{a}\rightarrow a^{2}\ket{a} . We first present how to block-encode the amplitude of a two’s complement register, namely \ket{a}\rightarrow a\ket{a} . Although this operation could be used twice in a row to implement the square, we here present a qubitization-based implementation which instead implements \ket{a}\rightarrow T_{2}(a)\ket{a}=(2a^{2}-1)\ket{a} , effectively reducing the 1-norm by a factor of 2 while introducing a constant shift that can be generally neglected. A.4.1 Amplitude encoding We start by presenting how to block-encode the amplitude \ket{a}\rightarrow a\ket{a} , with the two associated oracles \textup{PREP}_{\rm amp} and \textup{SEL}_{\rm amp} ( Figs. 11 and 12 ). We here consider for the integer a to be encoded using n bits in the two’s complement encoding, with its amplitude being expressed as a=\sum_{b=0}^{n-2}\bar{a}_{b}2^{b}-\bar{a}_{n-1}2^{n-1} , where \bar{a}_{i}\in\{0,1\} is the i th bit used for encoding a . To understand how our block-encoding works, we first consider an unsigned (n-1) -bit integer c . We then exploit a property of its one’s complement c^{*} , namely the associated value we obtain by flipping the values of all of its bits ( \bar{c}_{i}=0(1)\leftrightarrow\bar{c}_{i}^{*}=1(0) ): c=\sum_{b=0}^{n-2}\bar{c}_{i}2^{b}=2^{n-1}-1-\sum_{b=0}^{n-2}\bar{c}_{i}^{*}2^{b}=2^{n-1}-c^{*}-1. (43) This property is particularly useful as it allows for the calculation of the absolute amplitude of a two’s complement integer. To better understand how this works, consider the two following cases: 1. The integer a\geq 0 , meaning its sign qubit is 0 . In this case, the first n-1 qubits can be considered as an unsigned (n-1) -qubit representation of a positive integer already. 2. The integer a<0 . In this case, it follows from Eq. ( 43 ) that |a| can be recovered by doing the one’s complement of the first n-1 qubits, obtaining the associated amplitude, and adding 1 . The basic idea for performing this block-encoding is to encode the bit-wise amplitudes through the state \ket{\sqrt{\mathtt{amp}_n}}:=\frac{1}{2^{(n-1)/2}}\left(\ket{0}^{n-1}\ket{1}_{s}+\sum_{b=0}^{n-2}2^{b/2}X_{b}\ket{0}\ket{0}_{s}\right), (44) where X_{b} is a Pauli X acting on qubit b , having that this can be thought as a one-hot encoding for the amplitudes of the first n-1 bits. Each of these amplitudes is then added constructively (or cancelled destructively) if the associated bit in \ket{a} is 1 (or 0 ). This can be achieved by using an alternating sign register with a single qubit, namely a qubit which is prepared in the \ket{+} state and on which we act with identity (or a Pauli Z) for having constructive (destructive) interference. The n th bit, which corresponds to the sign qubit in the two’s complement representation, will then be used to control the three following operations: flip to one’s complement representation over first n-1 qubits, addition of +1 value for negative sign branch (encoded through \ket{\cdot}_{s} qubit), and global multiplication by -1 for case where amplitude is negative. We now formally describe this operation and associated costs. Lemma 8 (Controlled Amplitude Block-Encoding in Two’s Complement Representation) . For a given n -qubit register encoding a signed integer \ket{a} in two’s complement encoding, there exists a (2^{n-1},n+1,0) block encoding O_{\rm amp} of the controlled operator that encodes its amplitude a\ket{a} using 4n-3 (45) Toffoli gates and 2 temporary carry qubits. Proof. This proof is carried out by constructing the PREPARE and SELECT oracles, as illustrated in Figs. 11 and 12 . We now start by describing the PREPARE routine, which corresponds to the operation \textup{PREP}_{\rm amp}\ket{0}=\ket{+}\ket{\sqrt{\mathtt{amp}_n}}. (46) We now provide a detailed explanation of how this is implemented. First we show how to prepare \ket{\sqrt{\mathtt{amp}_n}} following the strategy in Ref. 84 , and then show how an associated LCU block-encodes the amplitude of a in the two’s complement representation. Preparation of \ket{\sqrt{\mathtt{amp}_n}} involves a series of cascading controlled Hadamard gates, each controlled on the previous single qubit state. This procedure iteratively halves the amplitude on the prior quantum state, effectively yielding the desired amplitudes over b th bits in the target (n-1) -qubit register. The preparation of this state works as follows: \displaystyle\ket{0}^{n-1}\xrightarrow{\mathtt{Had}_{0}} \displaystyle\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{0}^{n-2} (47) \displaystyle\xrightarrow{\text{ctrl}_{0}:\mathtt{Had}_{1}} \displaystyle\left(\frac{1}{\sqrt{2}}\ket{00}+\frac{1}{2}\ket{1}(\ket{0}+\ket{1})\right)\ket{0}^{n-3} (48) \displaystyle\xrightarrow{\text{ctrl}_{1}:\mathtt{Had}_{2}} \displaystyle\left(\frac{1}{\sqrt{2}}\ket{000}+\frac{1}{2}\ket{100}+\frac{1}{2\sqrt{2}}\ket{11}(\ket{0}+\ket{1})\right)\ket{0}^{n-4} (49) \displaystyle\xrightarrow{\text{ctrl}_{2}:\mathtt{Had}_{3}} \displaystyle\left(2^{-1/2}\ket{0000}+2^{-2/2}\ket{1000}+2^{-3/2}\ket{1100}+2^{-4/2}\ket{111}(\ket{0}+\ket{1})\right)\ket{0}^{n-5} (50) \displaystyle\xrightarrow{\>\>...\>\>} \displaystyle\sum_{b=0}^{n-2}2^{-(b+1)/2}\ket{1}^{b}\ket{0}^{n-2-b}, (51) where the last line above can be obtained by completing the cascading controlled Hadamards. Interpreting the state as a unary encoding we effectively have the state \sum_{b=0}^{n-2}2^{-(b+1)/2}\ket{b}+2^{-(n-1)/2}\ket{1}^{n-2}(\ket{0}+\ket{1}) where the endianness is chosen such that \ket{1}=\ket{1000...} , \ket{2}=\ket{1100...} and so on. This normalized state can be re-written 2^{-(n-1)/2}\left(\sum_{b=0}^{n-3}2^{(n-b-1)/2}\ket{b}+\ket{1}^{n-2}(\ket{0}+\ket{1})\right). (52) Note that ordering of the amplitudes is opposite what we desire such that the smallest unary encoded integer appears with the greatest amplitude. To give yield the complementary encoding, we flip all of the bits to obtain \displaystyle 2^{-(n-1)/2}\left(\sum_{b=0}^{n-3}2^{(b+1)/2}\ket{0}^{n-b-3}\ket{1}^{b+2}+\ket{0}^{n-2}(\ket{0}+\ket{1})\right) (53) Next, we use an additional qubit \ket{\cdot}_{s} to flag for the all-zeros state. Noting that this is the only state for which the last qubit is in 0 , this can be simply done by applying an open-controlled NOT on this last qubit, obtaining the state \displaystyle 2^{-(n-1)/2}\left(\sum_{b=0}^{n-3}2^{(b+1)/2}\ket{0}^{n-b-3}\ket{1}^{b+2}\ket{0}_{s}+\ket{0}^{n-2}(\ket{0}\ket{1}_{s}+\ket{1}\ket{0}_{s})\right). (54) Next, to avoid checking multiple bits per operation, we desire a one-hot encoding. This can be achieved by applying a cascade of CNOTs such that they act on the k th qubit and are controlled on the (k-1) th like so: \rm{ctrl}_{k-1}:X_{k} . This sequence starts with k=n , and progresses by decreasing k by 1, i.e. start on the final qubit pair in the sequence \rm{ctrl}_{n-1}:X_{n} and progress to the last (not considering the \ket{\cdot}_{s} register). This yields the state: \displaystyle 2^{-(n-1)/2}\left(\sum_{b=0}^{n-3}2^{(b+1)/2}\ket{0}^{n-b-3}\ket{1}\ket{0}^{b+1}\ket{0}_{s}+\ket{0}^{n-2}(\ket{0}\ket{1}_{s}+\ket{1}\ket{0}_{s})\right) (55) \displaystyle= \displaystyle 2^{-(n-1)/2}\left(\sum_{b=0}^{n-2}2^{b/2}\ket{0}^{n-b-2}\ket{1}\ket{0}^{b}\ket{0}_{s}+\ket{0}^{n-1}\ket{1}_{s}\right) (56) \displaystyle= \displaystyle 2^{-(n-1)/2}\left(\sum_{b=0}^{n-2}2^{b/2}\ket{b}\ket{0}_{s}+\ket{0}^{n-1}\ket{1}_{s}\right):=\ket{\sqrt{\mathtt{amp}_n}}, (57) where in the last line, we reverse the endianness of the register to obtain our one-hot encoding. Here \ket{0}=\ket{...0001} , \ket{1}=\ket{...0010} , \ket{2}=\ket{...0100} and so on. Zero is interpreted in this way since it is associated to the amplitude 2^{0} and needs to be included in the subsequent control logic, while the all-zeros state flagged by \ket{1}_{s} will be used for adding the +1 amplitude for the case where we are in the negative branch of the sign qubit. Finally, we note that our PREPARE circuit will use one additional qubit in an equal superposition, namely \ket{+}=\mathtt{Had}\ket{0} for performing destructive interference through a Z gate and cancelling amplitudes associated with a bit-value of 0 . Considering the fact that each controlled Hadamard gate can be implemented with a single Toffoli (see Fig. 17 from Ref. 40 ), and that these are the only non-Clifford operations in this procedure, this PREPARE oracle can then be implemented using n-2 Toffoli gates. The associated 1-norm directly corresponds to 2^{n-1} . Having presented how to implement the PREPARE operation, we now detail the operations of SELECT and derive the total cost of the block-encoding. 1. Apply a Z gate on the sign bit of the incoming n qubit register \ket{a} . This operation will give an overall phase of -1 for negative values, which in tandem with the subsequent implementation of the absolute amplitude |a| will return the signed amplitude a . 2. Controlled on the sign bit of the incoming n qubit register \ket{a} , compute the one’s complement of the other n-1 qubits in-place. This can be done by applying a CNOT on each of the n-1 qubits controlled on the sign bit for no Toffoli cost. 3. Controlled on \ket{b} copy the b -th bit of the state in the top register into an ancilla “flag” qubit. Since \ket{b} is one-hot encoded, this can be done with a Toffoli applied to each single qubit register for a cost of n-1 Toffolis. 4. For each bit of the state which has a value of 0 , cancel the associated amplitude by applying a Z gate on the \ket{+} register. This can be done by implementing a Z on the \ket{+} register that is controlled on the flag qubit being 0 . Note that this operation should also be controlled on the “global” control qubit for the entire block-encoding, for a total cost of 1 Toffoli gate. 5. Controlled on the \ket{\cdot}_{s} qubit flagging the all-zeros state, namely \ket{1}_{s} , cancel the amplitude for the case where the integer a is positive. Note that the previous operations will already have effectively implemented a Z gate on the \ket{+} register. This operation needs to be undone a is a negative number. This can be done by implementing a Toffoli gate on the \ket{+} register, controlled on the sign qubit of \ket{a} being 1 and the all-zeros flag being 1. Controlling this operation with the global control can be done by adding one logical AND operation, increasing the cost to 2 Toffolis and using one temporary carry ancilla. 6. Uncompute steps 2 and 3, returning the flag qubit to the \ket{0} state and the \ket{a} register to its regular two’s complement encoding. This step requires n-1 Toffoli gates. 7. Collecting the costs, this controlled operation requires 2\times(n-1)+3=2n+1 Toffoli gates and 2 temporary carry ancillas. Summing the costs of one call to PREPARE, one call to its hermitian conjugate, and one call to SELECT, we recover the costs outlined in this lemma. ∎ \scriptstyle n \ket{0} \mathtt{amp_{n}} \mathtt{amp_{n}} \ket{\sqrt{\mathtt{amp_n}}} = {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } \ket{0}^{n-1} \mathtt{Had} \mathtt{Had} X X \ket{b} \mathtt{Had} \mathtt{Had} X X \mathtt{Had} \mathtt{Had} X X \mathtt{Had} \mathtt{Had} X X \ket{0} \ket{s} \scriptstyle n \ket{0} \textrm{PREP}_{\rm amp} \textrm{PREP}_{\rm amp} \ket{\sqrt{\mathtt{amp_n}}} \ket{0} \ket{h} = \scriptstyle n-1 \ket{0} \mathtt{amp_{n}} \mathtt{amp_{n}} \ket{b} \ket{0} \ket{s} \ket{0} \mathtt{Had} \mathtt{Had} \ket{h} Figure 11: Preparation of \ket{\sqrt{\mathtt{amp_n}}} state (top), and implementation of \textrm{PREP}_{\rm amp} for block-encoding of amplitude \ket{a}\rightarrow a\ket{a} ( Lemma 8 ). \scriptstyle n \scriptstyle n {\lx@inpgf@ignorespaces b} {\lx@inpgf@ignorespaces b} \ket{b} \ket{0} \ket{a} = {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\ \cdots\ } {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\ \cdots\ } \ket{\bar b_0} \ket{\bar b_1} \ket{\bar b_{n-1}} \ket{0} \ket{\bar{a}_0} \ket{\bar{a}_1} \ket{\bar{a}_{n-1}} \scriptstyle n-1 \scriptstyle n \ket{ctl} \ket{s} s s \ket{b} b b \ket{h} h h \ket{a} \textrm{SEL}_{\rm amp} \textrm{SEL}_{\rm amp} = \scriptstyle n-1 \scriptstyle n-1 {\lx@inpgf@ignorespaces b} {\lx@inpgf@ignorespaces b} {\lx@inpgf@ignorespaces b} {\lx@inpgf@ignorespaces b} \ket{ctl} \ket{s} \ket{b} \ket{h} Z Z Z Z \ket{0} \ket{0} \ket{\bar a_{n-1}} Z Z \ket{\bar a_{0},\cdots,\bar a_{n-2}} Figure 12: Implementation of Toffoli cascade (top) and controlled \textrm{SEL}_{\rm amp} (bottom) routines for controlled block-encoding of amplitude \ket{a}\rightarrow a\ket{a} , as discussed in Lemma 8 . A.4.2 Walk-based implementation We now present an implementation of the squaring operation that uses a qubitization approach to implement it as a second degree Chebyshev polynomial \ket{a}\rightarrow T_{2}(a)\ket{a}=(2a^{2}-1)\ket{a} . The benefit of this approach is that it reduces the 1-norm by a factor of 2, since it implements \ket{a}\rightarrow 2a^{2}\ket{a} up to a constant shift. This improvement comes from effectively shifting the spectrum with a constant as [0,a_{\rm max}^{2}]\rightarrow[-a^{2}_{\rm max}/2,a^{2}_{\rm max}/2] . This operation is built by using the block-encoding oracles for the amplitude encoding \ket{a}\rightarrow a\ket{a} from Lemma 8 , which are then used to build an associated qubitized walk operator 52 ; 45 and applied two times, recovering the target Chebyshev polynomial. Lemma 9 (Walk-based Controlled Block Encoding of Square in Two’s Complement Representation) . Given an n -qubit register encoding a signed integer \ket{a} in the two’s complement encoding, there exists a (2^{2(n-1)},n+1,0) block-encoding of the controlled operator that computes T_{2}(a)\ket{a}=(2a^{2}-1)\ket{a} using 10n-6\in\mathcal{O}(n) (58) Toffoli gates and n-1 temporary carry qubits. Proof. Using the PREPARE and SELECT oracles presented in Lemma 8 implementing O_{\rm amp}\ket{a}\rightarrow a\ket{a} , it follows immediately from the qubitized walk operator construction 52 ; 45 that the construction in Fig. 13 block-encodes the second-degree Chebyshev polynomial \ket{a}\rightarrow T_{2}(a)\ket{a}=(2a^{2}-1)\ket{a} . The costs for this procedure then become twice the Toffoli costs from the block-encoding O_{\rm abs} (i.e. 2\times(4n-3) ), plus the cost of the reflection logic for building the walk operator, corresponding to two (separate) multi-controlled Z each over n+1 control qubits (where each can be implemented via temporary ANDs using n-1 temporary carry qubits and n Toffolis). Note that the temporary carry qubits for is dictated by those coming from the temporary ANDs, namely n-1 . Adding up the Toffoli counts, we recover the costs shown in this lemma. ∎ \scriptstyle n+1 \scriptstyle n \ket{ctl} \ket{\cdot}_{\rm BE} \ket{a} \mathtt{SQ} \mathtt{SQ} = \scriptstyle n+1 \scriptstyle n \ket{ctl} Z Z Z Z \ket{\cdot}_{\rm BE} \textup{PREP}_{\rm abs} \textup{PREP}_{\rm abs} \textup{PREP}_{\rm abs}^{\dagger} \textup{PREP}_{\rm abs}^{\dagger} \textup{PREP}_{\rm abs} \textup{PREP}_{\rm abs} \textup{PREP}_{\rm abs}^{\dagger} \textup{PREP}_{\rm abs}^{\dagger} \ket{a} \textup{SEL}_{\rm abs} \textup{SEL}_{\rm abs} \textup{SEL}_{\rm abs} \textup{SEL}_{\rm abs} Figure 13: Walk-based implementation for controlled block-encoding of square, up to a constant shift (see Lemma 9 ). Block-encoding register \ket{\cdot}_{\rm BE} encodes \ket{s}\ket{b}\ket{h} registers for block-encoding amplitude from Fig. 11 . A.5 Improved multiplication We now discuss our improved approach for out-of-place multiplication of two positive integers, which acts as \mathtt{Mult}\ket{a}\ket{b}\ket{0}=\ket{a}\ket{b}\ket{ab}. (59) One of the most expensive parts of block-encoding the potential operator V using the methods in this work is the multiplication step that occurs in the inequality test. This is because we are required to compute \mathtt{Mult}\ket{r^2}\ket{m^2}\ket{0}=\ket{r^2}\ket{m^2}\ket{r^2m^2}, and the \ket{m^2} register is particularly large due to the fact that many qubits are used to perform the calculation of the inverse root to high precision. Optimizing this multiplication routine therefore becomes a key interest. The cost of so called schoolbook multiplication that is often cited is 2n_{a}n_{b} Toffoli gates for the operation described above. This comes from the general procedure of performing multiplications as a series of controlled additions, and a controlled addition requires an extra Toffoli per qubit control qubit, hence the factor of 2. Optimized asymptotic schemes based on Karatsuba multiplication also exist 70 ; 24 , however, these only become advantageous for very large bitstrings. Litinski recently improved the scaling of quantum schoolbook multiplication by performing a series of add-subtract operations with corrections to remove the controlled adders, eliminating the factor of 2 47 . Here, we slightly improve the constants stemming from said corrections by performing an initial copy operation. This is detailed in the Lemma 10 . Lemma 10 (Faster Integer Multiplication) . Let a,\>b\in\mathbb{N} encoded in n_{a} and n_{b} qubits respectfully, then assuming n_{a}\text{choose $c=1$} (65) \displaystyle 2ab+(2^{2n_{a}}+2b)-2^{n_{a}}(a+1-a_{0})-2^{n_{a}}(a+1). (66) By choosing c=1 we have copied the b with CNOTs into the output register such that b_{0} is in the 2^{1} position. Now we have a very similar equation to that obtained by Litinski, and need to apply the like corrections to obtain ab . Adding 2^{n_{a}}(a+1-a_{0}) can be done by similarly applying an adder with carry-in set to 1, and applying a CNOT on the carry-in controlled on a_{0} . This controls whether we add 2^{n_{a}}a or 2^{n_{a}}(a+1) as in Ref. 47 . This addition is done on the n_{b}-n_{a}+1 high bits of the output, costing n_{a}+1 Toffolis. Next we add 2^{n_{a}}(b+1) using an adder (again with the carry-in set to 1) on the n_{b}+1 high bits of the output, costing n_{b}+1 Toffoli. Next, subtract (2^{2n_{a}}+2b) . First, using the fact that 2^{2n_{a}} has Hamming weight 1, we subtract only on the n_{a}+n_{b}+1-2n_{a} high bits of the string, using n_{b}-n_{a}+1 Toffoli. Then we subtract 2b on all but the bottom bit using n_{a}+n_{b} Toffoli. The remaining 2ab can then be divided by 2 using bit shifts with no non-Clifford cost, yielding the final cost result. The ancilla come from the largest necessary subtraction/addition, which is done in the final correction, plus an overflow qubit. ∎ Despite this minor speedup, the n^{2} term cannot be improved asymptotically for schoolbook multiplication, and it seems unlikely that a prefactor of 1 can be improved upon (given that the Hamming weights of the strings is unknown), simply due to the number of logical manipulations that need be carried out. Therefore, further improvements would likely only further improve upon the linear constant. One minor limitation of the result is that the output register needs to be initialized in the all zero state, where as the construction by Litinski in principle allows one to add the product ab directly into a 2n bit-string \textup{mod}\>2^{n+1} . For our purposes, the following operation is subtraction by a classical constant with Hamming weight one, so this in place addition of the product does not lead to space-time savings. A.6 Equality check The equality check circuit [ Fig. 14 ] uses one qubit to flag whether the values in two registers of the same size are the same, namely \mathtt{IsEq}\ket{a}\ket{b}\ket{0}=\ket{a}\ket{b}\ket{a=b}, (68) where we have defined \ket{a=b}=\begin{cases}\ket{0},&\textrm{if }a\neq b\\ \ket{1},&\textrm{if }a=b.\end{cases} (69) We detail the cost of this operation in Proposition 11 . While this is not necessarily a novel contribution, we provide detailed costs of this operation for readability and completeness. Proposition 11 (Equality Check) . Given two n -bit strings stored in the registers \ket{a} and \ket{b} , it is possible to check whether a=b using n-1 Toffoli gates and temporary carry qubits, and a single ancilla bit to store \ket{a=b} . Proof. First check if a=b by applying a CNOT controlled on each bit of \ket{a} with target on each associated bit of \ket{b} . Then, via temporary AND, check if b is the all zero state with n-1 Toffoli and store the result in an ancilla qubit, un-computing temporary ancilla with measurement and Clifford operations as done with the Gidney adder 23 . ∎ \scriptstyle n \scriptstyle n \ket{a} a a \ket{b} b b \ket{0} \mathtt{IsEq} \mathtt{IsEq} = {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ddots} {\lx@inpgf@ignorespaces\iddots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } {\lx@inpgf@ignorespaces\ \ldots\ } \ket{\bar{a}_{0}} \ket{\bar{a}_{0}} \ket{\bar{a}_{1}} \ket{\bar{a}_{1}} \ket{\bar{a}_{n-1}} \ket{\bar{a}_{n-1}} \ket{\bar{b}_{0}} \ket{\bar{b}_{0}} \ket{\bar{b}_{1}} \ket{\bar{b}_{1}} \ket{\bar{b}_{n-1}} \ket{\bar{b}_{n-1}} \ket{0} \ket{a=b} Figure 14: Circuit implementation of equality check routine discussed in Proposition 11 . A.7 Controlled classical subtraction circuit In this section we show how to add a number that stores both classical and quantum information to a quantum register. The motivation for this comes from saturating the potential in Section III . This involves modifying the inequality test such that we are required to subtract by a different classical number depending on a quantum control. This can trivially be done by using a QROM-like strategy and loading the classical number in a quantum register, but for large numbers, this can be qubit intensive. Here we show how this can be achieved (under certain conditions) without ever loading the classical number at all. We first prove our construction for a more general case than necessary in our algorithm in Lemma 12 , provide an example circuit construction in Fig. 15 , and then explain how it applies to our inequality test. Figure 15: Circuit implementation of the adder leveraged in the proof of Lemma 12 . Lemma 12 (In-place addition of controlled power of 2) . Given Q\in\mathbb{N} encoded in q quantum bits, a classical number C\in\mathbb{N} encoded in c\leq q bits, and a quantum control bit \beta\in\{0,1\} , then it is possible to compute the addition Q+C+\beta[(-1)^{c_{j}}2^{c_{j}}+(-1)^{c_{k}}2^{c_{k}}] using q-1 Toffoli gates, q-2 temporary carry qubits, and 3 ancilla qubits; 1 to store the overflow and 2 needed to encode the classical constant C , specifically the bits c_{j} and c_{k} whose values are dictated by the single qubit quantum control register \ket{\beta} . Proof. Considering first the qubit counts, observing the example circuit in Fig. 15 it is clear that only the bits of C controlled by \beta need a quantum encoding, specifically those of c_{j} and c_{k} , and one quantum bit is needed to store overflow. Then the rest of C is encoded via classical controls and q additional bits are required to store Q . The circuit works by replacing quantum adder units with classical adder subunits introduced in Fig. 17 of Ref. 79 . It is clear from the example that under the lemma conditions this can be done for a bit-string of arbitrary length. In terms of the gate cost, 1 Toffoli comes from each adder unit with the exception of the first one (whereby we have effectively assumed j\neq k\neq 0 ). ∎ Note that the control register \ket{\beta} changes the Hamming weight of C by at most the number of registers it acts on, which in the case above is 2. This circuit can be further generalized to cases where the quantum control performs more intricate manipulations to the classical constant at the price of encoding more bits in quantum registers. We now explain how this can be used in our algorithm. The circuit in Fig. 15 can clearly be used as a subtractor, similarly as shown in the circuit of Figs. 13 and 15 of Ref. 7 , all components of the adder can be reversed to be used as a subtractor circuit (with the exception of the overflow carry-out logic that remains unchanged). In the inequality test of Fig. 2 where we have added a control for modifying the saturation of nuclear-nuclear interactions (see Appendix E ), we are required to check r^{2}m^{2}-2^{2n_{M}+n_{\Gamma}}<0 . The key here is to notice that 2^{2n_{M}} is a Hamming weight 1 bitstring, whereby the location of the bit can be swapped/shifted by n_{\Gamma} bits with a single Toffoli gate. These properties allow 2^{2n_{M}+n_{\Gamma}} to be written in the form C+n_{\Gamma}[(-1)^{c_{j}}2^{c_{j}}+(-1)^{c_{k}}2^{c_{k}}] from Lemma 12 , where in our case, all but one of c_{j}=2n_{M} or c_{k}=2n_{M}+n_{\Gamma} are zero, making much of the classical control logic in Fig. 15 unnecessary. A.8 State preparation circuits In this section we discuss how to implement all PREP circuits appearing in the main text. Before showing these circuits, it is useful to present a lemma summarizing the cost of implementing rotations with some target accuracy using a phase kickback register. Lemma 13 (Single qubit rotation using phase kickback register) . Any single qubit rotation operator, namely R_{x} , R_{y} , or R_{z} , can be implemented with \epsilon_{rot} accuracy by using a phase gradient register consisting of at least n_{R}(\epsilon_{R})=\left\lceil\log_{2}\frac{\pi}{\epsilon_{R}}\right\rceil (70) qubits, with an associated Toffoli cost of \mathcal{T}_{R}(\epsilon_{R})=n_{R}(\epsilon_{R}). (71) Proof. We start by noting that all rotation operators are equivalent to e.g. R_{z} under a Clifford transformation, having that all will then have the same Toffoli cost. Considering that this rotation is implemented with Toffoli gates by using a controlled classical adder on an n_{R} -qubit phase kickback register, the associated angle is then implemented with an accuracy of \delta_{R}=2\pi/2^{n_{R}} , from which we can bound the accuracy for the R_{z} rotation as \epsilon_{R}\leq\delta_{R}/2 using the fact that \delta_{R}\ll 1 67 ; 80 . It follows immediately that by choosing the n_{R}(\epsilon_{R}) considered in this lemma, the overall accuracy for the rotation will be upper bounded by \epsilon_{R} . The Toffoli cost of this operation then corresponds to the cost of doing one controlled adder on n_{R} qubits, with a Toffoli cost of n_{R} . ∎ A.8.1 W state preparation The \textup{PREP}_{W} circuit shown in Fig. 3 corresponds to the preparation of the \ket{W} state, which is defined as \ket{W}=(\ket{001}+\ket{010}+\ket{100})/\sqrt{3}. (72) The corresponding circuit is shown in Fig. 16 , with the cost costs being summarized in the following lemma. Lemma 14 (W state preparation) . The W state in Eq. ( 72 ) can be prepared to \epsilon_{W} accuracy by using \mathcal{T}_{W}(\epsilon_{W})=\left\lceil\log_{2}\frac{\pi}{\epsilon_{W}}\right\rceil+1 (73) Toffoli gates, assuming we have access to an appropriate phase gradient state. Proof. We start by considering how the the only error in this operation comes from a single gate, namely R_{y} . Using the triangle inequality, it follows immediately that the error in this operation ( \epsilon_{W} ) can be upper bounded by the error in implementing R_{y} . Using Lemma 13 for implementing this R_{y} using a phase gradient register with \left\lceil\log_{2}\pi/\epsilon_{W}\right\rceil qubits, it follows immediately that an accuracy of \epsilon_{W} is achieved. The only other non-Clifford gate in this operation corresponds to a controlled Hadamard, which can be implemented for one Toffoli gate. Combining this cost with that of the rotation, we obtain the cost outlined in this lemma. The right action of this circuit follows immediately after the action of R_{y}(2\arccos 1/\sqrt{3})\ket{0}=(\ket{0}+\sqrt{2}\ket{1})/\sqrt{3} after propagating through the rest of the circuit. ∎ \ket{0} \textup{PREP}_{W} \textup{PREP}_{W} \ket{0} \ket{0} = \ket{0} R_{y}\left(2\arccos\frac{1}{\sqrt{3}}\right) R_{y}\left(2\arccos\frac{1}{\sqrt{3}}\right) X X \ket{W} \ket{0} H H \ket{0} Figure 16: Circuit preparing the \ket{W}=(\ket{001}+\ket{010}+\ket{100})/\sqrt{3} state. A.8.2 Controlled coherent alias sampling with flagging We show how to implement the controlled version of the coherent alias sampling routine from Ref. 4 , which can be used for preparing a state for arbitrary coefficients. These controlled versions of the coherent alias sampling circuits have been presented in Ref. 49 , however they are missing a minor correction for ensuring that the “junk” registers are also returned on an all-zeros state for the case where the control qubit is not activated. We also consider a general case where a flag is added to the returned states, namely for a target coefficient vector (c_{1},\cdots,c_{K}) with associated 1-norm \lambda_{\vec{c}}=\sum_{k}|c_{k}| , we return the state \textup{PREP}^{(n_{F})}(\vec{c})=\frac{1}{\sqrt{\lambda_{\vec{c}}}}\sum_{k}\sqrt{|c_{k}|}\ket{k}\ket{\vec b_k}\ket{\textrm{temp}(k)}, (74) for \vec{b}_{k} a binary vector of length n_{F} . The controlled implementation of this operation is presented in Fig. 17 , with the following lemma summarizing its costs. Lemma 15 (Generic state preparation with flagging) . Consider a coefficient vector \vec{c}=(c_{1},\cdots,c_{K}) with associated 1-norm \lambda_{\vec{c}}:=\sum_{k}|c_{k}| , and some number n_{F}\geq 0 corresponding to the length of binary flags to include (with n_{F}=0 corresponding to adding no flags). Implementing the operation outlined in Eq. ( 74 ) to accuracy \epsilon can be implemented with a Toffoli cost of \mathcal{T}_{\vec{c}}(\epsilon)=b_{K}+n_{F}+2l_{K}+\mathcal{Q}(K,b)+2\mathcal{T}_{R}(\epsilon/4)+\aleph+[l_{K}+k_{K}+\aleph+1] (75) using n_{c}=b_{K}+n_{F} qubits, \tilde{n}_{c}=b_{K}+2\aleph+n_{F}+1 “junk’ ’ ancillas that need to be passed for uncomputation, and \tilde{n}_{c}=\max\{l_{K}-1+[1],n(K,b),\aleph-1\} (76) temporary carry ancillas. Here we have defined \mathcal{Q}(K,b) and n(K,b) as the Toffoli and temporary carry qubits cost of loading K bitstrings of length b=2n_{F}+\aleph+\left\lceil\log_{2}K\right\rceil (which could be done with a QROM using \mathcal{Q}(K,b)=K-1 and n(K,b)=\left\lceil\log_{2}(K)\right\rceil-1 ), noting that there are approaches for reducing the Toffoli count in exchange for using more qubits. We have also defined b_{K}:=\left\lceil\log_{2}K\right\rceil , \displaystyle k_{K}=\max_{k\in\mathbb{N}}\{k\ :\ K/2^{k}\in\mathbb{N}\} the largest power of 2 dividing K , l_{K}=\left\lceil\log_{2}(K/2^{k_{K}})\right\rceil , and \displaystyle\aleph=\left\lceil\log_{2}\frac{2}{K\epsilon}\right\rceil . Numbers in brackets correspond to modifications when this operation is controlled. Proof. The action of this circuit is completely analogous to that from the original coherent alias sampling implementation of Ref. 4 , while having that the flagging procedure is a straightforward generalization from the one-qubit flags introduced in Refs. 7 ; 49 . We start by noting that the error from this operation will come from two components: first, the approximation of the angle for the R_{z} rotation inside of the UNIFORM routine, and second the discretization error from using \aleph qubits for the keep register. Using the triangle inequality, it follows immediately that by allocating an error of \epsilon/2 to each of these will yield an overall accuracy for our procedure which is upper bounded by \epsilon , having that each R_{z} rotation is then implemented to \epsilon/4 accuracy. We note that tighter error estimates could yield better bounds. However, the logarithmic dependence would make the associated resources extremely similar to those presented here. Using Eq.(35) from Ref. 4 , we can make the error on each of the loaded coefficients \rho_{k}:=\sqrt{|c_{k}|/\lambda_{\vec{c}}} smaller than \epsilon/2 by choosing \displaystyle\aleph=\left\lceil\log_{2}\frac{2}{K\epsilon}\right\rceil . We now start by deducing the costs for the uncontrolled version of this routine. We now show the costs for each part of this routine: 1. One [controlled] call to UNIFORM (K) , requiring 2l_{K}+2\mathcal{T}_{R}(\epsilon/2)+[l_{K}+k_{K}+1] Toffolis and l_{K}-1+[1] temporary carry ancillas, where \mathcal{T}_{R}(\epsilon/2) is the associated cost of performing an R_{z} rotation (see Lemma 13 ). 2. One [controlled] call to \aleph Hadamard gates, requiring [\aleph] Toffoli gates. 3. One data loading routine over K coefficients with data length b_{K}+\aleph+2n_{F} , with \mathcal{Q}(K,n_{b}) Toffoli cost and requiring n(K,b_{K}+\aleph+2n_{F}) temporary carry ancillas. 4. One call to a comparison circuit between two \aleph bit registers, which can be done as a subtraction 7 requiring \aleph Toffolis and \aleph-1 temporary carry ancillas and one ancilla for storing the result. 5. One [open controlled] series of NOT gates for no Toffoli cost. 6. A series of b_{K}+n_{F} controlled SWAPs, requiring b_{K}+n_{F} Toffolis. Combination of these steps returns the costs outlined in this lemma. ∎ \scriptstyle\left\lceil\log_{2}K\right\rceil \scriptstyle\left\lceil\log_{2}K\right\rceil \scriptstyle\aleph \scriptstyle\aleph \scriptstyle n_{F} \scriptstyle n_{F} \ket{ctl} \ket{\vec 0} \textrm{UNIFORM}(K) \textrm{UNIFORM}(K) In(k) In(k) \ket{\vec 0} \textrm{data : alt}_{k} \textrm{data : alt}_{k} \vec{X}(s=0) \vec{X}(s=0) \ket{k} \ket{\vec 0} H^{\otimes{\aleph}} H^{\otimes{\aleph}} a a \ket{\vec 0} \textrm{data : keep}_{k} \textrm{data : keep}_{k} b b \ket{0} \mathtt{Comp}(a\leq b) \mathtt{Comp}(a\leq b) \ket{0} \textrm{data : }\vec{b}_{k} \textrm{data : }\vec{b}_{k} \ket{\vec b_{k}} \ket{0} \textrm{data : alt}_{\vec{b}_{k}} \textrm{data : alt}_{\vec{b}_{k}} Figure 17: Controlled coherent alias sampling circuit with n_{F} flagging qubits. A.8.3 Alias sampling for symmetric matrices We now show an extension of the coherent alias sampling PREPARE circuit 4 ; 49 that loads data corresponding to a two-dimensional symmetric matrix. This circuit exploits the fact that for a \bm{C} matrix with dimensions K\times K , not all K^{2} coefficients need to be loaded, saving some costs on the QROM of the coherent alias sampling routine, following the ideas from the sparse data loading routine in Ref. 7 . The associated action of this circuit with F flags then corresponds to \textup{PREP}^{(F)}(\bm{C})\ket{\vec 0}=\sum_{j,k=1}^{K}\sqrt{\frac{|C_{jk}|}{\lambda_{c}}}\ket{j}\ket{k}\ket{\textrm{junk}(j,k)}\bigotimes_{f=1}^{F}\ket{b^{(f)}_{jk}}, (77) where b_{jk}^{(f)} is a binary variable flagging some property of interest associated with coefficients j,k and we have defined the 1-norm \lambda_{C}=\sum_{j,k=1}^{K}|C_{jk}|. (78) The associated circuit is presented in Fig. 18 , which closely follows the implementation of the regular coherent alias sampling routine from Lemma 15 with two key additions: utilization of an additional register for only loading unique non-zero coefficients, as done for sparse data loading 7 , and swapping of registers encoding j,k coefficients in the end for recovering a symmetric matrix. Note that as mentioned in Refs. 7 ; 49 , the data to be loaded by the register encoding S non-zero coefficients will run through at most K(K+1)/2 coefficients as only the upper-diagonal is required to fully specify a symmetric matrix. Defining a bijection s\leftrightarrow(j_{s},k_{s}) , the coefficients to be loaded then become the non-zero entries of C_{s}=\begin{cases}\sqrt{2}C_{j_{s}k_{s}}&\text{if}\>j_{s}j_{s}=k_{s}\\ 0&\text{otherwise}.\end{cases} (79) \scriptstyle\left\lceil\log_{2}S\right\rceil \scriptstyle 2\left\lceil\log_{2}K\right\rceil \scriptstyle\aleph \scriptstyle 2\left\lceil\log_{2}K\right\rceil \scriptstyle\aleph \scriptstyle n_{F} \scriptstyle n_{F} \ket{ctl} \ket{\vec 0} \textrm{UNIFORM}(S) \textrm{UNIFORM}(S) In(s) In(s) \ket{\vec 0} \textrm{data : }(j,k)_{s} \textrm{data : }(j,k)_{s} \vec{X}(s=0) \vec{X}(s=0) \textrm{SWAP}_{j\leftrightarrow k} \textrm{SWAP}_{j\leftrightarrow k} \ket{jk} \ket{\vec 0} H^{\otimes{\mu}} H^{\otimes{\mu}} a a \ket{\vec 0} \textrm{data : alt}(j,k)_{s} \textrm{data : alt}(j,k)_{s} \ket{\vec 0} \textrm{data : keep}_{s} \textrm{data : keep}_{s} b b \ket{0} \mathtt{Comp}(a\leq b) \mathtt{Comp}(a\leq b) \ket{0} \textrm{data : }\vec{b}_{s} \textrm{data : }\vec{b}_{s} \ket{\vec b_{jk}} \ket{0} \textrm{data : alt}_{\vec{b},s} \textrm{data : alt}_{\vec{b},s} \ket{0} H H Figure 18: Circuit for loading positive symmetric matrix \bm{C}\in\mathbb{R}^{K\times K} with S unique non-zero coefficients and n_{F} flagging registers. The \vec{X}(s=0) routine here corresponds to a series of X gates which reset the registers to the all-zeros state for the case where the control qubit is not activated. \mathtt{Comp} routine compares two qubit registers of the same size and flags the result in an additional qubit 9 , while the SWAP over j\leftrightarrow k swaps qubits from register encoding index j with those of index k , consisting \left\lceil\log_{2}K\right\rceil controlled SWAPs. A.8.4 Amplitude-amplified alias sampling We now show how to implement the state preparation routine which acts as \displaystyle\textup{PREP}_{V,\Gamma}\ket{0}\ket{0} \displaystyle=\frac{1}{\sqrt{\lambda_{V}(\Gamma)}}\sum_{i\neq j}^{\eta}\sqrt{\gamma_{\Gamma}(i,j)}\ket{i}\ket{j} (80) \displaystyle:=\ket{\zeta_{target}(\Gamma)} (81) where we consider \displaystyle\gamma_{\Gamma}(i,j)=\begin{cases}\frac{\zeta_{i}\zeta_{j}}{\Gamma},&\textrm{ if particle }i\textrm{ and }j\textrm{ are both nuclei },\\[8.0pt] \zeta_{i}\zeta_{j}&\textrm{ otherwise },\end{cases} (82) and have defined the 1-norm \lambda_{V}(\Gamma)=\sum_{i\neq j}\gamma_{\Gamma}(i,j). (83) Note that we here have made the dependence with respect to the nuclear-nuclear factor \Gamma\geq 1 explicit as to make this discussion general for both oracles \textup{PREP}_{V} and \textup{PREP}_{V,\Gamma} presented in the main text, having that the former will correspond to choosing \Gamma=1 . We start by considering a product state consisting of two separate alias sampling routines, each one preparing a coefficient vector (\zeta_{1},\zeta_{2},\cdots,\zeta_{\eta}) , associated with the state \displaystyle\ket{\zeta_{prod}} \displaystyle:=\left(\textup{PREP}(\vec{\zeta})\ket{0}\right)\otimes\left(\textup{PREP}(\vec{\zeta})\ket{0}\right) (84) \displaystyle=\frac{1}{\lambda_{\zeta}}\left(\sum_{i}\sqrt{\zeta_{i}}\ket{i}\right)\otimes\left(\sum_{j}\sqrt{\zeta_{j}}\ket{j}\right), (85) where we have defined \lambda_{\zeta}=\sum_{i}\zeta_{i} . The idea of this approach is to use amplitude amplification 12 as to recover the target state in Eq. 80 . Each of the coherent alias sampling routines \textup{PREP}(\vec{\zeta}) has a Toffoli cost \mathcal{T}_{\vec{\zeta}}\in\mathcal{O}(\eta) (see Lemma 15 ). Below we show that for most chemical reactions a single call to amplitude amplification is sufficient for obtaining the target state with a success probability of 1 , making the overall cost of our state preparation routine 6\mathcal{T}_{\vec{\zeta}}+\mathcal{O}(1)\in\mathcal{O}(\eta) : one call to amplitude amplification requires 3 calls to the associated oracle, with each oracle here requiring 2 calls to \textup{PREP}(\vec{\zeta}) . Deducing the number of calls to amplitude amplification can be done by calculating the associated success probability \displaystyle P(\Gamma,\vec{\zeta}) \displaystyle:=|\langle\zeta_{target}(\Gamma)|\zeta_{prod}\rangle|^{2} (86) \displaystyle=\frac{1}{\lambda_{\zeta}^{2}\lambda_{V}(\Gamma)}\left(\sum_{i\neq j}\sqrt{\zeta_{i}\zeta_{j}\gamma_{\Gamma}(i,j)}\right)^{2} (87) \displaystyle\geq\frac{\lambda_{V}(\Gamma)}{\lambda_{\zeta}^{2}}. (88) Defining \mathcal{M} as the set of electron-nuclear and electron-electron interactions and noting that this overlap will be minimized in the \Gamma\rightarrow\infty limit, we get to \displaystyle P(\Gamma,\vec{\zeta}) \displaystyle\geq\frac{\sum_{i,j\in\mathcal{M}}\zeta_{i}\zeta_{j}}{\left(\sum_{i}\zeta_{i}\right)^{2}} (89) \displaystyle=\frac{2\eta_{e}Z_{tot}+\eta_{e}(\eta_{e}-1)}{Z_{tot}^{2}+2\eta_{e}Z_{tot}+\eta_{e}^{2}}, (90) where we have defined the total nuclear charge Z_{tot}=\sum_{i\in nuc}\zeta_{i} . Since for chemical reactions we can generally consider for the net charge to be close to zero, we can replace Z_{tot}\approx\eta_{e} , arriving to \displaystyle P(\Gamma,\vec{\zeta}) \displaystyle\gtrsim\frac{3}{4}-\frac{1}{4\eta_{e}}\geq\frac{1}{2}, (91) where we have considered to have at least one electron in the simulation for the last inequality. Overall, this shows that the success probability is greater than 1/4 , from which a single round of amplitude amplification will suffice to obtain the target state deterministically (Theorem 4 from Ref. 12 ). The associated circuit is presented in Fig. 19 , which acts as follows: 1. Apply the coherent alias sampling technique associated with the coefficients (\zeta_{1},\cdots,\zeta_{\eta}) in two separate registers. One flagging qubit is used in these routines to mark whether the associated index corresponds to a nuclei or an electron. This can be done for almost the same cost \mathcal{T}_{\vec{\zeta}} of implementing the controlled generic alias sampling state preparation, requiring one additional Toffoli gate and two extra qubits 49 . 2. Apply an R_{y} gate with a rotation angle encoding the success probability P(\Gamma,\zeta) controlled on both coefficient registers encoding a nuclear index. This can be done with a cost of \mathcal{T}_{R}+1 Toffolis using one additional qubit to encode whether both indices are nuclear \ket{i,j\in\mathcal{N}} , where \mathcal{T}_{R} is the Toffoli cost of implementing a controlled rotation. 3. Perform an equality test ( Proposition 11 ) over the registers encoding the particle indices, flagging the result in one additional qubit \ket{i=j} . This routine requires n_{\eta}-1 Toffoli gates and temporary carry qubits, where we have defined n_{\eta}:=\left\lceil\log_{2}\eta\right\rceil . 4. Controlled on the equality test qubit \ket{i=j} from step 3 being false and the rotation angle qubit from step 2, flag an additional qubit for the overall success of the state preparation routine, using an additional qubit and one Toffoli gate. 5. Steps 1-4 constitute the oracle \mathcal{A} for a Grover iteration. This oracle will be called a total of three times for doing one round of amplitude amplification, which as discussed in Theorem 4 of Ref. 12 will return the target state with certainty by choosing adequate rotation angles in between applications of \mathcal{A} and \mathcal{A}^{\dagger} . The rotation around the successful application can be done with a single R_{z} gate on the qubit flagged in step 4 for \mathcal{T}_{R} cost. The rotation around the initial state requires an R_{z} gate controlled over 2n_{\eta}+8 qubits, requiring 2n_{\eta}+7 temporary carry ancillas and 2n_{\eta}+7+\mathcal{T}_{R} Toffoli gates. Overall, this routine has a total Toffoli cost of \displaystyle\mathcal{T}_{{\rm PREP}_{V}} \displaystyle=3\cdot(2(\mathcal{T}_{\vec{\zeta}}+1)+(\mathcal{T}_{R}+1)+(n_{\eta}-1)+1)+2n_{\eta}+7+2\mathcal{T}_{R} (92) \displaystyle=6\mathcal{T}_{\vec{\zeta}}+2n_{\eta}+16+5\mathcal{T}_{R}. (93) \mathcal{A} \ket{ctl} R_{z}\left(\varphi\right) R_{z}\left(\varphi\right) \ket{0} \textup{PREP}(\vec{\zeta}) \textup{PREP}(\vec{\zeta}) i i \mathcal{A}^{\dagger} \mathcal{A}^{\dagger} \mathcal{A} \mathcal{A} \ket{i} \ket{0} \ket{i\in nuc} \ket{0} \textup{PREP}(\vec{\zeta}) \textup{PREP}(\vec{\zeta}) j j \ket{j} \ket{0} \ket{j\in nuc} \ket{0} \mathtt{IsEq} \mathtt{IsEq} \ket{i=j} \ket{0} \ket{i,j\in\mathcal{N}} \ket{0} R_{y}\left(\theta\right) R_{y}\left(\theta\right) \ket{0} R_{z}\left(\phi\right) R_{z}\left(\phi\right) X X \ket{0} Figure 19: Controlled \textup{PREP}_{V}(\Gamma,\vec{\zeta}) circuit implementing operation in Eq. 80 using one round of amplitude amplification. \textup{PREP}(\vec{\zeta}) routines correspond to controlled coherent alias sampling with one flag qubit marking whether i index corresponds to a nuclear term, as shown in Fig. 7 of Ref. 49 . \mathtt{IsEq} routine is shown in Proposition 11 , flagging the ancilla qubit if indices i and j are equal. Rotation angles \theta,\phi and \varphi are determined by overlap P(\Gamma,\vec{\zeta}) defined in Eq. 86 . Logic inside of \mathcal{A} operation in yellow rectangle following application of PREPs flags successful preparation of \ket{\zeta_{target}(\Gamma)} with \ket{1}_{succ} qubit, which is then used to rotate the Grover iterate for performing amplitude amplification 12 . Appendix B Cost and error analysis In this appendix we show how the action of our circuits correctly implements the associated operations, while also analyzing the total error from these operations. We start by showing the action of our circuits for block-encoding V and T while deducing associated costs and errors, building up to proving Theorem 1 which outlines the cost of block-encoding the molecular Coulomb Hamiltonian. We note that we generally consider arithmetic routines to be implemented without any error. Before showing the action of our operators, it is useful to establish some general notation, as well as a general theorem for linear combinations of block-encodings. Let’s first consider the block-encoding error of an operator A . We here use the notation \tilde{A} to indicate an imperfect construction of the operator. For example, we say \widetilde{O}_{A} imperfectly block-encodes the operator A up to accuracy \epsilon_{A} if \|\alpha_{A}(\bra{0}^{m_{i}}\otimes\mathbb{I})\widetilde{O}_{A}(\ket{0}^{m_{i}}\otimes\mathbb{I})-A\|\leq\epsilon_{A}. (94) Following the notation of Ref. 25 , we call this a (\alpha_{A},n_{A},\epsilon_{A}) block-encoding of the operator A . In the context of LCU , n_{A} would be the number of qubits used to represent the PREPARE register. We also use the notation of an (\beta,Q,\epsilon) state preparation pair (P_{L},P_{R}) to denote a PREPARE unitary P_{L} and its associated uncomputation P_{R} (noting that often P_{R}=P_{L}^{\dagger}) that prepare a state with coefficients encoded in Q qubits given by \vec{y} with a 1-norm of \beta=\sum_{j}|y_{j}| such that the sum of errors over coefficients \sum_{j}|y_{j}-\beta\tilde{y}_{j}/\tilde{\beta}|\leq\epsilon , where \tilde{y}_{j} are the effective coefficients being implemented and \tilde{\beta} their associated 1-norm. We now present a lemma summarizing how to block-encode a linear combination of block-encodings. Lemma 52 of Ref. 25 provides the means for analyzing a linear combination of block-encoded operators, however, under the assumption that all block-encodings in the linear combination have the same parameters (\alpha,Q,\epsilon) . We provide a minor generalization in the following lemma and then leverage it to conclude the block-encoding parameters of our Hamiltonian from this algorithm. Lemma 16 (Linear combination of distinct block-encodings (generalization of (Lemma 52, Ref. 25 )) . Let A=\sum_{j=0}^{m-1}y_{j}A_{j} be an s -qubit operator. Suppose (P_{L},P_{R}) is an (\beta,Q,\epsilon_{y}) state preparation pair for the vector \vec{y}\in\mathbb{C}^{m} . If \forall\>j\in\{0,...,m-1\} we have O_{j} an (\alpha_{j},Q_{j},\epsilon_{j}) block-encoding of A_{j} , and \textup{SEL}_{A}=\sum_{j=0}^{m-1}\outerproduct{j}{j}\otimes\mathbb{I}_{(a-a_{j})}\otimes O_{j}+\left(({\mathbb{I}}-\sum_{j=0}^{m-1}\outerproduct{j}{j})\otimes{\mathbb{I}}_{i}\otimes{\mathbb{I}}_{s}\right), where Q_{J}:=\max_{j}Q_{j} , and \alpha:=\sum_{j}\alpha_{j} , then we can construct an (\alpha\beta,Q+Q_{J},\epsilon_{j}\max_{j}\alpha_{j}+\beta\max_{j}\epsilon_{j}) block-encoding of A with one query to each of P_{L} , P_{R} , and \textup{SEL}_{A} . Proof. Observe that \tilde{O}_{A}:=(P_{L}^{\dagger}\otimes{1}_{i}\otimes{1}_{s})\textup{SEL}(P_{R}\otimes{1}_{i}\otimes{1}_{s}) is a (\alpha\beta,Q+Q_{J},\epsilon_{j}\max_{j}\alpha_{j}+\beta\max_{j}\epsilon_{j}) block-encoding of A : \displaystyle\left\|A-\alpha\beta(\bra{0}^{Q}\otimes\bra{0}^{Q_{J}}\otimes\mathbb{I})\tilde{O}_{A}(\ket{0}^{Q}\otimes\ket{0}^{Q_{J}}\otimes{\mathbb{I}})\right\| (95) \displaystyle=\left\|A-\sum_{j=0}^{m-1}\beta\frac{\tilde{y}_{j}}{\tilde{\beta}}\alpha_{j}\left((\bra{0}^{Q_{J}}\otimes{\mathbb{I}})({\mathbb{I}}_{({Q_{J}}-Q_{j})}\otimes\tilde{O}_{j})(\ket{0}^{Q_{J}}\otimes{\mathbb{I}})\right)\right\| (96) \displaystyle\leq\sum_{j=0}^{m-1}\left|\beta\frac{\tilde{y}_{j}}{\tilde{\beta}}-y_{j}\right|\alpha_{j}+\left\|A-\sum_{j=0}^{m-1}y_{j}\alpha_{j}\left((\bra{0}^{Q_{J}}\otimes{\mathbb{I}})({\mathbb{I}}_{({Q_{J}}-Q_{j})}\otimes\tilde{O}_{j})(\ket{0}^{Q_{J}}\otimes{\mathbb{I}})\right)\right\| (97) \displaystyle\leq\sum_{j=0}^{m-1}\left|\beta\frac{\tilde{y}_{j}}{\tilde{\beta}}-y_{j}\right|\alpha_{j}+\sum_{j=0}^{m-1}y_{j}\left\|A_{j}-\alpha_{j}\left((\bra{0}^{Q_{J}}\otimes{\mathbb{I}})({\mathbb{I}}_{({Q_{J}}-Q_{j})}\otimes\tilde{O}_{j})(\ket{0}^{Q_{J}}\otimes{\mathbb{I}})\right)\right\| (98) \displaystyle=\underbrace{\sum_{j=0}^{m-1}\left|\beta\frac{\tilde{y}_{j}}{\tilde{\beta}}-y_{j}\right|}_{\epsilon_{y}}\alpha_{j}+\sum_{j=0}^{m-1}y_{j}\epsilon_{j} (99) \displaystyle\leq\epsilon_{y}\max_{j}\alpha_{j}+\beta\max_{j}\epsilon_{j}. (100) Here \tilde{\beta} is an imperfect normalization factor, and the {\mathbb{I}}_{(Q_{J}-Q_{j})} term is to “pad” the operators requiring less than Q_{J} qubits to block-encode, therefore this ensures consistent dimensionality. ∎ Note that when the block-encoding parameters are chosen to be identical, we recover the result of Lemma 52 up to a factor of \alpha in the second term. We believe this to be an erratum in Ref 25 , given that the error as stated is a sum of terms with different units. The way that the block-encoding error is defined therein is to have units of \alpha so a term in an error bound derived from a sum of such operators cannot have a term that is a product \alpha\epsilon unless the block-encoding error is defined in terms of the normalized operator A/\alpha , which it is not as stated. In addition, also defined in Ref. 25 is the notion of a state-prep-pair, which loosely speaking is a pair of unitaries that prepare a normalized state with arbitrary coefficients. We leverage this construction throughout the analysis where we define errors in terms of the coefficients as done in the lemma above. For example, for a state that encodes reciprocal mass coefficients, we define \epsilon_{m}=\sum_{j=1}^{\eta}\left|\lambda_{T}\frac{\tilde{m}_{j}^{-1}}{\tilde{\lambda}_{T}}-m_{j}\right| , and this error is then passed into and propagated through our prepare routines in the form of discretization and rotation errors. B.1 Block-encoding V We now start by showing how the circuit in Fig. 2 effectively block-encodes the saturated Coulomb interaction [Eq. ( 9 )] corresponding to 1/2r , alongside the incurred error in this operation coming from the alternating sign discretization. Lemma 17 (Alternating sign implementation of controlled Coulomb interaction) . The construction in Fig. 2 corresponding to an alternating sign trick encoding of \|\vec{q}_{1}-\vec{q}_{2}\|^{-1} effectively block-encodes the controlled saturated Coulomb interaction in Eq. ( 9 ) using n_{M} ancillas with a 1-norm of \alpha_{M}=\frac{1}{2\Delta}, (101) while using \mathcal{T}_{M}=2n_{M}^{2}+8n_{M}n_{g}+16n_{M}+6n_{g}^{2}+16n_{g}+8 (102) Toffolis, \tilde{n}_{M}=n_{g}+4+\max\{3n_{g}^{2},\;4n_{M}+5n_{g}+6\} (103) temporary carry ancillas, and incurring an error \epsilon_{M}\leq\frac{3}{2M\Delta}. (104) Proof. The construction in Fig. 2 clearly corresponds to an LCU which is a uniform superposition of the unitaries U_{m} summing over all the values of m=0,\cdots,M-1 , having that the \mathtt{Had}^{\otimes n_{M}} operation done on the \ket{m} register effectively implements the PREPARE circuit corresponding to a uniform superposition over M unitaries, where each unitary then has an associated weight of 1/M . Here we defined M:=2^{n_{M}} . The action from the arithmetic part of the circuit trivially encodes the result of the inequality test m^{2}\|\vec{q}_{1}-\vec{q}_{2}\|^{2}0)} \displaystyle=\left|\frac{1}{2r}-\frac{1}{2M\Delta}\sum_{m=0}^{M-1}u_{m}(q)\right| (106) \displaystyle=\frac{1}{2}\left|\frac{1}{q\Delta}-\frac{1}{M\Delta}\left(\sum_{m=0}^{\left\lfloor\frac{M}{q}\right\rfloor}(1)+\sum_{m=\left\lceil\frac{M}{q}\right\rceil}^{M-1}(-1)^{m}\right)\right| (107) \displaystyle=\frac{1}{2}\left|\frac{1}{q\Delta}-\frac{1}{M\Delta}\left(\left\lfloor\frac{M}{q}\right\rfloor+1+\sum_{m=\left\lceil\frac{M}{q}\right\rceil}^{M-1}(-1)^{m}\right)\right| (108) \displaystyle\leq\frac{1}{2M\Delta}\left|\frac{M}{q}-\left\lfloor\frac{M}{q}\right\rfloor+2\right| (109) \displaystyle\leq\frac{3}{2M\Delta}. (110) Here we have used the fact that m^{2}q^{2}n_{g}+1 (noting that in this work n_{g}\leq 9 and n_{M}\geq 23 in all systems), the Toffoli cost is 4n_{M}(n_{g}+1)+4n_{M}+2(n_{g}+1)+3=4n_{M}n_{g}+8n_{M}+2n_{g}+5 , while requiring 2(n_{g}+n_{M}+1) ancillas for storing the result and 2n_{M}+2n_{g}+3 temporary carry ancillas. The qubit overhead is \tilde{n}_{M}^{(5)}=4n_{g}+2n_{M}+7+(2n_{M}+2n_{g}+3) . 6. One \mathtt{Sub} routine by a classical constant M^{2}=2^{2n_{M}} with Hamming weight one (in bit 2n_{M} ) from a (2n_{M}+2n_{g}+2) -qubit register. This can be done by combining the inequality test routine in Fig. 15 of Ref. 7 with the adder subunits of Fig. 17b from Ref. 79 , with an associated cost of 2n_{g}+1 Toffolis, one additional ancilla for carrying the inequality test result, and 2n_{g}-1 temporary carry qubits. Note that these carry qubits are kept alive for uncomputing this operation with measurement and phase for no Toffoli cost. The qubit overhead is \tilde{n}_{M}^{(6)}=4n_{g}+2n_{M}+8+(2n_{g}-1) . 7. Application of a CCZ gate for one Toffoli cost, with the same qubit overhead as in step 6 (considering how carry qubits from subtraction are kept alive for uncomputation). 8. Uncomputation of steps 1-7, which effectively doubles the Toffoli costs from steps 2-6 (noting that step 7 is uncomputed for no Toffoli cost). This requires 6n_{g}+3n_{g}^{2}-n_{g}-1+n^{2}_{m}-2+4n_{M}n_{g}+8n_{M}+2n_{g}+5=n_{M}^{2}+4n_{M}n_{g}+8n_{M}+3n_{g}^{2}+7n_{g}+3 Toffolis. After step 8, all ancillas used in steps 2-7 are returned to 0 . The number of temporary carry ancillas used overall thus becomes \tilde{n}_{M}=\max_{i}\tilde{n}_{M}^{(i)} , which will generally be given by either step 3 or 5: \displaystyle\tilde{n}_{M} \displaystyle=\max\{3n^{2}_{g}+n_{g}+4;4n_{M}+6n_{g}+10\} (117) \displaystyle=n_{g}+4+\max\{3n_{g}^{2},4n_{M}+5n_{g}+6\}, (118) while the total number of Toffolis is twice the cost reported in step 8, plus the costs from steps 6 and 7: \displaystyle\mathcal{T}_{M} \displaystyle=2\times(n_{M}^{2}+4n_{M}n_{g}+8n_{M}+3n_{g}^{2}+7n_{g}+3)+2n_{g}+1+1 (119) \displaystyle=2n_{M}^{2}+8n_{M}n_{g}+16n_{M}+6n_{g}^{2}+16n_{g}+8, (120) concluding this proof. ∎ Initially, the factor of 3/2 in the bound on \epsilon_{M} seems peculiar. The reason for this is due to the subtlety that the \ket{m} state produced by applying \mathtt{Had}^{\otimes n_{M}}\ket{\vec{0}} produces a superposition over stings m\in\{0,M-1\} , whereas the inequality test is defined in terms of M , not M-1 . Therefore, when m=0 amplitude is always added, leading to over counting by a grid point for boundary cases as a trade-off for cheaper arithmetic. Lemma 18 (Controlled block-encoding of potential energy) . Block-encoding of the controlled potential energy operator V in Eq. ( 8 ) can be done using \mathcal{T}_{V}=2\mathcal{T}_{\textrm{PREP}_{V}}+4(\eta-1)(1+3n_{g})-8+\mathcal{T}_{M} (121) Toffolis, with a 1-norm of \alpha_{V}=\frac{\lambda_{V}}{2\Delta}, (122) using n_{V}=n_{M}+2\left\lceil\log_{2}\eta\right\rceil (123) block-encoding qubits, \tilde{n}_{V}=\tilde{n}_{M}+\tilde{n}_{\textup{PREP}_{V}} (124) temporary carry ancillas, and incurring an error of \epsilon_{V}\leq\frac{\epsilon_{\zeta}}{2\Delta}+\frac{3\lambda_{V}}{2^{n_{M}+1}\Delta}. (125) Here we have defined \mathcal{T}_{\textup{PREP}_{V}}\in\tilde{\mathcal{O}}(\sqrt{\eta}) as the cost of loading the \sum_{i\neq j}\sqrt{\zeta_{i}\zeta_{j}}\ket{i,j} state with 1-norm \lambda_{V}:=\sum_{i\neq j}\zeta_{i}\zeta_{j} , which corresponds to the cheapest routine between the amplitude-amplified approach ( Section A.8.4 ) and coherent alias sampling for symmetric matrices ( Section A.8.3 ), requiring an associated number of temporary qubits that need to be passed for uncomputation \tilde{n}_{\textup{PREP}_{V}} and incurring a maximum error \epsilon_{\zeta} per coefficient. \mathcal{T}_{M} is the Toffoli count for the alternating sign block-encoding in Lemma 17 . Proof. The numbers from this lemma follow immediately from combining the two-dimensional swap network technique in Lemma 4 with the alternating sign block-encoding for the saturated Coulomb potential in Lemma 17 , considering that in this case K=\eta , n=3n_{g} , n_{B}=n_{M} , n_{c}=2\left\lceil\log_{2}\eta\right\rceil . Note that the swap network with controlled phases is used here ( Fig. 8 ), which has the same Toffoli and qubit requirements as its regular version. Finally, note that the temporary carry ancillas required for the multiplexed swaps in the unary iteration can be generally taken from the temporary carry ancillas \tilde{n}_{M} , from which they do not have to be considered in this cost. ∎ We now present the costs for the optimized approach with variable saturation \Gamma . Lemma 19 (Controlled block-encoding of potential energy with optimized saturation) . The controlled block-encoding of the potential energy operator V in Eq. ( 8 ) with the variable nuclear-nuclear saturation governed by \Gamma:=2^{n_{\Gamma}/2}\>|\>n_{\Gamma}\in\mathbb{N} can be done using \mathcal{T}_{V,\Gamma}=2\mathcal{T}_{\textrm{PREP}_{V}}+4(\eta-1)(1+3n_{g})-8+\mathcal{T}_{M}+3 (126) Toffolis, with a 1-norm of \alpha_{V,\Gamma}=\frac{\lambda_{V}(\Gamma)}{2\Delta}, (127) using n_{V}=n_{M}+2\left\lceil\log_{2}\eta\right\rceil (128) block-encoding qubits, \tilde{n}_{V,\Gamma}=\tilde{n}_{M}+\tilde{n}_{\textrm{PREP}_{V}}+3 (129) temporary carry ancillas, and incurring an error of \epsilon_{V,\Gamma}\leq\frac{\epsilon_{\zeta}}{2\Delta}+\frac{3\lambda_{V}(\Gamma)}{2^{n_{M}+1}\Delta}. (130) All definitions are the same as in Lemma 18 , while we also used the optimized 1-norm \lambda_{V}(\Gamma):=\sum_{i,j\in\mathcal{N}}\zeta_{i}\zeta_{j}/\Gamma+2\eta_{e}Z_{tot}+\eta_{e}(\eta_{e}-1) for \mathcal{N} the set of nuclear-nuclear interactions and Z_{tot}=\sum_{i\in nuc}\zeta_{i} . Proof. The proof of this lemma is analogous to that of Lemma 18 , with the only difference that the cost of the alternating sign block-encoding needs to be modified. The cost of modifying this block-encoding corresponds to replacing the \mathtt{Sub} routine for the inequality test by a controlled counterpart \mathtt{cSub} , which using Lemma 12 will increase the cost by a total of three extra Toffolis and three extra temporary carry qubits: two Toffolis are coming from the quantum control changing the saturation constant with two associated quantum single-qubit registers, while one Toffoli and one extra qubit come from an additional temporary AND operation. For these associated costs, \Gamma must be defined as the square root of a power of 2, with the reason being that in the inequality test, \Gamma^{2} appears, which then has Hamming weight 1 (an important property in the efficiency of Lemma 12 ). Also, note that the \mathcal{T}_{\textrm{PREP}_{V}} and \tilde{n}_{\textrm{PREP}_{V}} costs used here will be higher by a couple of Toffolis/qubits when compared to those appearing in Lemma 18 , given how the PREPARE routine now also needs to flag a register for nuclear-nuclear interactions. ∎ Finally, we note that the potential operator can be block-encoded with a reduced 1-norm by shifting the spectrum. The idea here is that currently the spectral range of the operator is (0,\|V\|) , and this can be shifted to (-\|V\|/2,\|V\|/2) to reduce \alpha_{V} as realized in Ref. 50 , having that this procedure effectively adds a constant shift by an identity that for all purposes can be neglected. This can be done by testing a more sophisticated inequality. First, rewrite the prior inequality and shift by half the maximum interaction energy 1/4\Delta recalling the fact that the maximum energy comes from particles separated by 1 grid space \Delta and the factor of 2 comes from double-counting interactions: \displaystyle\frac{m}{M}\frac{1}{2\Delta} \displaystyle<\frac{1}{2\Delta\|\vec{q}\|}-\frac{1}{4\Delta} (131) \displaystyle\frac{m}{M} \displaystyle<\frac{1}{\|\vec{q}\|}-\frac{1}{2} (132) \displaystyle\|\vec{q}\|^{2}(4m^{2}+M(4m+M)) \displaystyle<4M^{2}. (133) We see from the second line that this inequality is violated if \|\vec{q}\|\geq 2\>|\>\forall\>m or for \|\vec{q}\|^{2}\geq 4 . In the last line we rearrange the inequality into a form that is efficient to compute with arithmetic. This leads us to define the following operator: \displaystyle V^{\rm{ss}}_{12} \displaystyle=\frac{1}{\Delta M}\sum_{m=0}^{M-1}\sum_{\vec{q}_{1},\vec{q}_{2}}v_{m}\left(\|\vec{q}_{1}-\vec{q}_{2}\|^{2}\right)\,\,\outerproduct{\vec q_1}{\vec q_1}\otimes\outerproduct{\vec q_2}{\vec q_2}, (134) with v_{m}(x)=\begin{cases}1,&\textup{if}\>\left(\frac{m}{M}<\frac{1}{x}-\frac{1}{2}\right)\land(x\leq 2),\\ -1,&\textup{if}\>\left(\frac{m}{M}>\frac{1}{x}-\frac{1}{2}\right)\land(x>2),\\ (-1)^{m},&\textup{otherwise}.\end{cases} (135) To generalize this to the case where the nuclear-nuclear interaction can be further saturated by \Gamma , this inequality undergoes the following modification: \displaystyle\frac{m}{M}\frac{1}{2\Delta\Gamma} \displaystyle<\frac{1}{2\Delta\|\vec{q}\|}-\frac{1}{4\Delta\Gamma} (136) \displaystyle\|\vec{q}\|^{2}(4m^{2}+M(4m+M)) \displaystyle<4\Gamma^{2}M^{2} (137) \displaystyle\|\vec{q}\|^{2}(4m^{2}+2^{n_{M}}(4m+2^{n_{M}})) \displaystyle<\Gamma^{2}2^{2n_{M}+2}, (138) in which case we have the function v_{m}^{(nuc)}(x)=\begin{cases}1,&\textup{if}\>\left(\frac{m}{M}<\frac{\Gamma}{x}-\frac{1}{2}\right)\land(x\leq 2\Gamma),\\ -1,&\textup{if}\>\left(\frac{m}{M}>\frac{\Gamma}{x}-\frac{1}{2}\right)\land(x>2\Gamma),\\ (-1)^{m},&\textup{otherwise}.\end{cases} (139) As with the previous construction, by testing this inequality the V^{ss} operator can be efficiently block encoded, with the following lemma summarizing the costs, as shown in Fig. 20 . \scriptstyle 2(n_{g}+n_{M}+3) \scriptstyle n_{M} \scriptstyle+2 \scriptstyle+2 \scriptstyle 2n_{M} \scriptstyle+2 \scriptstyle+2 \scriptstyle 2n_{g}+2 \scriptstyle 3n_{g} \scriptstyle 3 \scriptstyle 3n_{g} \ket{i,j\in\mathcal{N}} \hskip 25.6073pt\mathtt{cSub}[2^{2(n_{M}+1+b\cdot n_{\Gamma})}]\hskip 25.6073pt \hskip 25.6073pt\mathtt{cSub}[2^{2(n_{M}+1+b\cdot n_{\Gamma})}]\hskip 25.6073pt \ket{0}_{\mathcal{F}} \ket{\mathcal{F}} \ket{0} \ket{0}_{m} \mathtt{Had}^{\otimes n_{M}} \mathtt{Had}^{\otimes n_{M}} \hskip 8.5359pt\mathtt{Square}\hskip 8.5359pt \hskip 8.5359pt\mathtt{Square}\hskip 8.5359pt \mathtt{Mult}[2^{2}] \mathtt{Mult}[2^{2}] \mathtt{Add}[2^{n_{M}}] \mathtt{Add}[2^{n_{M}}] \hskip 8.5359pt\mathtt{Add}[\times 2^{n_{M}}]\hskip 8.5359pt \hskip 8.5359pt\mathtt{Add}[\times 2^{n_{M}}]\hskip 8.5359pt \ket{0} \mathtt{Mult}[2^{2}] \mathtt{Mult}[2^{2}] \hskip 8.5359pt\mathtt{Mult}\hskip 8.5359pt \hskip 8.5359pt\mathtt{Mult}\hskip 8.5359pt \ket{0} \hskip 8.5359pt\mathtt{Sum\ of\ Squares}\hskip 8.5359pt \hskip 8.5359pt\mathtt{Sum\ of\ Squares}\hskip 8.5359pt \hskip 14.22636pt\mathtt{cSub}[2^{2+b\cdot 2n_{\Gamma}}]\hskip 14.22636pt \hskip 14.22636pt\mathtt{cSub}[2^{2+b\cdot 2n_{\Gamma}}]\hskip 14.22636pt \ket{\vec q_1} \mathtt{AbsDiff}^{\otimes 3} \mathtt{AbsDiff}^{\otimes 3} \ket{0} \ket{\vec q_2} \ket{0} Z Z b b b b 0 a\leq 0 ab a a a a a 0 a^{2} b b+a\cdot 2^{n_{M}} a a 0 x^{2}+y^{2}+z^{2} b b a x,y,z x,y,z 0 a\leq Figure 20: Implementation for spectrally shifted and variably saturated Coulomb interaction flagging routine (replacing flagging routine \mathcal{U}_{\rm arithmetic} in Fig. 2 ), as specified by Eqs.( 134 - 139 ) and summarized by Lemma 20 . Single-register \mathtt{Mult}[2^{n}] routines simply append n qubits to the end of the register for encoding multiplication by power of 2 . \mathtt{Add}[\times 2^{n}] routine corresponds to adder where the “ a ” register is being multiplied by a power of 2 , which can be done with usual adder circuit with shifted a register by n bits, having a classical control for value of 0 in associated n bits. Note that Pauli Z gate in bottom register does not get applied during uncomputation, as it adds a global -1 sign for negative values below median appearing from spectral shifting. Lemma 20 (Controlled block-encoding of spectral shifted V operator with saturation) . There exists a (\alpha_{V}^{\rm ss},n_{V}^{\rm ss},\epsilon_{V,\Gamma}) controlled block-encoding of V^{\rm{ss}}_{12} defined in Eq. ( 135 ) that requires \mathcal{T}_{V,\Gamma}^{\rm ss}=6n_{g}^{2}+2n_{M}^{2}+8n_{M}n_{g}+36n_{g}+20n_{M}+46+2\mathcal{T}_{\textrm{PREP}_{V}}+4(\eta-1)(1+3n_{g}) (140) Toffoli gates to construct, with a 1-norm of \alpha_{V}^{\rm ss}=\frac{\lambda_{V}(\Gamma)}{4\Delta} (141) using n_{V,\Gamma}^{\rm ss}=n_{M}+2\left\lceil\log_{2}\eta\right\rceil (142) block-encoding qubits, \tilde{n}_{V,\Gamma}^{\rm ss}=\max\{(6n_{g}+6n_{M}+25),\;(3n_{g}^{2}+n_{g}+4)\}+\tilde{n}_{\textrm{PREP}_{V}} (143) temporary carry ancillas, and incurring an error of \epsilon_{V,\Gamma}\leq\frac{\epsilon_{\zeta}}{2\Delta}+\frac{\lambda_{V}(\Gamma)}{2^{n_{M}}\Delta}. (144) Proof. In perfect analogy to Lemma 18 , we here use a swap network over an alternating sign implementation for the Coulomb interaction, with the difference that this implementation also includes the discussed spectral shift, alongside the saturation \Gamma . We now review the cost of the shifted and saturated alternating sign implementation for the Coulomb potential, with the remainder of the costs following exactly the same line of reasoning as in Lemma 18 . We need to use quantum arithmetic to compute the inequality test of Eq. ( 138 ), which can be done with the following steps that correspond to circuit 20 . We will again calculate the qubit overhead by noting the maximum ancilla at any point in time using the notation for temporary carry ancillas (\cdot) : 1. Three calls to the \mathtt{AbsDiff} operation, each one acting on two n_{g} -qubit registers ( Lemma 7 ). This requires 3\times(2n_{g})=6n_{g} Toffolis, 3 ancillas, and n_{g}+1 temporary carry qubits, noting that the latter can be reused for each of the three applications. The qubit overhead is \tilde{n}_{M}^{(1)}=3+(n_{g}+1) . 2. One call to the \mathtt{Sum\ of\ Squares} oracle (Lemma 8 of Ref. 84 ) acting on three n_{g} -qubit registers, requiring a total of 3n_{g}^{2}-n_{g}-1 Toffolis, 2n_{g}+2 additional ancillas for encoding the result and 3n_{g}^{2}-n_{g}-1 temporary carry qubits. The qubit overhead is \tilde{n}_{M}^{(2)}=2n_{g}+5+(3n^{2}_{g}-n_{g}-1) . 3. One \mathtt{Square} routine on the n_{M} -qubit register (Lemma 6 of Ref. 84 ), requiring n_{M}^{2}-2 Toffolis, 2n_{M} ancillas for storing the result, and 2n_{M}+2 temporary carry ancillas. The qubit overhead is \tilde{n}_{M}^{(3)}=2n_{g}+2n_{M}+5+(2n_{M}+2) . 4. Multiply the registers \ket{m} and \ket{m^2} each by 4 with a bit shift. This has no Toffoli cost, but requires 2 qubits each. This has no Toffoli cost, and the qubit overhead is \tilde{n}_{M}^{(4)}=2n_{g}+2n_{M}+9 5. Add M=2^{n_{M}} to the \ket{4m} state. Since this is addition by a power of 2, we only need an adder on the top 2 bits with a carry-out. This has a cost of 2 Toffoli. The qubit overhead is \tilde{n}_{M}^{(5)}=2n_{g}+2n_{M}+10+(2) . 6. Multiply the register storing \ket{4m +M} by M , which can be done with bit shifts. This shift can be done be done by reinterpreting the indices of the bits. Since \ket{M(4m+M)} will be used in an adder in the next step, and since the bottom n_{M} bits will be deterministically 0 after the shift, classical controls can be used on those bits using a hybrid quantum-classical adder as in Fig. 15 . In this step, prior to using this adder, there is no cost. 7. Add \ket{M(4m+M)} to \ket{4m^2} in place with the hybrid quantum-classical adder. The resulting sum is 2n_{M}+4 bit state, 2 more bits than needed to store 4m^{2} (so the end of said state is padded prior to addition), and we can remove the Toffoli on the lowest bit with a classical control, giving a cost of 2n_{M}+3 Toffoli. The qubit overhead is \tilde{n}_{M}^{(7)}=2n_{g}+2n_{M}+12+(2n_{M}+3) . 8. Multiply the two registers \ket{\|q\|^2} and \ket{4m^2 + M(4m+M)} using Lemma 10 . This gives a Toffoli cost of 4n_{M}n_{g}+10n_{g}+8n_{M}+21 , with a qubit overhead of \tilde{n}_{M}^{(8)}=4n_{g}+4n_{M}+18+(2n_{g}+2n_{M}+7) . 9. Perform an inequality test to check if \|q\|^{2}\leq 4\Gamma^{2} using the subtraction from Lemma 12 , where we subtract by either 4\Gamma^{2} or 4 controlled on the register flagging nuclear-nuclear interactions ( \Gamma=1 when the interaction is not nuclear-nuclear). This has cost 2n_{g}+1 . The qubit overhead is \tilde{n}_{M}^{(9)}=4n_{g}+4n_{M}+22+(2n_{g}) . 10. Perform the overall inequality test using \mathtt{cSub} controlled on whether the reaction is between two nuclei or not. This is performed on the state \ket{\|q\|^2(4m^2+M(m+M))} , which is stored in 2n_{M}+2n_{g}+6 qubits. As stated previously, since we are subtracting powers of 2, the bottom 2n_{M} bits do not change. Performing the subtraction on the 2n_{g}+6 high bits then gives a cost of 2n_{g}+5 . The qubit overhead is \tilde{n}_{M}^{(10)}=4n_{g}+4n_{M}+23+(2n_{g}+4) . 11. One Toffoli is needed for the controlled Z . 12. Uncompute prior arithmetic other than the step 10, which can be uncomputed for free by holding on to dirty ancillae. In terms of the error, the sign-trick inequality test is begin performed with the same precision as the non-shifted version of the block encoding, so the error follows from the prior lemmas. ∎ B.2 Block-encoding T We now show how block-encoding of the kinetic energy T can be done simply by combining the one-dimensional swap network technique in Lemma 3 with the squaring block-encoding from Lemma 9 . Note that the kinetic energy is block-encoded using the swap network recursively: first it is done over Cartesian coordinates, effectively block-encoding T_{1} [Eq. ( 30 )], which is then used inside another swap network running over all \eta particles. Lemma 21 (Controlled block-encoding of kinetic energy operator) . Controlled block-encoding of the kinetic energy operator T in Eq. ( 8 ) can be done using \mathcal{T}_{T}=2n_{g}^{2}+14n_{g}-3+2\mathcal{T}_{R}(\epsilon_{W})+2\mathcal{T}_{m}(\epsilon_{m})+[2(\eta-1)(1+3n_{g})-4] (145) Toffolis, with a 1-norm of \alpha_{T}=\frac{3\pi^{2}2^{2(n_{g}-1)}}{L^{2}}\lambda_{T}, (146) using n_{T}=\left\lceil\log_{2}\eta\right\rceil+n_{g}+4 (147) ancilla qubits, \tilde{n}_{T}=\left\lceil\log_{2}\eta\right\rceil+n_{g}-1+\tilde{n}_{mass}(\epsilon_{m}) (148) temporary carry ancillas, and incurring an error of \epsilon_{T}\leq\alpha_{T}\left(\epsilon_{W}+\frac{\epsilon_{m}}{\lambda_{T}}\right). (149) Here we have defined the mass 1-norm \lambda_{T}:=\sum_{i}m_{i}^{-1} , alongside the number of temporary qubits for the state associated PREPARE routine \tilde{n}_{mass}(\epsilon_{m}) , incurring an error \epsilon_{m} and using \mathcal{T}_{m}(\epsilon_{m}) Toffolis. \epsilon_{W} corresponds to the error in the W state preparation in Fig. 16 . Proof. We first start by noting that the full block-encoding of T is done by using a swap network over the different mass coefficients for different particles m_{i}^{-1} for the single-particle kernel T_{1} . This T_{1} operator in turn corresponds to a swap network block-encoding of the squaring operator in Lemma 9 swapped over 3 Cartesian coordinates, with the associated 1-norm \displaystyle\alpha_{T_{1}} \displaystyle=\frac{2\pi^{2}}{L^{2}}\cdot 3\cdot\alpha_{\rm SQ}(n_{g}) (150) \displaystyle=\frac{3\pi^{2}2^{2(n_{g}-1)}}{L^{2}}, (151) where the 2\pi^{2}/L^{2} comes from the physical momentum units (see Eq. ( 10 )), the factor of 3 corresponds to the 1-norm for the linear combination over Cartesian coordinates, and \alpha_{\rm SQ}(n_{g})=(2^{2(n_{g}-1)})/2 is the 1-norm from the squaring block-encoding, noting that there is a factor of 1/2 appearing from the fact that the squaring routine encodes 2q^{2}-1 . The 1-norm of the full kinetic energy thus becomes \displaystyle\alpha_{T} \displaystyle=\alpha_{T_{1}}\cdot\sum_{i}\frac{1}{m_{i}} (152) \displaystyle=\frac{3\pi^{2}2^{2(n_{g}-1)}}{L^{2}}\lambda_{T}. (153) Noting that no error is incurred by the squaring routine, the error for T_{1} can be upper bounded using Lemma 3 as \displaystyle\epsilon_{T_{1}} \displaystyle\leq\alpha_{T_{1}}\cdot\epsilon_{W} (154) \displaystyle=\frac{3\pi^{2}2^{2(n_{g}-1)}}{L^{2}}\epsilon_{W}, (155) where \epsilon_{W} is the error associated with the W state preparation ( Lemma 14 ). Considering an error of \epsilon_{m} for the mass coefficients and using Lemma 3 again, we recover the total error for this routine \displaystyle\epsilon_{T} \displaystyle\leq\lambda_{T}\epsilon_{T_{1}}+\alpha_{T_{1}}\epsilon_{m} (156) \displaystyle=\frac{3\pi^{2}2^{2(n_{g}-1)}}{L^{2}}\lambda_{T}\epsilon_{W}+\frac{3\pi^{2}2^{2(n_{g}-1)}}{L^{2}}\epsilon_{m} (157) \displaystyle=\alpha_{T}\left(\epsilon_{W}+\frac{\epsilon_{m}}{\lambda_{T}}\right). (158) The number of ancilla qubits for this block-encoding corresponds to the sum of those used for the mass coefficients ( \left\lceil\log_{2}\eta\right\rceil ), those used for the Cartesian coordinates ( 3 ), and those used by the squaring routine ( n_{g}+1 ), yielding a total of n_{T}=\left\lceil\log_{2}\eta\right\rceil+n_{g}+4 (159) block-encoding ancillas. For the number of temporary carry ancillas, we need to sum those required by the squaring block-encoding ( n_{g}-1 ), those used by the PREPARE routine for the mass coefficients ( \tilde{n}_{mass} ), and those coming from the unary iteration for the swap network ( \left\lceil\log_{2}\eta\right\rceil ), recovering \tilde{n}_{T}=\left\lceil\log_{2}\eta\right\rceil+n_{g}-1+\tilde{n}_{mass}. (160) Finally, we have that the Toffoli cost of this routine can be obtained by adding the cost of the squaring block-encoding ( 10n_{g}-6 ), two times cost of the W state preparation ( 2\times(\mathcal{T}_{R}(\epsilon_{W})+1) ), two times the cost of the mass state preparation ( 2\mathcal{T}_{m} ), two times the cost of the SWAPs over Cartesian coordinates ( 2\times 2n_{g} ), two times the cost of performing a QFT over n_{g} qubits ( 2\times n_{g}(n_{g}+1) ), and two times the cost of the multiplexed SWAPs over particle registers ( 2(\eta-1)(1+3n_{g})-4 from Lemma 3 ) obtaining a total cost of \mathcal{T}_{T}=2n_{g}^{2}+16n_{g}-4+2\mathcal{T}_{R}(\epsilon_{W})+2\mathcal{T}_{m}+[2(\eta-1)(1+3n_{g})-4], (161) where we have left the swap network cost inside of brackets for clarity in our following deductions. ∎ B.3 Block-encoding H Having shown how our routines correctly block-encode the kinetic and potential energy operators, we are now ready to provide the proof of Theorems 1 and 2 summarizing our costs, having that the block-encoding of the full Hamiltonian is done as a linear combination of block-encodings for T and V . See 1 Proof. This theorem follows from building the block-encodings of T and V with their most optimized versions ( Lemmas 21 and 20 ), alongside Lemma 16 for implementing the sum of both block-encodings as described by Eqs. 34 and 35 . Note that as shown in Fig. 4 , the swap networks for both block-encodings have been combined, which effectively removes the Toffoli cost from performing the multiplexed SWAPs in the kinetic energy routine. Overall, this yields the 1-norm \displaystyle\alpha_{H} \displaystyle=\alpha_{V}+\alpha_{T} (162) \displaystyle=\frac{\lambda_{V}(\Gamma)}{4\Delta}+\frac{3\pi^{2}2^{2(n_{g}-1)}}{L^{2}}\lambda_{T} (163) \displaystyle\in\mathcal{O}\left(\frac{\eta^{2}}{\Delta}+\frac{\eta}{\Delta^{2}}\right), (164) where we have used \lambda_{V}(\Gamma)\in\mathcal{O}(\eta^{2}) , \lambda_{T}\in\mathcal{O}(\eta) , and L\in\mathcal{O}(\Delta\cdot 2^{n_{g}}) (see Eq. ( 5 )). The total number of Toffolis is \displaystyle\mathcal{T}_{H} \displaystyle=(2\mathcal{T}_{\textup{PREP}_{V}}+4(\eta-1)(1+3n_{g})+2n^{2}_{m}+8n_{M}n_{g}+20n_{M}+6n^{2}_{g}+36n_{g}+46)+(2n_{g}^{2}+14n_{g}-3+2\mathcal{T}_{R}(\epsilon_{W})+2\mathcal{T}_{m}) (165) \displaystyle=12\eta n_{g}+4\eta+2n_{M}^{2}+8n_{g}^{2}+8n_{M}n_{g}+40n_{g}+20n_{M}+39+2(\mathcal{T}_{\textup{PREP}_{V}}+\mathcal{T}_{R}(\epsilon_{W})+\mathcal{T}_{m}) (166) \displaystyle\in\mathcal{O}(\eta n_{g}+n_{M}^{2}+n_{g}^{2}), (167) noting that \mathcal{T}_{\textup{PREP}_{V}}\in\tilde{\mathcal{O}}(\sqrt{\eta}) , while requiring \displaystyle n_{H} \displaystyle=1+\max\{n_{V},n_{T}\} (168) \displaystyle=n_{M}+2\left\lceil\log_{2}\eta\right\rceil+3 (169) ancillas for the block-encoding. The number of temporary block-encoding ancillas corresponds to the maximum of required by T and V , which corresponds to \displaystyle\tilde{n}_{H} \displaystyle=\tilde{n}_{V}+n_{R} (170) \displaystyle=n_{g}+4+\max\{3n^{2}_{g};4n_{M}+5n_{g}+6\}+\tilde{n}_{\textup{PREP}_{V}}. (171) Finally, the error of this routine will be given by (using Lemma 16 ): \displaystyle\epsilon_{H} \displaystyle\leq\alpha_{H}\epsilon_{r}+\frac{\alpha_{V}}{\alpha_{H}}\epsilon_{V}+\frac{\alpha_{T}}{\alpha_{H}}\epsilon_{T} (172) \displaystyle=\alpha_{H}\epsilon_{r}+\frac{\alpha_{V}}{\alpha_{H}}\left(\frac{\epsilon_{\zeta}}{2\Delta}+\lambda_{V}\epsilon_{M}\right)+\frac{\alpha_{T}}{\alpha_{H}}\left(\epsilon_{W}+\frac{\epsilon_{m}}{\lambda_{T}}\right). (173) We now deduce the associated scalings, where we use \epsilon_{V}\in\mathcal{O}(\epsilon_{H}) , from which we can write \mathcal{O}(n_{M})=\mathcal{O}(\log\eta/\epsilon_{V})=\mathcal{O}(\log\eta/\epsilon_{H}) . Considering a simulation box with a volume that grows linearly with the number of particles, we have that \mathcal{O}(L^{3})=\mathcal{O}(\eta) . We also assume that the grid spacing does not scale with system size, namely \mathcal{O}(\Delta)=\mathcal{O}(1) . We thus arrive to \mathcal{O}(n_{g})=\mathcal{O}(\log\eta^{\frac{1}{3}})=\mathcal{O}(\log\eta) , from which we get \displaystyle\mathcal{T}_{H} \displaystyle\in\mathcal{O}\left(\eta\log\eta+\log^{2}\frac{\eta}{\epsilon_{H}}+\log^{2}\eta\right) (174) \displaystyle\subset\tilde{\mathcal{O}}\left(\eta+\log^{2}\frac{1}{\epsilon_{H}}\right), (175) for the Toffoli complexity, and \displaystyle n_{H} \displaystyle\in\mathcal{O}\left(\log\frac{\eta}{\epsilon}\right)+\mathcal{O}\left(\log\eta\right)+\mathcal{O}(1) (176) \displaystyle=\mathcal{O}\left(\log\eta+\log\frac{1}{\epsilon}\right). (177) ∎ Appendix C Simulation complexity In this section we calculate the overall Toffoli gates required for implementing an \epsilon -accurate time-evolution operator e^{-iHt} using our algorithm. Thus far we have calculated the total block-encoding 1-norm \alpha_{H} and accuracy \epsilon_{H} , which provides the means for calculating the necessary degree of polynomial approximation d to implement via QSP for a qubitized simulation of the time-evolution operator. Since the block-encoding will be iteratively called in the QSP sequence (of which has a length dependent on t ) the error in the block-encoding will naturally propagate in time. In order to make the guarantee a total simulation error \epsilon , we use Lemma 20 from 75 , which accounts for error propagation and simultaneously give the simulation complexity in terms of queries to the block-encoding to perform an \epsilon -accurate implementation of the time-evolution operator e^{-iHt} via the qubitization algorithm using generalized quantum signal processing 65 . Note that a similar result is also presented in Ref. 19 . The lemma states that given access to an (\alpha_{H},n_{H},\epsilon_{H}) block-encoding of the Hamiltonian \tilde{O}_{H} , then one can construct f(\tilde{O}_{H}) which is a (1,n_{H}+2,\epsilon) block-encoding of e^{-iHt} , where f(x) is effectively a polynomial approximation of \exp(-ix) such that |f(x)-\exp(-ix)|\leq\epsilon_{\mathrm{exp}} . In order for the entire simulation error to be bound by \epsilon , the following inequality must be satisfied t\epsilon_{H}+\epsilon_{\mathrm{exp}}\leq\epsilon. (178) Given our prior analysis in the proof of Theorem 1 , the total error must satisfy: \displaystyle t\epsilon_{H}+\epsilon_{\mathrm{exp}} \displaystyle=t\left(\alpha_{H}\epsilon_{r}+\frac{\alpha_{V}}{\alpha_{H}}\epsilon_{V}+\frac{\alpha_{T}}{\alpha_{H}}\epsilon_{T}\right)+\epsilon_{\mathrm{exp}} (179) \displaystyle\leq t\left(\alpha_{H}\epsilon_{r}+\frac{\alpha_{V}}{\alpha_{H}}\left(\frac{\epsilon_{\zeta}}{2\Delta}+\lambda_{V}\epsilon_{M}\right)+\frac{\alpha_{T}^{2}}{\alpha_{H}}\left(\epsilon_{W}+\frac{\epsilon_{m}}{\lambda_{T}}\right)\right)+\epsilon_{\rm exp}\leq\epsilon, (180) where we have used \Delta\geq L/2^{n_{g}} to arrive to the second line. As expected, for long time simulations the block-encoding of the Hamiltonian will need to be achieved with high precision. The most expensive part of doing so will likely be in the inequality test to calculate the electrostatic potential. As the desired accuracy of block-encoding is increased, the number of qubits to perform said inequality test will grow (albeit logarithmically), which then increases the Toffoli cost of arithmetic. Given that the algorithm complexity scales logarithmically with respect to all errors considered, finding the “optimal” means for distributing error will likely lead to at most a small constant-factor improvement over the naive choice of evenly distributing the error. Let us consider a set of positive numbers f_{r},f_{\rm exp},f_{M},f_{\zeta},f_{m} , and f_{W} such that their sum is equal to 1 , associated with portion of the error is allowed to come from each component, as seen in 3 . A uniform distribution of error would then correspond to choosing f_{r}=f_{\rm exp}=f_{M}=f_{\zeta}=f_{m}=f_{W}=1/6 . Note how we have also deduced the scaling of each error with respect to the main parameters used in this work by considering all f ’s to be \mathcal{O}(1) , while also considering that both the number of grid points and length per Cartesian direction grow as L,2^{n_{g}}\in\mathcal{O}(\eta^{\frac{1}{3}}) , from which \Delta\in\mathcal{O}(1) . Error Expression Scaling Rotation error in \textup{PREP}_{H} \displaystyle\epsilon_{r}=\epsilon f_{r}\cdot\frac{1}{t\alpha_{H}} \displaystyle\mathcal{O}\left(\frac{\epsilon}{t}\cdot\frac{1}{\eta^{2}}\right) Polynomial approximation error \epsilon_{\mathrm{exp}}=\epsilon f_{\rm exp} \displaystyle\mathcal{O}\left(\epsilon\right) Error in approximating the potential \displaystyle\epsilon_{M}=\epsilon f_{M}\cdot\frac{\alpha_{H}}{t\lambda_{V}\alpha_{V}} \displaystyle\mathcal{O}\left(\frac{\epsilon}{t}\cdot\frac{1}{\eta^{2}}\right) Error in charge coefficients \displaystyle\epsilon_{\zeta}=\epsilon f_{\zeta}\cdot\frac{2\alpha_{H}\Delta}{t\alpha_{V}} \displaystyle\mathcal{O}\left(\frac{\epsilon}{t}\right) Error in mass coefficients \displaystyle\epsilon_{m}=\epsilon f_{m}\cdot\frac{\alpha_{H}\lambda_{T}}{t\alpha_{T}^{2}} \displaystyle\mathcal{O}\left(\frac{\epsilon}{t}\cdot\eta\right) Error in W state preparation \displaystyle\epsilon_{W}=\epsilon f_{W}\cdot\frac{\alpha_{H}}{t\alpha_{T}^{2}} \displaystyle\mathcal{O}\left(\frac{\epsilon}{t}\right) Table 3: Subroutine errors in relation to total error \epsilon where the grid spacing is taken to be constant for a fixed precision. Note that each contains a factor f_{\cdot} which can be replaced by an arbitrary positive constant given that the constants sum to 1, with the uniform allocation corresponding to taking all of them to be 1/6 . As discussed in the main text, the logarithmic cost dependence with respect to errors makes the costs mostly insensitive to the error allocation. Lemma 20 of Ref. 75 leverages recent improvements from generalized quantum signal processing (GQSP) 8 ; 65 to derive a constant factor bound on the degree of this polynomial D . The bound from [Ref. 75 , Lemma 21] is stated below: D(t)=\left\lceil\frac{e}{2}\alpha t+\log\left(\frac{2c}{\epsilon_{\mathrm{exp}}}\right)\right\rceil (181) where c=4(\sqrt{2\pi}e^{1/13})^{-1}\approx 1.47762 . The art of GQSP then dictates that D+2 queries to the block-encoding of the Hamiltonian guarantee an \epsilon -accurate implementation of the time-evolution operator. To calculate the necessary Toffoli gates for our simulation, we can then simply multiply the number of Toffoli gates required to block-encode the Hamiltonian (calculated in prior sections) by (D+2) . The total Toffoli cost \mathcal{T}[e^{-iHt}] can then be approximated as \mathcal{T}[e^{-iHt}]=D(t)\times\mathcal{T}_{H}. (182) Note that the additive factor of 2 is a trivial addition to the complexity, and we omit it from our constant factor formulas for simplicity. In addition, for an n -qubit block-encoding the QSP sequence requires an additional D(n-1) zero controlled Toffoli gates (to control on the entire prep register being \ket{0} ) and D rotations. However, since these costs are additive to D(t)\times\mathcal{T}_{H} , which will be orders of magnitude larger, they will be a negligible contribution to the cost. Having presented these results, we are now ready to present the proof of Theorem 2 . See 2 Proof. We start by combining the results from Theorem 1 , alongside with Eq. ( 182 ). The associated number of queries to the block-encoding oracle for implementing a time evolution with time t is \displaystyle\mathcal{T}[e^{-iHt}] \displaystyle\in\mathcal{O}(D(t)\cdot\mathcal{T}_{H}) (183) \displaystyle=\mathcal{O}\left(\left(\alpha_{H}t+\log\frac{1}{\epsilon}\right)\cdot\left(\eta n_{g}+n_{M}^{2}+n_{g}^{2}\right)\right) (184) \displaystyle=\mathcal{O}\left(\left[\left(\frac{\eta^{2}}{\Delta}+\frac{\eta}{\Delta^{2}}\right)t+\log\frac{1}{\epsilon}\right]\cdot\left[\eta n_{g}+n^{2}_{m}+n^{2}_{g}\right]\right). (185) Inserting the scalings n_{g}\in\mathcal{O}(\log\eta) and n_{M}\in\mathcal{O}(\log\eta/\epsilon_{V})=\mathcal{O}(\log\eta t/\epsilon) into the Toffoli complexity above, we recover \displaystyle\mathcal{T}[e^{-iHt}] \displaystyle\in\mathcal{O}\left(\left[\eta^{2}t+\log\frac{1}{\epsilon}\right]\cdot\left[\eta\log\eta+\log^{2}\frac{\eta t}{\epsilon}+\log^{2}\eta\right]\right) (186) \displaystyle=\mathcal{O}\left(\eta^{3}t\log\eta+\eta\log(\eta)\log\frac{1}{\epsilon}+\textup{polylog}\frac{\eta t}{\epsilon}\right) (187) \displaystyle\subset\tilde{\mathcal{O}}\left(\eta^{3}t+\eta\log\frac{1}{\epsilon}\right). (188) Noting that the error for the block-encoding of the Hamiltonian scales as \epsilon_{H}\in\mathcal{O}(\epsilon/t) , we recover the required number of ancillas \displaystyle\mathcal{O}\left(\log\eta+\log\frac{t}{\epsilon}\right) . ∎ Appendix D Grid discretization for faithful wavefunctions In this appendix we show an approach to determine the Cartesian grid spacing for having a faithful representation of the molecular wavefunction. We start from the well-known result when that 2 to 4 grid points per de Broglie wavelength are required for a faithful representation of a quantum system. This is a direct cause of the Nyquist-Shannon sampling theorem 56 ; 57 , having that this result has been obtained in different places throughout the quantum chemistry literature 17 ; 48 . The two different types of particles that we consider in this work are nuclei and electrons. We first start by considering what this criterion implies for nuclei, and then consider the electronic case. D.1 Nuclear grid spacing We can estimate the nuclear de Broglie wavelengths by considering a system of non-interacting nuclei, where for a given temperature T we can use the equipartition theorem for deducing the average kinetic energy of each nuclei \langle K\rangle_{nuc}=\frac{3}{2}k_{B}T. (189) Using the formula for the de Broglie wavelength \lambda_{dB} of a particle with momentum p (using atomic units): \lambda_{dB}=\frac{2\pi}{\tilde{p}} (190) we can then use the average momentum \tilde{p}=\sqrt{2m\langle K\rangle_{nuc}} , where m is the particle’s mass, to arrive to a formula for the grid spacing: \displaystyle\Delta_{r}^{(nuc)} \displaystyle=\frac{\tilde{\lambda}_{dB}^{(nuc)}}{2} (191) \displaystyle=\frac{\pi}{\sqrt{3mk_{B}T}}. (192) Using room temperature T=300\ \rm K , a single proton would then require a grid spacing of 0.79 Å, while a heavier nuclei (e.g. chlorine) would need 0.12 Å, with more atoms and associated grid spacings being shown in Fig. 21 . Note that the approach we took here for estimating this quantity will break down as T\rightarrow 0 since the classical assumptions we have considered are not valid in this regime. However, considering the spacing for room temperature should be a conservative bound for this case given the de Broglie wavelength will only increase as the temperature goes down. D.2 Electronic grid spacing We now estimate the maximum de Broglie wavelength that will appear for electronic wavefunctions. In general we have that the most localized electronic wavefunction will have the associated largest de Broglie wavelength. For a given atom, the maximally localized electronic wavefunction will be its associated 1s orbital, which should be occupied for most chemical reactions in non-extreme conditions. Considering an atom with nuclear charge Z , its associated 1s wavefunction corresponds to \psi_{1s}(\vec{r})=\sqrt{\frac{Z^{3}}{\pi}}e^{-Zr} (193) where here we have considered without loss of generality for the nuclei to be centered around zero. The associated expectation value of the kinetic energy for this wavefunction then corresponds to \displaystyle\langle K\rangle_{1s} \displaystyle=-\frac{Z^{3}}{2\pi}\int d^{3}r\ e^{-Zr}\nabla^{2}e^{-Zr} (194) \displaystyle=-\frac{Z^{3}}{2\pi}\cdot 4\pi\int_{0}^{\infty}dre^{-Zr}\frac{\partial}{\partial r}\left(r^{2}\frac{\partial}{\partial r}e^{-Zr}\right) (195) \displaystyle=-2Z^{3}\int_{0}^{\infty}dre^{-2Zr}\left(-2Zr+r^{2}Z^{2}\right) (196) \displaystyle=-2Z^{3}\left(Z^{2}\frac{2!}{(2Z)^{3}}-2Z\frac{1!}{(2Z)^{2}}\right) (197) \displaystyle=\frac{Z^{2}}{2}, (198) where we have used the formula \int_{0}^{\infty}dx\ x^{n}e^{-ax}=n!/a^{n+1} . From this we can obtain an associated grid spacing based on the de Broglie wavelength as \displaystyle\Delta_{r}^{(el)} \displaystyle=\frac{2\pi}{2\sqrt{2\langle K\rangle_{1s}}} (199) \displaystyle=\frac{\pi}{Z}. (200) D.3 General grid spacing Since our algorithm uses the same grid for both nuclear and electronic wavefunctions, we have that the overall grid spacing \Delta_{\rm min} will be determined by the minimum between the presented nuclear and electronic de Broglie-based criteria. Figure 21 shows the associated grid spacing for different atoms. Once a required grid spacing is obtained, and considering some width L for the simulation box, the associated number of qubits for discretizing the real-space grid is obtained from Eq. ( 5 ) as n_{g}=\left\lceil\log_{2}\left(1+\frac{L}{\Delta_{\rm min}}\right)\right\rceil, (201) from which an associated effective grid spacing \Delta can be obtained using Eq. ( 5 ) again, having that by construction \Delta\leq\Delta_{\rm min} . Figure 21: Grid spacings for different nuclei, obtained considering room temperature T=300\ \rm K for Eq. 192 . Appendix E Minimum nuclear-nuclear distance For finding a \Gamma value for saturating the nuclear-nuclear interaction, we will consider in a general chemical reaction what is the minimum distance at which we can typically expect to find two nuclei. It is a well known that the molecule with shortest bond length corresponds to \rm H_{2} , with a bond distance of d_{\rm H_{2}}\approx 0.74 Å. Using a harmonic approximation with the associated vibrational frequency of \nu_{\rm H_{2}}\approx 4200\ \rm cm^{-1} , we now consider the thermal distribution of associated vibrational states at a given temperature \beta , which is given by \rho_{\rm H_{2}}=\frac{e^{-\beta H_{\rm H_{2}}}}{Z}, (202) where we have defined the vibrational harmonic Hamiltonian H_{\rm H_{2}}:=\hbar\omega_{\rm H_{2}}\left(n+\frac{1}{2}\right). (203) Here \omega_{\rm H_{2}}=2\pi c\nu_{\rm H_{2}} is the angular frequency associated to the vibrational frequency with c the speed of light, n is the bosonic number operator, and we used the partition function Z=\tr{e^{-\beta H_{\rm H_2}}} . The associated probability distribution of positions around the equilibrium value x=0 is known to be a Gaussian \propto e^{-x^{2}/2\sigma_{x}^{2}} with width \sigma_{x}(\beta)=\frac{\hbar}{2\pi\mu_{\rm H_{2}}\omega_{\rm H_{2}}}\coth\frac{\beta\hbar\omega_{\rm H_{2}}}{2}, (204) with an associated root-mean-squared displacement x_{\rm RMS}=\sqrt{\sigma_{x}} 39 ; 71 . Here we have used the reduced mass for the hydrogen molecule \mu_{\rm H_{2}}=m_{\rm H}/2 , with m_{\rm H}=1.008\rm\ amu the mass of a hydrogen atom. An associated minimum nuclear distance can then be obtained as \Delta_{nuc}(\beta,N)=d_{\rm H_{2}}-N\cdot x_{\rm RMS}(\beta), (205) where N is the number of standard deviations considered, having that for N=2 we have \sim 95.45\% of nuclei having a larger separation, while this number becomes \sim 99.73\% and \sim 99.9937\% for N=3 and N=4 respectively. The associated nuclear distances are shown in Fig. 22 . The nuclear saturation constant for a given grid spacing \Delta is then obtained as \Gamma=\frac{\Delta_{nuc}}{\Delta}. (206) In practice, we want to use the largest constant \tilde{\Gamma}\leq\Gamma so that \tilde{\Gamma}^{2} is a power of two, making \tilde{\Gamma}^{2}M^{2} have Hamming weight 1 and compatible with the most efficient implementation of the hybrid quantum-classical subtraction in Lemma 12 . This can be done by defining \displaystyle n_{\Gamma} \displaystyle:=\left\lfloor 2\log_{2}\frac{\Delta_{nuc}}{\Delta}\right\rfloor (207) \displaystyle\tilde{\Gamma} \displaystyle=2^{n_{\Gamma}/2}, (208) which guarantees that the induced minimal nuclear distance is \tilde{\Delta}_{nuc}=\Delta\tilde{\Gamma}\leq\Delta_{nuc}. (209) Finally, we note that an analogous strategy could be used for obtaining minimal distances of any nuclear pair by using an associated experimental vibrational frequency for that bond. For vibrational frequencies which depend on what functional group the bond is a part of, the lowest frequency yielding an estimate of the smallest \Delta_{nuc} should be used. Figure 22: Minimum nuclear distance for \rm H_{2} bond as a function of temperature. Different curves correspond to associated confidence interval coming from N standard deviations. Appendix F Rigorous bounds on separations The above discussion provides useful heuristic estimates of the separation needed between particles but these estimates may be difficult to apply quantitatively to show that the separation is bounded below by a constant. Here we provide explicit estimates based on assumptions about the moments of the energy distribution that allow us to bound the separation. Lemma 22 . For any p\geq 0 , Hermitian H\in\mathbb{C}^{2^{n}\times 2^{n}} and t\in\mathbb{R} the expectation value \bra{\psi(t)}H^{p}\ket{\psi(t)}=\bra{\psi(0)}H^{p}\ket{\psi(0)} where \ket{\psi(t)}=e^{-iHt}\ket{\psi(0)} . Proof. The result immediately follows from the fact that H commutes with e^{-iHt} . ∎ Next if we are promised an initial value of the mean energy and the variance of the energy then we can argue that large fluctuations of the energy will happen with vanishing probability and in turn that configurations that have unreasonably large potential energy must be improbable. We will use this property to bound, with high probability, the inter electronic and inter nuclear separations. Theorem 23 . Let \ket{\psi(t)} be a bound state for the Coulomb Hamiltonian and assume that it has the property that for all time \ket{\psi(t)} is confined within a box of side length L in position space in three spatial dimensions. Further let us assume that the mean energy for the system is known to be \bra{\psi(0)}H\ket{\psi(0)}=\bar{E} . Then let \epsilon and \delta be probabilities and let \gamma be an error tolerance. We then have that with probability at least 1-\epsilon for any time t^{*} sampled uniformly from [-\infty,\infty] the probability of drawing a momentum measurement greater than \sqrt{\frac{3m_{e}(\eta_{e}+\eta_{n})\bar{E}}{\delta\epsilon}} is at most \delta and the error in approximating the wave function to be constant over a distance of h is at most \gamma if h\leq\gamma\left(\sqrt{\frac{6\pi}{L}}\left(\frac{\epsilon\delta}{3m_{e}(\eta_{e}+\eta_{n})\bar{E}}\right)^{3/4}\right) Proof. The Virial theorem states that for the Coulomb potential V(\vec{r},\vec{R}) \displaystyle\mathbb{E}_{t}\bra{\psi(t)}T\ket{\psi(t)}=-2\mathbb{E}_{t}\bra{\psi(t)}V\ket{\psi(t)} (210) for any bound state \ket{\psi(t)} (ignoring for notational simplicity that \ket{\psi} is not necessarily an element of a Hilbert space). From energy conservation, formalized by Lemma 22 , we then have that \mathbb{E}_{t}\bra{\psi(t)}H\ket{\psi(t)}=\bar{E}=\mathbb{E}_{t}(\bra{\psi(t)}T\ket{\psi(t)}+\mathbb{E}_{t}\bra{\psi(t)}V\ket{\psi(t)}=\frac{1}{2}\mathbb{E}_{t}(\bra{\psi(t)}T\ket{\psi(t)}) (211) Thus from the Markov inequality the probability that the kinetic energy is greater than T_{\max} is and any time randomly chosen from -\infty to \infty {\rm Pr}(T\geq T_{\max})\leq\frac{\bar{E}}{2T_{\max}} (212) Since T=\sum_{i}p_{i}^{2}/2m_{i} in momentum eigenbasis, it follows from the fact that the sum is positive that for any given momenta component \ell {\rm Pr}(p_{\ell}\geq\sqrt{2m_{e}T_{\max}})\leq\frac{\bar{E}}{2T_{\max}} (213) where m_{e} is the mass of an electron, which we assume is less than or equal to the masses of all other charged objects. Thus from the union bound the probability that none of the momenta are greater than the above threshold is at most {\rm Pr}(\max_{\ell}|p_{\ell}|\geq\sqrt{2m_{e}T_{\max}})\leq\frac{3(\eta_{e}+\eta_{n})\bar{E}}{2T_{\max}} (214) Assuming that we are considering a simulation in 3 spatial dimensions. Thus if we have that \Pi_{cut} is the momentum space cutoff projector then this is equivalent to saying that if \ket{\psi(t)} is the continuum analogue of the state that for a randomly chosen time \mathbb{E}_{t}\left(\bra{\psi(t)}\Pi_{\rm cut}\ket{\psi(t)}\mathbf{1}_{\max_{\ell}|p_{\ell}|\geq\sqrt{2m_{e}T_{\max}}}\right)\leq\frac{3(\eta_{e}+\eta_{n})\bar{E}}{2T_{\max}} (215) Thus we have that if t^{*} is a specific time we then have from the Markov inequality that the probability that the cutoff in momentum of \sqrt{2m_{e}T_{\max}} for all momenta in the system fails is bounded by \delta if we increase the threshold by a factor of 1/\delta. Specfically, {\rm Pr}\left((\bra{\psi(t^*)}\Pi_{\rm cut}\ket{\psi(t^*)}\geq\epsilon\right)\leq\delta (216) if T_{\max}=\frac{3(\eta_{e}+\eta_{n})\bar{E}}{2\delta\epsilon}. (217) In turn, this implies that the maximum mentum cutoff for the same assumption is p_{\max}=\sqrt{2m_{e}T_{\max}}=\sqrt{\frac{3m_{e}(\eta_{e}+\eta_{n})\bar{E}}{\delta\epsilon}} (218) Now that the dynamics remains restricted to a box of size L^{3} . We then can use the standard solution for the particle in a box to express the eigenfunctions for the kinetic operator to be \sin(2\pi k_i x_i/L) for position coordinate i of any of the particles where k_{i}\in\mathbb{Z}_{+} . Thus our state can be written without loss of generality as \bra{x}\Pi_{\rm cut}\ket{\psi(t^*)}=\sum_{\vec{k}}a_{k_{i}}(t^{*})\left(\prod_{i}\sin(2\pi k_i x_i/L)\right) (219) We then have that if t^{*} is a time that obeys the cutoff \displaystyle\left|\frac{\partial}{\partial_{x_{q}}}\bra{x}\Pi_{\rm cut}\ket{\psi(t^*)}\right| \displaystyle=\left|\sum_{\vec{k}}\frac{2\pi k_{q}a_{k_{i}}(t^{*})}{L}\left(\prod_{{i\neq q}}\sin(2\pi k_i x_i/L)\right)\cos(2\pi k_q x_q/L)\right| \displaystyle\leq\sqrt{\sum_{k_{q}}\frac{4\pi^{2}k_{q}^{2}}{L^{2}}}\sqrt{1-\delta} \displaystyle\leq\sqrt{\sum_{k_{q}}\frac{4\pi^{2}k_{q}^{2}}{L^{2}}}\leq\sqrt{\frac{4\pi^{2}k_{\max}^{3}}{3L^{2}}} (220) from the Cauchy-Schwarz inequality. Next using the momenta eigenvalues we have that k_{q}\leq k_{\max}\leq\frac{L\sqrt{2m_{e}T_{\max}}}{2\pi}=\frac{L}{2\pi}\sqrt{\frac{3m_{e}(\eta_{e}+\eta_{n})\bar{E}}{\delta\epsilon}}. (221) Thus we have that under the assumptions that t^{*} is in the set of times that obey the cutoff \left|\frac{\partial}{\partial_{x_{q}}}\bra{x}\Pi_{\rm cut}\ket{\psi(t^*)}\right|\leq\sqrt{\frac{L}{6\pi}}\left(\frac{3m_{e}(\eta_{e}+\eta_{n})\bar{E}}{\delta\epsilon}\right)^{3/4} (222) The approximation error that arises from discretizing a function over a hypercube of side length h is at most the maximum derivative multiplied by the length h . Thus we have that the discretization error is under these assumptions h\sqrt{\frac{L}{6\pi}}\left(\frac{3m_{e}(\eta_{e}+\eta_{n})\bar{E}}{\delta\epsilon}\right)^{3/4}:=\gamma (223) Our claim then immediately follows. ∎ This provides a rigorous criteria about how the spatial discretization should be set given some moderately strong assumptions about the initial state and the dynamics. As with all discretization bounds, it is often challenging to provide tight estimates that rigorously hold owing to the complicated nature of real space wave functions which will not necessarily be smoothly varying functions of position. In this case, however, we are able to make stronger statements about the typical behaviour of the system owing to conserved quantities and the quantum Virial theorem. Unfortunately, direct estimation of the spatial scale of 1/r is difficult in this problem because of the fact that there are both attractive and repulsive terms allowing for the possibility of particles being tightly concentrated if the attraction and repulsive effects cancel. Specifically, if we have two pairs of distant charged particles, wherein one pair is a proton and an electron and the other is a pair of electrons, then we can move the pair of particles together at the same rate and keep energy constant. This allows in theory an infinitesmal separation to be permitted on purely energetic grounds. The use of the Virial theorem allows us to go beyond this reasoning of the worst possible configuration, but at the price of restricting our discussion to one of probability measures over randomly chosen configurations. Nonetheless, while loose and lacking some of the physical insight of the aforementioned estimatates, these results do provide rigorous guarantees on the discretization scale needed for position with high probability. Appendix G Hyperparameter selection A minimum nuclear distance of \Delta_{nuc}=0.59 Å was considered for the optimized algorithm, with the derivation from statistical arguments in Appendix E guaranteeing that shorter distances will have no significant contributions for the studied reactions. From the condition of the associated constant \tilde{\Gamma}^{2} having Hamming weight 1 , this translated to an effective minimum distance of \tilde{\Delta}_{nuc}\approx 0.49 Å being used for all reactions. All relevant hyperparameters are summarized in Table 4 , with the associated temperatures being used for the de Broglie-based grid spacing determination discussed in Appendix D . We also note that when performing our resource estimates, the Toffoli-based synthesis of single-qubit rotations (e.g. R_{z}(\theta) ) was done by performing an addition of an associated classical constant which depends on \theta on a phase gradient state 79 , having that achieving an accuracy \epsilon_{rot} requires the resources as stated in Lemma 13 . The total Toffoli counts reported in this work also include the cost of preparing the phase gradient state one time, while the qubit counts also take into account the required qubits for the most precise single qubit rotation required throughout the workflow. Reaction number Box width L (Å) Temperature ( o C) n_{g} n_{\Gamma} n_{M} f_{r}^{-1} f_{\rm exp}^{-1} f_{M}^{-1} f_{\zeta}^{-1} f_{m}^{-1} 1 22 30 7 3 24 51.13 25.93 1.64 3.20 56.57 2 22 30 7 3 24 158.64 1.73 3.08 12.18 130.02 3 22 1500 9 7 23 89.89 42.15 1.19 10.31 40.70 4 22 -90 7 3 23 28.39 257.08 1.09 25.87 144.65 5 44 30 8 3 30 83.45 12.95 1.38 5.92 61.28 Table 4: Summary of hyperparameters used in this work. For all systems considered here, an error of \epsilon=10^{-2} was allowed, with associated subroutine errors being optimized to reduce overall Toffoli cost while complying with the total error [ Eq. 180 ] and associated parameters f_{\cdot} ’s. Note that as discussed in the main text, the total cost is extremely similar to what would be obtained with a uniform allocation of errors. To reduce the amount of variables in the optimization problem, we make the choice \epsilon_{W}=\frac{\lambda_{T}-1}{\lambda_{T}^{2}}\epsilon_{m} , such that f_{m} determines each. We lift the constraints of the optimization problem by saturating the total error inequality of Eq. ( 180 ), setting the total error to \epsilon and then solving for \epsilon_{\rm exp} as a function of the other errors. In the optimization problem, we calculate f_{\rm exp}(\epsilon,f_{m},f_{r},f_{\rm{exp}},f_{M},f_{\zeta}) , and optimize the other f parameters, following the strategy of Ref. 75 . We use the gradient boosted trees algorithm from \mathtt{SciKit} 72 , which has been successfully used to optimize the error in prior quantum algorithms 74 .