Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target

The main objective of this paper is to provide a detailed logical resource estimate (LRE) analysis of QLSA based on its further elaborated formulation [5]. Our analysis particularly also aims at including the commonly ignored resource requirements of oracle implementations. In addition to providing a detailed LRE for a large practical problem size, another important purpose of this work is to demonstrate explicitly, i.e., using a fine-grained approach rather than relying on big-O asymptotic approximations, how the concrete resource counts accumulate with an actual quantum-circuit implementation of a quantum algorithm.

Our LRE is based on an approach which combines manual analysis with automated estimates generated via the programming language Quipper and its compiler. Quipper [14, 15] is a domain-specific, higher-order, functional language for quantum computation, embedded in the host-language Haskell. It allows automated quantum circuit generation and manipulation; equipped with a gate-count operation, Quipper offers a universal automated LRE tool. We demonstrate how Quipper’s powerful capabilities have been exploited for the purpose of this work.

We underline that our research contribution is not merely providing the LRE results, but also to demonstrate an approach to how a concrete resource estimation can be done for a quantum algorithm used to solve a practical problem of a large size. Finally, we would also like to emphasize the modular nature of our approach, which allows to incorporate future work as well as to assess the impact of prospective advancements of quantum-computation techniques.

Our analysis was performed within the scope of a larger context: IARPA Quantum Computer Science (QCS) program [16], whose goals were to achieve an accurate estimation and moreover a significant reduction of the necessary computational resources required to implement quantum algorithms for practically relevant problem sizes on a realistic quantum computer. The work presented here was conducted as part of our general approach to tackle the challenges of IARPA QCS program: the PLATO project,² which stands for “Protocols, Languages and Tools for Resource-efficient Quantum Computation.”

The QCS program BAA [17] presented a list of seven algorithms to be analyzed. For the purpose of evaluation of the work, the algorithms were specified in “government-furnished information” (GFI) using pseudo-code to describe purely quantum subroutines and explicit oracles supplemented by Python or MATLAB code to compute parameters or oracle values. While this IARPA QCS program GFI is not available as published material,³ the Quipper code developed as part of the PLATO project to implement the algorithms and used for our LRE analyses is available as published library code [18, 19]. In our analyses, we found the studied algorithms to cover a wide range of different quantum-computation techniques. Additionally, with the algorithm parameters supplied for our analyses, we have seen a wide range of complexities as measured by the total number of gate operations required, including some that could not be executed within the expected life of the universe under current predictions of what a practical quantum computer would be like when it is developed.

This approach is consistent with the one commonly used in computer science for algorithms analysis. There are at least two reasons for looking at large problem sizes. First, in classical computing, we have often been wrong in trying to predict how computing resources will scale across periods of decades. We can expect to make more accurate predictions in some areas in quantum computing because we are dealing with basic physical properties that are relatively well studied. However, disruptive changes may still occur.⁴ Thus, in computer science, one likes to understand the effect of scale even when it goes beyond what is currently considered practical. The second reason for considering very large problem sizes, even those beyond a practical scale, is to develop the level of abstraction necessary to cope with them. The resulting techniques are not tied to a particular size or problem and can then be adapted to a wide range of algorithms and sizes. In practice, some of our original tools and techniques were developed while expecting smaller algorithm sizes. Developing techniques for enabling us to cope with large algorithm sizes resulted in speeding up the analysis for small algorithm sizes.

Determining the algorithmic-level resources is a very important and indispensable first step toward a complete analysis of the overall resource requirements of each particular real-world quantum-computer implementation of an algorithm, for the following reasons. First, it helps to understand the structural features of the algorithm, and to identify the actual bottlenecks of its quantum-circuit implementation. Second, it helps to differentiate between the resource costs that are associated with the algorithmic logical-level implementation (which are estimated here) and the additional overhead costs associated with physically implementing the computation in a fault-tolerant fashion including quantum-computer-technology-specific resources. Indeed, the algorithmic-level LRE constitutes a lower bound on the minimum resource requirements that is independent of which QEC or QC strategies are employed to establish fault-tolerance, and independent of the physics details of the quantum-computer technology. For this reason, it is crucial to develop techniques and tools for resource-efficient quantum computation even at the logical quantum-circuit level of the algorithm implementation. The LRE for QLSA provided in this paper will serve as a baseline for research into the reduction of the algorithmic-level minimum resource requirements.

The key ideas underlying QLSA [3‐5] can be briefly summarized as follows; for a detailed description, see Sect. 3. The preliminary step consists of converting the given system of linear equations \(A{\mathbf {x}}={\mathbf {b}}\) (with \({\mathbf {x}},{\mathbf {b}}\in {\mathbb {C}}^N\) and A a Hermitian \(N\times N\) matrix with \(A_{ij}\in {\mathbb {C}}\)) into the corresponding quantum-theoretic version \(A\left| x\right\rangle =\left| b\right\rangle \) over a Hilbert space \({\mathscr {H}}=({\mathbb {C}}^2)^{\otimes n}\) of \(n=\lceil \log _2N\rceil \) qubits. It is important to formulate the original problem such that the operator \(A:{\mathscr {H}}\rightarrow {\mathscr {H}}\) is self-adjoint, see footnote 1.

Provided that oracles exist to efficiently compute A and prepare state \(\left| b\right\rangle \), the main task of QLSA is to solve for \(\left| x\right\rangle \). According to the spectral theorem for self-adjoint operators, the solution can be formally expressed as \(\left| x\right\rangle =A^{-1}\left| b\right\rangle =\sum _{j=1}^N\beta _j/\lambda _j\left| u_j\right\rangle \), where \(\lambda _j\) and \(\left| u_j\right\rangle \) are the eigenvalues and eigenvectors of A, respectively, and \(\left| b\right\rangle =\sum _{j=1}^N\beta _j\left| u_j\right\rangle \) is the expansion of quantum state \(\left| b\right\rangle \) in terms of these eigenvectors. QLSA is designed to implement this representation.

QLSA starts with preparing (in a multiqubit data register) the known quantum state \(\left| b\right\rangle \) using an oracle for vector \({\mathbf {b}}\). Next, Hamiltonian evolution \(\exp (-iA\tau /T)\) with A as the Hamilton operator is applied to \(\left| b\right\rangle \). This is accomplished by using an oracle for matrix A and Hamiltonian Simulation (HS) techniques [8]. The Hamiltonian evolution is part of the well-established technique known as quantum phase estimation algorithm (QPEA) [6, 7], here employed as a subalgorithm of QLSA to acquire information about the eigenvalues \(\lambda _j\) of A and store them in QPEA’s control register. In the next step, a single-qubit ancilla starting in state \(\left| 0\right\rangle \) is rotated by an angle inversely proportional to the eigenvalues \(\lambda _j\) of A stored in QPEA’s control register. Finally, the latter are uncomputed by the inverse QPEA yielding a quantum state of the form \(\sum _{j=1}^N\beta _j\sqrt{1-C^2/\lambda ^2_j}\left| u_j\right\rangle \otimes \left| 0\right\rangle +\sum _{j=1}^N C\beta _j/\lambda _j\left| u_j\right\rangle \otimes \left| 1\right\rangle \), with the solution \(\left| x\right\rangle \) correlated with the value 1 in the auxiliary single-qubit register. Thus, if the latter is measured and the value 1 is found, we know with certainty that the desired solution of the problem is stored in the quantum amplitudes of the multiqubit quantum register in which \(\left| b\right\rangle \) was initially prepared. The solution can then either be revealed by an ensemble measurement (a statistical process requiring the whole procedure to be run many times), or useful information can also be obtained by computing its overlap \(\left| \langle R\left| x\right\rangle \right| ^2\) with a particular (known) state \(\left| R\right\rangle \) (corresponding to a specific vector \({\mathbf {R}}\in {\mathbb {C}}^N\)) that has been prepared in a separate quantum register [5].

Harrow, Hassidim and Lloyd (HHL) [3] showed that, given the matrix A is well-conditioned and sparse or can efficiently be decomposed into a sum of sparse matrices, and if the elements of matrix A and vector \({\mathbf {b}}\) can be efficiently computed, then QLSA provides an exponential speedup over the best known classical linear-system-solving algorithm. The performance of any matrix-inversion algorithm depends crucially on the condition number \(\kappa \) of the matrix A, i.e., the ratio between A’s largest and smallest eigenvalues. A large condition number means that A becomes closer to a matrix which cannot be inverted, referred to as “ill-conditioned”; the lower the value of \(\kappa \) the more “well-conditioned” is A. Note that \(\kappa \) is a property of the matrix A and not of the linear-system-solving algorithm. Roughly speaking, \(\kappa \) characterizes the stability of the solution \({\mathbf {x}}\) with respect to changes in the given vector \({\mathbf {b}}\). Further important parameters to be taken into account are the sparseness d (i.e., the maximum number of nonzero entries per row/column in the matrix A), the size N of the square matrix A, and the desired precision of the calculation represented by error bound \(\varepsilon \).

In [3] it was shown that the number of operations required for QLSA scales aswhile the best known classical linear-system-solving algorithm based on conjugate gradient method [20, 21] has the run-time complexitywhere, compared to \(O(\cdot )\), the \({\widetilde{O}}(\cdot )\) notation suppresses more slowly growing terms. Thus, it was concluded in [3] that, in order to achieve an exponential speedup of QLSA over classical algorithms, \(\kappa \) must scale, in the worst case, as \(\text{ poly }\log (N)\) with the size of the \(N\times N\) matrix A.

The original HHL-QLSA [3] has the drawback to be nondeterministic, because accessing information about the solution is conditional on recording outcome 1 of a measurement on an auxiliary single-qubit, thus in the worst case requiring many iterations until a successful measurement event is observed. To substantially increase the success probability for this measurement event indicating that the inversion \(A^{-1}\) has been successfully performed and the solution \(\left| x\right\rangle \) (up to normalization) has been successfully computed (i.e., probability that the postselection succeeds), HHL-QLSA includes a procedure based on quantum amplitude amplification (QAA) [22]. However, in order to determine the normalization factor of the actual solution vector \(\left| x\right\rangle \), the success probability of obtaining 1 must be “measured,” requiring many runs to acquire sufficient statistics. In addition, because access to the entire solution \(\left| x\right\rangle \) is impractical as it is a vector in an exponentially large space, HHL suggested that the information about the solution can be extracted by calculating the expectation value \(\left\langle x\right| {\hat{M}}\left| x\right\rangle \) of an arbitrary quantum-mechanical operator \({\hat{M}}\), corresponding to a quadratic form \({\mathbf {x}}^TM{\mathbf {x}}\) with some \(M\in {\mathbb {C}}^{N\times N}\) representing the feature of \({\mathbf {x}}\) that one wishes to evaluate. But such a solution readout is generally also a nontrivial task and typically would require the whole algorithm to be repeated numerous times.

In a subsequent work, Ambainis [4] proposed using variable-time quantum amplitude amplification to improve the run-time of HHL algorithm from \({\widetilde{O}}(\kappa ^2\log N)\) to \({\widetilde{O}}(\kappa \log ^3 \kappa \log N)\), thus achieving an almost optimal dependence on the condition number \(\kappa \).⁵ However, the improvement of the dependence of the run-time on \(\kappa \) was thereby attained at the cost of substantially worsening its scaling in the error bound \(\varepsilon \).

The recent QLSA analysis by Clader, Jacobs and Sprouse (CJS) [5] incorporates useful generalizations to make the original algorithm more practical. In particular, a general method is provided for efficient preparation of the generic quantum state \(\left| b\right\rangle \) (as well as of \(\left| R\right\rangle \)). Moreover, CJS proposed a deterministic version of the algorithm by removing the postselection step and demonstrating a resolution to the read-out problem discussed above. This was achieved by introducing several additional single-qubit ancillae and using the quantum amplitude estimation (QAE) technique [22] to deterministically estimate the values of the success probabilities of certain ancillae measurement events in terms of which the overlap \(\left| \langle R\left| x\right\rangle \right| ^2\) of the solution \(\left| x\right\rangle \) with any generic state \(\left| R\right\rangle \) can be expressed after performing a controlled swap operation between the registers storing these vectors. Finally, CJS also addressed the condition-number scaling problem and showed how by incorporating matrix preconditioning into QLSA, the class of problems that can be solved with exponential speedup can be expanded to worse than \(\kappa \sim \text{ poly }\log (N)\)-conditioned matrices. With these generalizations aiming at improving the efficiency and practicality of the algorithm, CJS-QLSA was shown to have the run-time complexity⁶ which is quadratically better in \(\kappa \) than in the original HHL-QLSA. To demonstrate their method, CJS applied QLSA to computing the electromagnetic scattering cross section of an arbitrary object, using the finite-element method (FEM) to transform Maxwell’s equations into a sparse linear system [23, 24].

In the previous analyses of QLSA [3‐5], resource estimation was performed using “big-O” complexity analysis, which means that it only addressed the asymptotic behavior of the run-time of QLSA, with reference to a similar big-O characterization for the best known classical linear-system-solving algorithm. Big-O complexity analysis is a fundamental technique that is widely used in computer science to classify algorithms; indeed, it represents the core characterization of the most significant features of an algorithm, both in classical and quantum computing. This technique is critical to understanding how the use of resources and time grows as the inputs to an algorithm grow. It is particularly useful for comparing algorithms in a way where details, such as start-up costs, do not eclipse the costs that become important for the larger problems where resource usage typically matters. However, this analysis assumes that those constant costs are dwarfed by the asymptotic costs for problems of interest as has typically proven true for practical classical algorithms. In QCS, we set out to additionally learn (1) whether this assumption holds true for quantum algorithms, and (2) what the actual resource requirements would be as part of starting to understand what would be required for a quantum computer to be a practical quantum computer.

In spite of its key relevance for analyzing algorithmic efficiency, a big-O analysis is not designed to provide a detailed accounting of the resources required for any specific problem size. That is not its purpose, rather it is focused on determining the asymptotic leading-order behavior of a function, and does not account for the constant factors multiplying the various terms in the function. In contrast, in our case we are interested, for a specific problem input size, in detailed information on such aspects as the number of qubits required, the size of the quantum circuit, and run-time required for the algorithm. These aspects, in turn, are critical to evaluating the practicality of actually implementing the algorithm on a quantum computer.

Thus, in this work we report a detailed analysis of the number of qubits required, the quantity of each type of elementary quantum logic gate, the width and depth of the quantum circuit, and the number of logical timesteps needed to run the algorithm—all for a realistic set of parameters \(\kappa , d\), N, and \(\varepsilon \). Such a fine-grained approach to a concrete resource estimation may help to identify the actual bottlenecks in the computation, which algorithm optimizations should particularly focus on. Note that this is similar to the practice in classical computing, where we would typically use techniques like run-time profiling to determine algorithmic bottlenecks for the purpose of program optimization. It goes without much saying that the big-O analyses in [3‐5] and the more fine-grained LRE analysis approach presented here are both valuable and complement each other.

Two more differences are worth mentioning. Unlike in previous analyses of QLSA, our LRE analysis particularly also includes resource requirements of oracle implementations. Finally, this work leverages the use of novel universal automated circuit-generation and resource-counting tools (e.g., Quipper) that are currently being developed for resource-efficient implementations of quantum computation. As such our work advances efforts and techniques toward practical implementations of QLSA and other quantum algorithms.

We find that surprisingly large logical gate counts and circuit depth would be required for QLSA to exceed the performance of a classical linear-system-solving algorithm. Our estimates pertain to the specific problem size \(N=332{,}020{,}680\). This explicit example problem size has been chosen such that QLSA and the best known classical linear-system-solving method are expected to require roughly the same number of operations to solve the problem, assuming equal algorithmic precisions. This is obtained by comparing the corresponding big-O estimates, Eqs. (3) and (2). Thus, beyond this “cross-over point” the quantum algorithm is expected to run faster than any classical linear-system-solving algorithm. Assuming an algorithmic accuracy \(\varepsilon =0.01\), gate counts and circuit depth of order \(10^{29}\) or \(10^{25}\) are found, respectively, depending on whether we take the resource requirements for oracle implementations into account or not, while the numbers of qubits used simultaneously amount to \(10^8\) or 340, respectively. These numbers are several orders of magnitude larger than we had initially expected according to the big-O analyses in [3, 5], indicating that the constant factors (which are not included in the asymptotic big-O estimates) must be large. This indicates that more research is needed about whether asymptotic analysis needs to be supplemented, particularly in comparing quantum to classical algorithms.

To get an idea of our results’ implications, we note that the practicality of implementing a quantum algorithm can strongly be affected by the number of qubits and quantum gates required. For example, the algorithm’s run-time crucially depends on the circuit depth. With circuit depth on the order of \(10^{25}\), and with gate operation times of 1 ns (as an example), the computation would take approx. \(3\times 10^8\) years. And such large resource estimates arise for the solely logical part of the algorithm implementation, i.e., even assuming perfect gate performance and ignoring the additional physical overhead costs (associated with QEC/QC to achieve fault-tolerance and specifics of quantum-computer technology). In practice, the full physical resource estimates typically will be even larger by several orders of magnitude.

One of the main purposes of this paper is to demonstrate how the impressively large LRE numbers arise and to explain the actual bottlenecks in the computation. We find that the dominant resource-consuming part of QLSA is Hamiltonian Simulation and the accompanying quantum-circuit implementations of the oracle queries associated with Hamiltonian matrix A. Indeed, to be able to accurately implement each run of the Hamiltonian evolution as part of QPEA, one requires a large time-splitting factor of order \(10^{12}\) when utilizing the Suzuki-Higher-Order Integrator method including Trotterization [8, 25, 26]. And each single timestep involves numerous oracle queries for matrix A, where each query’s quantum-circuit implementation yields a further factor of several orders of magnitude for gate count. Hence, our LRE results suggest that the resource requirements of QLSA are to a large extent dominated by the numerous oracle A queries and their associated resource demands. Finally, our results also reveal lack of parallelism; the algorithmic structure of QLSA is such that most gates must be performed successively rather than in parallel.

Our LRE results are intended to serve as a baseline for research into the reduction of the logical resource requirements of QLSA. Indeed, we anticipate that our estimates may prove to be conservative as more efficient quantum-computation techniques become available. However, these estimates indicate that, for QLSA to become practical (i.e., its implementation in real world to be viable for relevant problem sizes), a resource reduction by many orders of magnitude is necessary (as is, e.g., suggested by \(\sim \)3\(\times 10^8\) years for the optimistic estimate of the run-time given current knowledge).

This paper is organized as follows. In Sect. 2 we identify the resources to be estimated and expand on our goals and techniques used. In Sect. 3 we describe the structure of QLSA and elaborate on its coarse-grained profiling with respect to resources it consumes. Section 4 demonstrates our quantum implementation of oracles and the corresponding automated resource estimation using our quantum programming language Quipper (and compiler). Our LRE results are presented in Sect. 5 and further reviewed in Sect. 6. We conclude with a brief summary and discussion in Sect. 7.

QLSA computes the solution of a system of linear equations, \(A{\mathbf {x}}={\mathbf {b}}\), where A is a Hermitian \(N\times N\) matrix over \({\mathbb {C}}\) and \({\mathbf {x}},{\mathbf {b}}\in {\mathbb {C}}^N\). For this purpose, the (classical) linear system is converted into the corresponding quantum-theoretic analogue, \(A\left| x\right\rangle =\left| b\right\rangle \), where \(\left| x\right\rangle , \left| b\right\rangle \) are vectors in a Hilbert space \({\mathscr {H}}=({\mathbb {C}}^2)^{\otimes n}\) corresponding to \(n=\lceil \log _2N\rceil \) qubits and A is a Hermitian operator on \({\mathscr {H}}\). Note that, if A is not Hermitian, we can define \({\bar{A}}:=\bigl ({\begin{matrix} 0&{}A\\ A^\dagger &{}0 \end{matrix}} \bigr ), {\bar{\mathbf{b}}}:= ({\mathbf {b}},0)^T\), and \({\bar{\mathbf{x}}}:= (0,{\mathbf {x}})^T\), and restate the problem as \({\bar{A}}{\bar{\mathbf{x}}}={\bar{\mathbf{b}}}\) with a Hermitian \(2N\times 2N\) matrix \({\bar{A}}\) and \({\bar{\mathbf{x}}},{\bar{\mathbf{b}}}\in {\mathbb {C}}^{2N}\).

The basic idea of QLSA has been outlined in the Introduction. In what follows, we illustrate the structure of QLSA including the recently proposed generalization [5] in more detail. In particular, we expand on its coarse-grained profiling with respect to resources it consumes. Our focus in this section is the implementation of the bare algorithm, which accounts for oracles only in terms of the number of times they are queried. The actual quantum-circuit implementation of oracles is presented in Sect. 4. Our overall LRE results are summarized in Sect. 5.

We analyze a concrete example which was demonstrated as an important QLSA application of high practical relevance in [5]: the linear system \(A{\mathbf {x}}={\mathbf {b}}\) arising from solving Maxwell’s equations to determine the electromagnetic scattering cross section of a specified target object via the Finite-Element Method (FEM) [23]. Applied in sciences and engineering as a numerical technique for finding approximate solutions to boundary-value problems for differential equations, FEM often yields linear systems \(A{\mathbf {x}}={\mathbf {b}}\) with highly sparse matrices—a necessary condition for QLSA. The FEM approach to solving Maxwell’s equations for scattering of electromagnetic waves off an object, as demonstrated in [5, 23, 24], introduces a discretization by breaking up the computational domain into small volume elements and applying boundary conditions at neighboring elements. Using finite-element edge basis vectors [24], the system of differential Maxwell’s equations is thereby transformed into a sparse linear system. The matrix A and vector \({\mathbf {b}}\) comprise information about the scattering object; they can be derived, and efficiently computed, from a functional that depends only on the discretization chosen and the boundary conditions which account for the scattering geometry. For details, see [5] and [23, 24] including its supplementary material.

Within the scope of the PLATO project, we analyzed a 2D toy-problem given by scattering of a linearly polarized plane electromagnetic wave \({{\varvec{E}}}(x,y)=E_0 {{\varvec{p}}}\exp [i({{\varvec{k}}}\cdot {{\varvec{r}}}-\omega t)]\), with magnitude \(E_0\), frequency \(\omega \), wave vector \({{\varvec{k}}}=k(\cos \theta {{\varvec{e}}_x}+ \sin \theta {{\varvec{e}}_y})\), and polarization unit vector \({{\varvec{p}}}={{\varvec{e}}_z}\times {{\varvec{k}}}/k\), while \({{\varvec{r}}}=x{{\varvec{e}}_x}+ y{{\varvec{e}}_y}\) is the position, off a metallic object with a 2-dimensional scattering geometry. The scattering region can have any arbitrary design. A simple square shape was specified for our example problem, whose edges are parallel (or perpendicular) to the Cartesian x-y plane axes, and an incident field propagating in x-direction (\(\theta =0\)) toward the square, as illustrated in Fig. 1. The receiver polarization, needed to calculate the far-field radar cross section of the scattered waves, has been assumed to be parallel to the polarization of the incident field.

For the sake of simplicity, for FEM analysis we used a two-dimensional uniform finite-element mesh with square finite elements. Note that QLSA requires the matrix elements to be efficiently computable, a constraint which restricts the class of FEM meshes that can be employed. As a result of the local nature of the finite-element expansion of the scattering problem, the corresponding linear system has a highly sparse matrix A. For meshes with rectangular finite elements, the maximum number of nonzero elements in each row of A (i.e., sparseness) is \(d=7\). Moreover, for regular grids, such as used for our analysis, we obtain a banded sparse matrix A, with a total of \(N_b=9\) bands.

The actual instructions for computing the elements of the linear system’s matrix A and vector \({\mathbf {b}}\), as well as of the vector whose overlap with the solution \({\mathbf {x}}\) is used to calculate the far-field radar cross section (see Sect. 3.3), are specified in our Quipper code for QLSA, see [18, 19]. The metallic scattering region is thereby given in terms of an array of scatteringnodes denoted as “scatteringnodes.” Here we briefly summarize the FEM dimensions and the values of all other system parameters that are necessary to reproduce the analysis. For all other details, we refer the reader to our QLSA’s Quipper code and its documentation in [18, 19].

The total number of FEM vertices in x and y dimensions were \(n_x=12{,}885\) and \(n_y=12{,}885\), respectively, yielding \(N=n_x(n_y-1)+n_y(n_x-1)=332{,}020{,}680\) for the total number of FEM edges, which thus determines the number of edge basis vectors, and hence also the size of the linear system, and in particular the size of the \(N\times N\) matrix A. The lengths of FEM edges in x and y dimensions were \(l_x=0.1m\) and \(l_y=0.1m\), respectively. The analyzed 2D scattering object was a square with edge length \(L=2\lambda \), which in our analysis was placed right in the center of the FEM grid. In our Quipper code for QLSA [18, 19] it is represented by the array “scatteringnodes” containing the corner vertices of the scattering region. The dimensions of the scattering region can also be expressed in terms of the number of vertices in x and y directions; using \(\lambda =1m\) (see below), the scatterer was given by a \(200\times 200\) square area of vertices. The incident and scattered field parameters were specified as follows. The incident field amplitude, wave number and angle of incidence were set \(E_0=1.0\, V/m, k=2\pi \, m^{-1}\) (implying wavelength \(\lambda =1m\)) and \(\theta =0\), respectively. The receiver (for scattered field detection) was assumed to have the same polarization direction as the incident field and located along the x-axis (at angle \(\phi =0\)). The task of QLSA is to compute the far-field radar cross section with a precision specified in terms of the multiplicative error bound \(\varepsilon =0.01\).

Finally, we remark that our example analysis does not include matrix preconditioning that was also proposed in [5] to expand the number of problems that can achieve exponential speedup over classical linear-system algorithms. With no preconditioning, condition numbers of the linear-system matrices representing a finite-element discretization of a boundary-value problem typically scale worse than poly-log(N), which would be necessary to attain a quantum advantage over classical algorithms. Indeed, as was rigorously proven in [27, 28], FEM matrix condition numbers are generally bounded from above by \(O(N^{2/n})\) for \(n\ge 3\) and by \({\widetilde{O}}(N)\) for \(n=2\), with n the number of dimensions of the problem. For regular meshes, the bound \(O(N^{2/n})\) is valid for all \(n\ge 2\). In our 2D toy-problem, \(n=2\) and the mesh is regular, implying that the condition number is bounded by O(N). However, we used the much smaller value \(\kappa = 10^4\) from IARPA GFI to perform our LRE. This “guess” can be motivated by an estimate for the lower bound of \(\kappa \) that we obtained numerically.⁸

The generalized QLSA [5] is based on two well-known quantum algorithm techniques: (1) Quantum Phase Estimation Algorithm (QPEA) [6, 7], which uses Quantum Fourier Transform (QFT) [1] as well as Hamiltonian Simulation (HS) [8] as quantum computational primitives, and (2) Quantum Amplitude Estimation Algorithm (QAEA) [22], which uses Grover’s search-algorithm primitive. The purpose of QPEA, as part of QLSA, is to gain information about the eigenvalues of the matrix A and move them into a quantum register. The purpose of the QAEA procedure is to avoid the use of nondeterministic (nonunitary) measurement and postselection processes by estimating the quantum amplitudes of the desired parts of quantum states, which occur as superpositions of a “good” part and a “bad” part.⁹

QLSA requires several quantum registers of various sizes, which depend on the problem size N and/or the precision \(\varepsilon \) to which the solution is to be computed. We denote the jth quantum register by \(R_j\), its size by \(n_j\), and the quantum state corresponding to register \(R_j\) by \(\left| \psi \right\rangle _j\) (where \(\psi \) is a label for the state). The following Table 1 lists all logical qubit registers that are employed by QLSA, specified by their size as well as purpose. The register size values chosen (provided in GFI within the scope of IARPA QCS program) correspond to the problem size \(N=332{,}020{,}680\) and algorithm precision \(\varepsilon =0.01\).

For example, the choice \(n_0=\lceil \log _2 M\rceil =14\) for the size of the QAE control register can be explained as follows. According to the error analysis of Theorem 12 in [22], using QAEA the modulus squared \(0\le \alpha \le 1\) of a quantum amplitude can be estimated within \(\pm \varepsilon \alpha \) of its correct value¹⁰ with a probability at least \(8/\pi ^2\) for \(k=1\) and with a probability greater than \(1-\frac{1}{2(k-1)}\) for \(k\ge 2\), if the QAE control register’s Hilbert space dimension M is chosen such that (see [22])where \({\tilde{\alpha }}~(0\le {\tilde{\alpha }} \le 1)\) denotes the output of QAEA. Moreover, if \(\alpha =0\) then \({\tilde{\alpha }}=0\) with certainty, and if \(\alpha =1\) and M is even, then \({\tilde{\alpha }}=1\) with certainty. Corollary (4) can be viewed as a requirement used to determine the necessary value of M, yielding (for \(\alpha \not =0\))The RHS of this expression is strictly decreasing, tending to \(\frac{k\pi }{\sqrt{\varepsilon \alpha }}\) as \(\alpha \) becomes close to 1, whereas for \(\alpha \ll 1\) we have \(M\ge \lceil \frac{k\pi }{\varepsilon \sqrt{\alpha }}[(1-\frac{\alpha }{2})+(1-\frac{\alpha -\varepsilon }{2})]\rceil = \lceil \frac{2k\pi }{\varepsilon \sqrt{\alpha }}\rceil \). Hence, we take \(M\ge \lceil \frac{2k\pi }{\varepsilon \sqrt{\alpha }}\rceil \), so as to account for all possibilities. Moreover, we want QAEA to succeed with a probability close to 1, allowing failure only with a small error probability \(\wp _{\mathrm{{err}}}\). According to Theorem 12 in [22], this indeed can be achieved when \(1-\frac{1}{2(k-1)}\ge 1-\wp _{\mathrm{{err}}}\), i.e., for \(k\ge \lceil 1+\frac{1}{2\wp _{\mathrm{{err}}}}\rceil \), and thus forWhile we may assume any value for the failure probability, for the sake of simplicity we here choose \(\wp _{\mathrm{{err}}}=\varepsilon \), which is also the desired precision of QLSA. Unless \(\alpha \) is very small, this justifies our choice \(M=2^{\lceil \log _2( 1/{\varepsilon ^2)}\rceil }\). A similar requirement for the value of M was also proposed in the supplementary material of [5]. In our example computation, \(\varepsilon =0.01\), and so we have \(n_0=14\). Note that small \(\alpha \) values require an even larger value for the QAE control register size in order to ensure that the estimate \({\tilde{\alpha }}\) is within \(\pm \varepsilon \alpha \) of the actual correct value with a success probability greater than \(1-\varepsilon \).

As a first step, QLSA prepares the known quantum state \(\left| b\right\rangle _2=\sum _{j=0}^{N-1} b_j \left| j\right\rangle _2\) in a multiqubit quantum data register \(R_2\) consisting of \(n_2=\lceil \log _2(2N)\rceil \) qubits. This step requires numerous queries (see details below) of an oracle for vector \({\mathbf {b}}\). Moreover, as pointed out in [5], efficient quantum state preparation of arbitrary states is in general not always possible. However, the procedure proposed in [5] can efficiently generate the statewhere the multiqubit data register \(R_2\) contains (as a quantum superposition) the desired arbitrary state \(\left| b\right\rangle \) entangled with a 1 in an auxiliary single-qubit register \(R_6\), as well as a garbage state \(\left| {\tilde{b}}\right\rangle \) (denoted by the tilde) entangled with a 0 in register \(R_6\). To generate the state (7), in addition to data registers \(R_2\) and single-qubit auxiliary register \(R_6\), two further, computational registers \(R_4\) and \(R_5\) are employed, each consisting of \(n_4\) auxiliary qubits. The latter registers are used to store the magnitude and phase components, which in [5] are denoted as \(b_j\) and \(\phi _j\), respectively, that are computed each time the oracle b is queried. Which component (\(j=1,2,3, \dots \)) to query is thereby controlled by data register \(R_2\). The quantum circuit for state preparation [Eq. (7)] is shown in Sect. 3.4.3, Fig. 13. Following the oracle b queries, a controlled-phase gate is applied to the auxiliary single-qubit register \(R_6\), controlled by the calculated value of the phase carried by quantum register \(R_5\); in addition, the single-qubit register \(R_6\) is rotated conditioned on the calculated value of the amplitude carried by quantum register \(R_4\). Uncomputing registers \(R_4\) and \(R_5\) involves further oracle b calls, leaving registers \(R_2\) and \(R_6\) in the state (7) with \(\sin ^2\phi _b= \frac{C_b^2}{2N}\sum _{j=0}^{2N-1}b_j^2\) and \(\cos ^2\phi _b=\frac{1}{2N}\sum _{j=0}^{2N-1}\left( 1-C_b^2b_j^2\right) \), where \(C_b=1/{\text{ max }(b_j)}\), cf. [5].

As a second step, QPEA is employed to acquire information about the eigenvalues \(\lambda _j\) of A and store them in a multiqubit control register \(R_1\) consisting of \(n_1=\lceil \log _2 T\rceil \) qubits, where the parameter T characterizes the precision of the QPEA subroutine and is specified in Table 1. This high-level step consists of several hierarchy levels of lower-level subroutines decomposing it down to a fine-grained structure involving only elementary gates. More specifically, controlled Hamiltonian evolution \(\sum _{\tau =0}^{T-1}\left( \left| \tau \right\rangle \left\langle \tau \right| \right) _1\otimes \left[ \exp (-iA\tau t_0/T)\right] _2\otimes \mathbbm {1}_6\) with A as the Hamiltonian is applied to quantum state \(\left| \phi \right\rangle _1\otimes \left| b_T\right\rangle _{2,6}\). Here, similar to the presentation in [3], a time constant \(t_0\) such that \(t=\tau t_0/T\le t_0\) has been introduced for the purpose of minimizing the error for a given condition number \(\kappa \) and matrix norm \(\Vert A\Vert \). As shown in [3], for the QPEA to be accurate up to error \(O(\varepsilon )\), we must have \(t_0\sim O({\kappa }/{\varepsilon })\) if \(\Vert A\Vert \sim O(1)\). Accordingly, we define \(t_0:= \Vert A\Vert \kappa /\varepsilon \). The application of \(\exp (-iA\tau t_0/T)\) on the data register \(R_2\) is thereby controlled by \(n_1\)-qubit control register \(R_1\) prepared in state \(\left| \phi \right\rangle _1=H^{\otimes n_1}\left| 0\right\rangle ^{\otimes n_1}=\frac{1}{\sqrt{T}}\sum _{\tau =0}^{T-1}\left| \tau \right\rangle _1\) (with H denoting the Hadamard gate). Controlled Hamiltonian evolution is subsequently followed by a QFT of register \(R_1\) to complete QPEA.

The Hamiltonian quantum state evolution is accomplished by multiquerying an oracle for matrix A and HS techniques [8], which particularly include the decomposition of the Hamiltonian matrix into a sumof submatrices, each of which ought to be 1-sparse, as well as the Suzuki-Higher-Order Integrator method and Trotterization [25, 26]. In the general case, an arbitrary sparse matrix A with sparseness d can be decomposed into \(m=6d^2~1\)-sparse matrices \(A_j\) using the graph-coloring method, see [8]. However, a much simpler decomposition is possible for the toy-problem example considered in this work. Indeed, a uniform finite-element grid has been used to analyze the problem specified in the GFI. For uniform finite-element grids the matrix A is banded; furthermore, the number and location of the bands is given by the geometry of the scattering problem. Hence, to decompose the Hamiltonian matrix [Eq. (8)], the simplest way do so is to break it up by band into \(m=N_b\) submatrices, with \(A_j\) denoting the jth nonzero band of matrix A, and \(N_b\) denoting the overall number of its bands. For the square finite-element grid used in the analyzed example, \(N_b = 9\). Moreover, because the locations of the bands are known, this decomposition method requires only time of order O(1). Having the matrix decomposition (8), it is then necessary to implement the application of each individual one-sparse Hamiltonian from this decomposition to the actual quantum state of the data register \(R_2\). This “Hamiltonian circuit” can be derived by a procedure resembling the techniques of quantum-random-walk algorithm [30] and is discussed in more detail in Sect. 3.4.5.

After QPEA has been accomplished including the QFT of register \(R_1\), the joined quantum state of registers \(R_1, R_2\) and \(R_6\) becomes, approximately,where \(\lambda _j\) and \(\left| u_j\right\rangle \) are the eigenvalues and eigenvectors of A, respectively, and \(\left| b\right\rangle _2=\sum _{j=1}^N\beta _j\left| u_j\right\rangle _2\) and \(\left| {\tilde{b}}\right\rangle _2=\sum _{j=1}^N{\tilde{\beta }}_j\left| u_j\right\rangle _2\) are the expansions of quantum states \(\left| b\right\rangle _2\) and \(\left| {\tilde{b}}\right\rangle _2\), respectively, in terms of these eigenvectors, and \({\tilde{\lambda }}_j:=\lambda _jt_0/2\pi \).

As a third step, a further single-qubit ancilla in register \(R_7\) is employed, initially prepared in state \(\left| 0\right\rangle _7\) and then rotated by an angle inversely proportional to the value stored in register \(R_1\), yielding the overall state:where \(C:=1/\kappa \) is chosen such that \(C/\lambda _j<1\) for all j, because of \(\kappa =\lambda _{\mathrm{{max}}}/\lambda _{\mathrm{{min}}}.\)

Finally, the eigenvalues stored in register \(R_1\) are uncomputed, by the inverse QFT of \(R_1\), inverse Hamiltonian evolution on \(R_2\) and \(H^{\otimes n_1}\) on \(R_1\), leaving registers \(R_1, R_2, R_6\), and \(R_7\) in the stateIgnoring register \(R_1\) and collecting all terms that are not entangled with the term \(\left| 1\right\rangle _{6}\otimes \left| 1\right\rangle _{7}\) into a “garbage state” \(\left| \varPhi _0\right\rangle _{2,6,7}\), the common quantum state of registers \(R_2, R_6\), and \(R_7\) can be written as, see [5]:whereis the normalized solution to \(A\left| x\right\rangle =\left| b\right\rangle \) stored in quantum data register \(R_2\) and \(\sin ^2\phi _x:=C^2\sum _{j=1}^N|\beta _j|^2/\lambda ^2_j\). Note that the solution vector [Eq. (13)] in register \(R_2\) is correlated with the value 1 in the auxiliary register \(R_7\). Hence, if register \(R_7\) is measured and the value 1 is found, we know with certainty that the desired solution of the problem is stored in the quantum amplitudes of the quantum state of register \(R_2\), which can then either be revealed by an ensemble measurement (a statistical process requiring the whole procedure to be run many times) or useful information can also be obtained by computing its overlap \(\left| \langle R\left| x\right\rangle \right| ^2\) with a particular (known) state \(\left| R\right\rangle \) (corresponding to a specific vector \({\mathbf {R}}\in {\mathbb {C}}^N\)) that has been prepared in a separate quantum register. To avoid nonunitary postselection processes, CJS-QLSA [5] employs QAEA.¹¹

With respect to the particular application example that has been analyzed here, namely, solving Maxwell’s equations for a scattering problem using the FEM technique, we are interested in the radar scattering cross section (RCS) \(\sigma _{\mathrm{{RCS}}}\), which can be expressed in terms of the modulus squared of a scalar product, \( \sigma _{\mathrm{{RCS}}}=\frac{1}{4\pi }|{\mathbf {R}}\cdot {\mathbf {x}}|^2\), where \({\mathbf {x}}\) is the solution of \(A{\mathbf {x}}={\mathbf {b}}\) and \({\mathbf {R}}\) is an N-dim vector whose components are computed by a 2D surface integral involving the corresponding edge basis vectors and the radar polarization, as outlined in detail in [5]. Thus, to obtain the cross section using QLSA, we must compute \( | \left\langle R |x\right\rangle |^2\), where \(\left| R\right\rangle \) is the quantum-theoretic representation of the classical vector \({\mathbf {R}}\). It is important to note that, whereas \(\left| R\right\rangle \) and \(\left| x\right\rangle \) are normalized to 1, the vectors \({\mathbf {R}}\) and \({\mathbf {x}}\) are in general not normalized and carry units. Hence, after computing \( | \left\langle R |x\right\rangle |^2\), units must be restored to obtain \(|{\mathbf {R}}\cdot {\mathbf {x}}|^2\).

As for \(\left| b\right\rangle \), the preparation of the quantum state \(\left| R\right\rangle \) is imperfect. Employing the same preparation procedure that has been used to prepare \(\left| b_T\right\rangle \), but with oracle R instead of oracle b, we can prepare the entangled statewhere the multiqubit quantum data register \(R_3\) consisting of \(n_3=\lceil \log _2(2N)\rceil \) qubits contains (as a quantum superposition) the desired arbitrary state \(\left| R\right\rangle \) entangled with value 1 in an auxiliary single-qubit register \(R_8\), as well as a garbage state \(\left| {\tilde{R}}\right\rangle \) (denoted by the tilde) entangled with value 0 in register \(R_8\). Moreover, the amplitudes squared are given as \(\sin ^2\phi _r= \frac{C_R^2}{2N}\sum _{j=0}^{2N-1}R_j^2\) and \(\cos ^2\phi _r=\frac{1}{2N}\sum _{j=0}^{2N-1}\left( 1-C_R^2R_j^2\right) \), where \(C_R=1/{\text{ max }(R_j)}\), cf. [5]. As outlined in [5], the state (14) is adjoined to state (12) along with a further ancilla qubit in single-qubit register \(R_9\) that has been initialized to state \(\left| 0\right\rangle _9\). Then, a Hadamard gate is applied to the ancilla qubit in register \(R_9\) and a controlled swap operation is performed between registers \(R_2\) and \(R_3\) controlled on the value of the ancilla qubit in register \(R_9\), which finally is followed by a second Hadamard transformation of the ancilla qubit in register \(R_9\). After a few simple classical transformations, the algorithm can compute the scalar product between \(\left| x\right\rangle \) and \(\left| R\right\rangle \) as, cf. [5]:where \(P_{1110}\) and \(P_{1111}\) denote the probability of measuring a “1” in the three ancilla registers \(R_6, R_7\) and \(R_8\) and a “0” or “1” in ancilla register \(R_9\), respectively. Finally, after restoring the units to the normalized output of QLSA, the RCS in terms of quantities received from the quantum computation is, cf. [5]:where \(\sin \phi _{r0}:=P^{\frac{1}{2}}_{1110}\sin \phi _r\) and \(\sin \phi _{r1}:=P^{\frac{1}{2}}_{1111}\sin \phi _r\).

It is important to note that, because all the employed state preparation and linear-system-solving operations are unitary, the four amplitudes \(\sin \phi _b, \sin \phi _x, \sin \phi _{r0}\) and \(\sin \phi _{r1}\) that are needed for the computation of the RCS according to Eq. (16) can be estimated nearly deterministically (with error \(\varepsilon \)) using QAEA which allows to avoid nested nondeterministic subroutines involving postselection.¹² Yet, there is a small probability of failure, which means that QLSA can occasionally output an estimate \({\tilde{\sigma }}_{\mathrm{{RCS}}}\) that is not within the desired precision range of the actual correct value \(\sigma _{\mathrm{{RCS}}}\). The failure probability is generally always nonzero but can be made negligible.¹³

The high-level structure of QLSA [5] is captured by a tree diagram depicted in Fig. 2. It consists of several high-level subroutines hierarchically comprising (i)‘ ‘Amplitude Estimation” (first level), (ii) “State Preparation” and “Solve for x” (second level), (iii) “Hamiltonian Simulation” (third level), and several further sublevel subroutines, such as “HsimKernel” and “Hmag” that are used as part of HS. Figure 2 illustrates the coarse-grained profiling of QLSA for the purpose of an accurate LRE of the algorithm, demonstrating the use of repetitive patterns, i.e., templates representing algorithmic building blocks that are reused frequently. Representing each algorithmic building block in terms of a quantum circuit thus yields a step-by-step hierarchical circuit decomposition of the whole algorithm down to elementary quantum gates and measurements. The cost of each algorithmic building block is thereby measured in terms of the number of calls of lower-level subroutines or directly in terms of the number of specified elementary gates, data qubits, ancilla uses, etc.

The programming language Quipper [14, 15] is a domain-specific, higher-order, functional language for quantum computation. A snippet of Quipper code is essentially the formal description of a circuit construction. Being higher-order, it permits the manipulation of circuits as first-class citizens. Quipper is embedded in the host-language Haskell and builds upon the work of [31‐35].

In Quipper, a circuit is given as a typed procedure with an input type and an output type. For example, the Hadamard and the NOT gates are typed with

They input a qubit and output a qubit. The keyword Circ is of importance: it says that when executed, the function will construct a circuit (in this case, a trivial circuit with only one gate).

Quantum data-types in Quipper are recursively generated: Qubit is the type of quantum bits; (A,B) is a pair of an element of type A and an element of type B; (A,B,C) is a 3-tuple; () is the unit-type: the type of the empty tuple; [A] is a list of elements of type A.

If a program has multiple inputs, we can either place them in a tuple or use the curry notation (\(\rightarrow \)). For instance, the program

takes three inputs of type A, B and C and outputs a result of type D, while at the same time producing a circuit. Using the curry notation, the same program can also be written as

where D is the type of the output. We use the program by placing the inputs on the right, in order:

The meaning is the following: prog a is a function of type B -> C -> Circ D, waiting for the rest of the arguments; prog a b is a function of type C -> Circ D, waiting for the last argument; finally, prog a b c is the fully applied program. If a program has no input, it has simply the type Circ B if B is the type of its output.

Using the introduced notation, we can type the controlled-NOT gate:

and initialization and measure:

To illustrate explicitly how quantum circuits are generated with Quipper, let us use a well-known example: the EPR-pair generation, defined by the transformation \(\left| 0\right\rangle \otimes \left| 0\right\rangle \rightarrow 1/\sqrt{2}\left( \left| 0\right\rangle \otimes \left| 0\right\rangle +\left| 1\right\rangle \otimes \left| 1\right\rangle \right) \). The Quipper code which creates such an EPR pair can be written as follows:

The generated circuit is presented in Fig. 20, and each line is shown with its corresponding action. Line 1 defines the type of the piece of code: Circ means that the program generates a circuit, and (Qubit,Qubit) indicates that two quantum bits are going to be returned. Line 2 starts the actual coding of the program. Lines 3 to 6 are the instructions generating new quantum bits and performing gate operations on them, while Line 7 states that the newly created quantum bits q1 and q2 are returned to the user.

Quipper is a higher-order language, that is, functions can be inputs and outputs of other functions. This allows one to build quantum-specific circuit-manipulation operators. For example,

inputs a circuit, a qubit, and output the same circuit controlled with the qubit. It fails at run-time if some noncontrollable gates were used. So the following two lines are equivalent:

The function classical \(\_\) to \(\_\) reversible, presented in Section 4.4, is another example of high-level operator.

The previous section showed how a program in Quipper is essentially a description of a circuit. The execution of a given program will generate a circuit, and performing logical resource estimation is simply achieved by completing the program with a gate-count operation at the end of the circuit-generation process. Instead of, say, sending the gates to a quantum co-processor, the program merely counts them out. Quipper comes equipped with this functionality.

An oracle in quantum computation is a description of a classical structure on which the algorithm acts: a graph, a matrix, etc. An oracle is then usually presented in the form of a regular, classical function f from n to m bits encoding the problem. It is left to the reader to make this function into the unitary of Fig. 21 acting on quantum bits.

Provided that the function f is given as a procedure and not as a mere truth table, there is a known efficient strategy to build \(U_f\) out of the description of f [36].

The strategy consists in two steps. First, construct the circuit \(T_f\) of Fig. 22. Such a circuit can be built in a compositional manner as follows. Suppose that f is given in term of g and h: \(f(x) = h(g(x))\). Then, provided that \(T_g\) and \(T_h\) are already built, \(T_f\) is the circuit in Fig. 23. NOT and AND are enough to write any Boolean function f: these are the base cases of the construction. The gate \(T_{\mathrm{NOT}}\) is the controlled-NOT, and the gate \(T_{\mathrm{AND}}\) is the Toffoli gate.

Once the circuit \(T_f\) is built, the circuit \(U_f\), shown in Fig. 24 is simply the composition of \(T_f\), a fanout, followed with the inverse of \(T_f\). At the end of the computation, all the ancillas are back to 0: they are not entangled anymore and can be discarded without jeopardizing the overall unitarity of \(U_f\).

As the transformation sending a procedure f to a circuit \(T_f\) is compositional, it can be automated. We are using a feature of the host-language Haskell to perform this transformation automatically: Template Haskell. In a nutshell, it allows one to manipulate a piece of code within the language, produce a new piece of code and inject it in the program code. Another (slightly misleading) way of saying it is that it is a type-safe method for macros. Regardless, it allows one to do exactly what we showed in the previous section: function composition is transformed into circuit composition, and every subfunction \(\texttt {f}:A\rightarrow B\) is replaced with its corresponding circuit, whose type¹⁴ is \(A \rightarrow \texttt {Circ}~B\): a function that inputs an object of type A, builds a (piece of) circuit, and outputs B. For example, the code

computing the conjunction of the three input variables x, y and z is turned into a function

computing the circuit in Fig. 25. Notice how the input wires are not touched and how the result is just one among many output wires. One can as easily encode the addition using binary integer.

As Quipper is a high-level language, it flawlessly allows circuit manipulation. In particular, one can perform the meta-operation classical_to_reversible sending the circuit \(T_f\) to \(U_f\), of typeprovided that A and B are essentially lists of qubits, and that \(T_f\) only consists of classical reversible gates: NOTs, c-NOTs, cc-NOTs, etc.

In the case of our my \(\_\) and function, it produces the circuit in Fig. 26 of the correct shape. One can easily check that the wire out is correctly set.

The oracles of QLSA were given to us as a set of MATLAB functions as part of the IARPA QCS program GFI. These functions computed the matrix A and the vectors b and R of [5]. They were not using any particular library: directly translating them into Haskell was a straightforward operation. As the MATLAB code came with a few tests to validate the implementation, by running them in Haskell we were able to validate our translation.

The main difficulty was not to translate the MATLAB code into Quipper, but rather to encode by hand the real arithmetic and analytic functions that were used. Figure 27 shows a snippet of translated Haskell code: it is a nontrivial operation using trigonometric functions. Another part of the oracle is also using arctan.

We made heavy use of the subroutine facility of Quipper: All of the major operations are boxed, that is, appear only once in the internal structure representing the circuit. This allows manageable processing (e.g., printing, or resource counting). As an example, the circuit for Oracle R of QLSA is shown in Fig. 28.

Our strategy for generating circuits with Template Haskell is efficient in the following sense: the size of the generated quantum circuit is exactly the same as the number of steps in the classical program. For example, if the classical computation consists of n conjunctions and m negations, the generated quantum circuit consists of n Toffoli gates and m CNOT gates.

The advantage of this technique is that it is fully general: with this procedure, any classical computation can be turned into an oracle in an efficient manner.

The reason why we think it is possible to achieve the mentioned moderate optimization is the following. Although the oracles we deal with in this work are specified and tailored to the particular problem we have been analyzing, they are also general in the sense that they are made of smaller algorithms (e.g., adders, multipliers ...). The reversible versions of these algorithms have been studied for a long time, and quite efficient proposals have been made. An analysis of the involved resources shows that for the addition of n-bit integers, the number of gates involved in the automatically generated adder gate \(T_f\) is \(\lesssim 25n\) and the number of ancillas is \(\lesssim 8n\). A hand-made reversible adder can be constructed [37] with, respectively, \(\lesssim 5n\) gates and \(\le n\) ancillas. If one found a way to reuse these circuits in place of our automatically generated adders, it would reduce the oracle sizes. However, it could only do so by a relatively small factor; the total number of gates would still be daunting.

Our LRE results shown in Table 2 suggest that the resource requirements of QLSA are to a large extent dominated by the quantum-circuit implementation of the numerous oracle A queries and their associated resource demands. Indeed, accounting for oracle implementation costs yields resource counts which are by several orders of magnitude larger than those if oracle costs are excluded. While Oracle A queries have only slightly lower implementation costs than Oracle b and Oracle R queries, it is the number of queries that makes a substantial difference. As clearly illustrated in Fig. 2, Oracle A (required to implement the Hamiltonian transformation \(e^{iAt}\) with \(t\le t_0\sim O(\kappa /\varepsilon )\)) is queried by many orders of magnitude more frequently than Oracles b and R, which are needed only for preparation of the quantum states \(\left| b\right\rangle \) and \(\left| R\right\rangle \) corresponding to the column vectors \({\mathbf {b}}, {\mathbf {R}}\in {\mathbb {C}}^N\). Hence, the overall LRE of the algorithm depends very strongly on the Oracle A implementation. However, note that Oracles b and R contribute most to circuit width due to the vast number of ancilla qubits (\(\sim \)3\(\times 10^8\)) they employ at a time, see Table 10 in “Appendix 3.”

The LRE for the bare algorithm, i.e., with oracle queries and “IntegerInverse” function regarded as “for free” (excluding their resource costs), amounts to the order of magnitude \(10^{25}\) for gate count and circuit depth—still a surprisingly high number. In what follows, we explain how these large numbers arise, expanding on all the factors in more detail that yield a significant contribution to resource demands. To do so, we make use of Fig. 2.

QLSA’s LRE is dominated by series of nested loops consisting of numerous iterative operations, see Fig. 2. The major iteration of circuits with similar resource demands occurs due to the Suzuki-Higher-Order Integrator method including a Trotterization with a large time-splitting factor of order \(10^{12}\) to accurately implement each run of the HS as part of QPEA. Indeed, each single call of “HamiltonianSimulation” yields the iteration factor \(r=2.5\times 10^{12}\). This subroutine is called twice during the “Solve_x” procedure, and the latter is furthermore employed twice within the (controlled) Grover iterators in three of the four QAEAs. There are \(\sum _{j=0}^{n_0-1} 2^j=2^{n_0}-1=16{,}383\) controlled Grover iterators employed within each of the four QAEAs. Hence, the “HamiltonianSimulation” subroutine is employed \( (2^{n_0}-1)\times 4\times 3=196{,}596\approx 2\times 10^5\) number of times altogether. Because each of its calls uses Trotterization with time-splitting factor \(2.5\times 10^{12}\) and a Suzuki-Higher-Order Integrator decomposition with order \(k=2\) involving a further additional factor 5, we already get the factor \(\sim \)2.5\(\times 10^{18}\). Moreover, the lowest-order Suzuki operator is a product of \(2\times N_b=18\) one-sparse Hamiltonian propagator terms (where \(N_b=9\) is the number of bands in matrix A); each such term calls the “HsimKernel” function, with “band” and “timestep” as its runtime parameters. In addition, each call of HsimKernel employs Oracle A six times and furthermore involves 24 applications of the procedure “Hmag” controlled by the time register \(R_1\). Thus, in total QLSA involves \(6\times 18\times 2.5\times 10^{18}\approx 2.7\times 10^{20}\) Oracle A queries and \(24\times 18\times 2.5\times 10^{18}\approx 10^{21}\) calls of controlled Hmag. Hence, even if subroutine Hmag consisted of a single gate and oracle A queries were for free, we would already have approx. \(10^{21}\) for gate count and circuit depth.

However, Hmag is a subalgorithm consisting of further subcircuits to implement the application of the magnitude component of a particular one-sparse Hamiltonian term to an arbitrary state. It consists of several W gates, Toffolis and controlled rotations. Hence, a further increase of the order of magnitude is incurred by various decompositions of multicontrolled gates and/or rotation gates into the elementary set of fault-tolerant gates \(\{H, S, T, X, Z, \text{ CNOT }\}\), using the well-known decomposition rules outlined in “Appendix 2” (e.g., optimal-depth decompositions for Toffoli [38] and for controlled single-qubit rotations [39‐42]). In our analysis, this yields a further factor \(\sim \)10\(^4\). Thus, even if we exclude oracle costs, we have \(10^{21} \times 10^4 = 10^{25}\) for gate count and circuit depth for the bare algorithm, simply because of a large number of iterative processes (due to Trotterization and Grover-iterate-based QAE) combined with decompositions of higher-level circuits (such as multicontrolled NOTs) into elementary gates and single-qubit rotation decompositions (factors \(\sim \)10\(^2\)–10\(^4\)).

If we include the oracle implementation costs, the dominant contribution to LRE is that of Oracle A calls, because oracle A is queried by a factor \(\sim \)10\(^{15}\) more frequently than Oracle b and even by a larger factor than Oracle R. Each Oracle A query’s circuit implementation has a gate count and circuit depth of order \(\sim \)2.5\(\times 10^8\), see “Appendix 3.” Having approx. \(2.7\times 10^{20}\) Oracle A queries, the LRE thus amounts to the order of magnitude \(\sim \)10\(^{29}\).

Let us briefly summarize the nested loops of QLSA that dominate the resource demands, while other computational components have negligible contributions. The dominant contributions result from those series of nested loops which include Hamiltonian Simulation as the most resource-demanding bottleneck. The outer loops in these series are the first-level QAEA subroutines to find estimates for \(\phi _x, \phi _{r0}\) and \(\phi _{r1}\), each involving \(2^{n_0}-1=16{,}383\) controlled Grover iterators. Each Grover iterator involves several implementations of Hamiltonian Simulation based on Suzuki-Higher-Order Integrator decomposition and Trotterization with \(r\approx 10^{12}\) time-splitting slices. Each Trotter slice involves iterating over each matrix band whereby the corresponding part of Hamiltonian evolution is applied to the input state. Finally, for each band several oracle A implementations are required to compute the corresponding matrix elements, which moreover employs several arithmetic operations, each of which themselves require loops with computational effort scaling polynomially with the number of bits in precision.

As pointed out in the Introduction, we provide the first concrete resource estimation for QLSA in contrast to the previous analyses [3, 5] which estimated the run-time of QLSA only in terms of its asymptotic behavior using the “big-O” characterization. As the latter is supposed to give some hints on how the size of the circuit evolves with growing parameters, it is interesting to compare our concrete results for gate count and circuit depth with what one would expect according to the rough estimate suggested by the big-O (complexity) analysis. The big-O estimations proposed by Harrow et al. [3] and Clader et al. [5] have been briefly discussed in the Introduction and are given in Eqs. (1) and (3), respectively.

Complexity-wise, the parameters taken into account in the big-O estimations are the size N of the square matrix A, the condition number \(\kappa \) of A, the sparseness d which is the number of nonzero entries per row/column in A, and the desired algorithmic accuracy given as error bound \(\varepsilon \). The choice of parameters made in this paper fixes these values to \(N=332{,}020{,}680, \kappa =10^4, d=7\), and \(\varepsilon =10^{-2}\). If one plugs them into Eqs. (1) and (3), one gets, respectively, \(\sim \)4\(\times 10^{12}\) and \(\sim \)2\(\times 10^{12}\).

Although these numbers are large, they are not even close to compare with our estimates. This is due to the way a big-O estimate is constructed: it only focuses on a certain set of parameters, the other ones being roughly independent of the chosen set. Indeed, the “function” provided as big-O estimate is only giving a trend on how the estimated quantity behaves as the chosen set of parameters goes to infinity (or to zero, in the case of \(\varepsilon \)). Hence, only the limiting behavior of the estimate can be predicted with high accuracy, when the chosen relevant parameters it depends on tend toward particular values or infinity, while the estimate is very rough for other values of these parameter. In particular, a big-O estimate is hiding a set of constant factors, which are unknown. In the case of QLSA, our LRE analysis does not reveal a trend, it only gives one point. Nonetheless, it shows that these factors are extremely large, and that they must be carefully analyzed and otherwise taken into account for any potentially practical use of the algorithm.

Although the (unknown) constant factors implied by big-O complexity cannot be inferred from our LRE results obtained for just a single problem size, we can nevertheless consider which steps in the algorithm are likely to contribute most to these factors. With our fine-grained approach we found that, if excluding the oracle A resources, the accrued circuit depth \(\sim \)10\(^{25}\) is roughly equal to \(3\times (2^{n_0}-1)\) Grover iterations (as part of amplitude estimation loops for \(\phi _x, \phi _{r0}\) and \(\phi _{r1}\)) times \(4\times (2N_b)\times 5\times 2.5\times 10^{12}\) for the number of exponentials needed to implement the Suzuki-Trotter expansion (as part of implementing HS, which is employed twice in Solve_x that is again employed twice in each Grover iterator) times a factor \(\sim \)24\(\times 10^4\) coming about from the circuits to implement, for each particular \(A_j\) in the decomposition [Eq. (8)], the corresponding part of Hamiltonian state transformation. In terms of CJS big-O complexity the circuit depth is \({\widetilde{O}}\left( \kappa {}d^7\log (N)/\varepsilon ^2 \right) \), which comes from \({\widetilde{O}}\left( 1/\varepsilon \right) \) QAE Grover iterations,¹⁵ times \({\widetilde{O}}\left( d^4\kappa /\varepsilon \right) \) exponential operator applications to implement the Suzuki-Trotter expansion,¹⁶ times \(O\left( \log N\right) \) oracle A queries to simulate each query to any \(A_j\) in the decomposition [Eq. (8)], times the overhead of \(O(d^3)\) computational steps including \(O(d^2)\) Oracle A queries to estimating the preconditioner M of the linear system in order to prepare the preconditioned state \(M\left| b\right\rangle \), see [5]. Here it is appropriate to note though that the HHL and CJS runtime complexities given in Eqs. (1) and (3), respectively, neglect more slowly growing terms, as indicated by the tilde notation \({\widetilde{O}}(\cdot )\). However, in a comparison with our empirical gate counts we ought to also take those slowly growing terms into account. For instance, there is another factor of \((\kappa d^2/\varepsilon ^2)^{1/4}\approx 3\times 10^2\) contributing to the number of Suzuki-Trotter expansion slices, which was ignored in the \({\widetilde{O}}\) notation for HHL and CJS complexities, while it was accounted for in our LRE. By inspecting and comparing (CJS big-O vs. our LRE) the orders of magnitude of the various contributing terms, we conclude that the big-O complexity is roughly two orders of magnitude off (smaller) from our empirical counts for the Suzuki-Trotter expansion step. As for the QAE steps, our LRE count is \(\sim \)5\(\times 10^4\), which is roughly two orders of magnitude higher than \(O(1/\varepsilon )\) and smaller than \(O(\kappa /\varepsilon )\), suggesting that \(O(1/\varepsilon )\) is too optimistic while \(O(\kappa /\varepsilon )\) is too conservative. Finally, the big-O complexity misses roughly 5 orders of magnitude that our fine-grained approach reveals for the circuit implementation of the Hamiltonian state transformation for each \(A_j\) at the lowest algorithmic level.

In order to understand what caused such large constant factors, we estimated the resources needed to run QLSA for a smaller problem size¹⁷ while keeping the same precision (and therefore the same size for the registers holding the computed values). Specifically, we chose \(N=24\), while we kept the condition number and the error bound at the same values \(\kappa =10^4\) and \(\varepsilon =10^{-2}\), respectively. Despite the fact that the matrix A lost several orders of magnitude in size, the circuit width and depth ended up being of roughly the same order of magnitude as of Table 2.

What our results suggest is that the large constant factors arise as a consequence of the desired precision forcing us into choosing large sizes for the registers, whereas the LRE is not notably impacted by a change in problem size N. This can intuitively be understood as follows. First, the total number of gates required for QLSA’s nonoracle part scales as \(O(\log N)\), cf. Eq. (3); hence, using \(N=24\) in place of \(N=332{,}020{,}680\) suggests an LRE reduction only by a moderate factor \(\sim \)5. Secondly, what matters for the LRE of oracles is also mostly determined by the desired accuracy \(\varepsilon \). Each oracle query essentially computes a single (complex) value corresponding to a particular input from the set of all inputs. The oracles are oblivious to the problem size and to the actual value of each of their inputs. While oracles obtain actual input data from the data register \(R_2\) or \(R_3\), whose size \(n_2=n_3=\log _2(2N)\) clearly depends on N, these are not the ones that crucially determine the oracles’ sizes. What virtually matters for the size of the generated quantum circuit implementing an oracle query, is the size of the computational registers \(R_4\) and \(R_5\) used to compute and hold the output value of each particular oracle query. In our analysis, these registers have size \(n_4=65\), cf. Table 1; they were kept at the same size when computing QLSA’s LRE for the smaller problem size \(N=24\).

Comparing the estimates for the total number of gates and circuit depth reveals a distinct lack of parallelism ¹⁸ in the design of QLSA. As explained earlier, due to the highly repetitive structures of the algorithm primitives used, most of the gates have to be performed sequentially. Indeed, QLSA involves numerous iterative operations. The major iteration of circuits with similar resource requirements occurs due to the Suzuki-Higher-Order Integrator method that also involves Trotterization, which uses a large time-splitting factor of order \(10^{12}\) to accurately implement each run of the Hamiltonian-evolution simulation. In fact, the iteration factor imposed by Trotterization of the Hamiltonian propagator is currently a hard bound on the overall circuit depth and even the total LRE of QLSA, and it crucially depends on the aimed algorithmic precision \(\varepsilon \). The remarks in the following paragraph expand on this issue in more detail.

It is worth emphasizing that the quantum-circuit implementation of the Hamiltonian transformation \(e^{iAt}\) using well-established HS techniques [8] constitutes the actual bottleneck of QLSA. Indeed, this step implies the largest contribution to the overall circuit depth; it is given by the factor \(r\times 5^{k-1} \times (2N_b)\), see Fig. 2, which is imposed by the Suzuki-Higher-Order Integrator method together with Trotterization. According to Eq. (17) and the discussion following it, \(r\sim O\left( (N_b\kappa )^{1+1/{2k}}/ \varepsilon ^{1+1/{k}}\right) \). Thus, the key dependence of the time-splitting factor r is on the condition number \(\kappa \) and the error bound \(\varepsilon \) rather than on problem size N. The dependence on the latter enters only through the number of bands \(N_b\) (in the general case, the number m of submatrices in the decomposition [Eq. (8)]), which can be small even for large matrix sizes, as is the case in our example. This feature explains why we can get similar LRE results for \(N=332{,}020{,}680\) and \(N=24\) if \(\kappa \) and \(\varepsilon \) are kept at the same values for both cases and the number of bands \(N_b\) is small (see above).

It is also important to note that there has been significant recent progress on improving HS techniques. Berry et al. [43] provide a method for simulating Hamiltonian evolution with complexity polynomial in \(\log (1/\varepsilon )\) (with \(\varepsilon \) the allowable error). Even more recent works by Berry et al. [44, 45] improve upon results in [43] providing a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error. Compared to [44], the analysis in [45] yields a near-linear instead of superquadratic dependence on the sparsity d. Moreover, unlike the approach [43], the query complexities derived in [44, 45] are shown to be independent of the number of qubits acted on. Most importantly, all three approaches [43‐45] provide an exponential improvement upon the well-established method [8] that our analysis is based on.¹⁹ To account for these recent achievements, we estimate the impact they may have with reference to the baseline imposed by our LRE results. The modular nature of our LRE approach allows us to do this estimation. The following back-of-the-envelope evaluation shows that, for \(\varepsilon =0.01\), the advanced HS approaches [43, 44] and [45] may offer a potential reduction of circuit depth and overall gate count by orders of magnitude \(10^1\), \(\sim \)10\(^4\) and \(\sim \)10\(^5\), respectively.

Indeed, let us compare the scalings of the total number of one-sparse Hamiltonian-evolution terms required to approximate \(e^{iAt}\) to within error bound \(\varepsilon =0.01\) for the prior approach [8] (used here) and the recent methods [43, 45]. In doing so, we arrive at contrasting for the three approaches [8, 43] and [45], respectively. In the first term, m denotes the number of submatrices in the decomposition [Eq. (8)]; in the general case, \(m=6d^2\), in our toy-problem analysis, \(m=N_b\). In the second and third term, d is the sparsity of A, and n is the number of qubits acted on, while c is a constant. In all three expressions, \(\Vert A\Vert \) is the spectral norm of the Hamiltonian A, which in our toy-problem example is time-independent. As stated in Sect. 3.4.5, for QLSA to be accurate within error bound \(\varepsilon \), we must have \(\Vert A\Vert t\sim O(\kappa /\varepsilon )\), cf. [3]. Using \(\Vert A\Vert t \le \Vert A\Vert t_0=7\times \kappa /\varepsilon \) and the parameter values \(m=N_b=9, k=2, d=7, n=n_2=30\) and \(c\ge 1\), expression (19) yields \(\sim \)7\(\times 10^{13}\), whereas the query complexity estimates (20) and (21) yield \(\gtrsim \)5\(\times 10^{12}\) and \(\sim \)5\(\times 10^8\), respectively. Hence, notably the advanced results in [45] imply that an improvement of our LRE by order of magnitude \(\sim \)10\(^5\) seems feasible.