Quantum oracles for the finite element method

Abstract

In order to assess potential advantages of quantum algorithms that require quantum oracles as subroutines, the careful evaluation of the overall complexity of the oracles themselves is crucial. This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N\times N$ stiffness and mass matrices, which typically emerge in the finite element analysis of elastic structures. Starting from basic quantum adders, we show how to construct the necessary oracles, which require the calculation of polynomials, square root and the implementation of conditional operations. We propose quantum subroutines based on fixed-point arithmetic that, given an $r$-qubit register, construct the oracle using $\mathcal{O}((K+L+N_{\mathrm{geo}}+N_{\mathrm{D}})r)$ ancilla qubits and have a $\mathcal{O}((K+L)r^2+{\log }_2(N_{\mathrm{geo}}+N_{\mathrm{D}}))$ runtime, with $K$ the order at which we truncate the polynomials, $L$ the number of iterations in the Newton-Raphson subroutine for the square root, while $N_{\mathrm{geo}}$ and $N_{\mathrm{D}}$ are the number of hypercuboids used to approximate the geometry and the boundary, respectively. Since in practice $r$ scales as $r=\mathcal{O}({\log }_{2}N)$, and assuming that the other parameters are fixed independently of $N$, this shows that the oracles, while still costly in practice, do not endanger potential polynomial or exponential advantages in $N$.

14+7 pages, 17 figures

References in corpus (11)

• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• On the relationship between continuous- and discrete-time quantum walk
• Preconditioned quantum linear system algorithm
• Halving the cost of quantum addition
• Quantum algorithms and the finite element method
• Fast Quantum Modular Exponentiation
• Quantum arithmetic with the Quantum Fourier Transform
• Quantum Fourier Addition, Simplified to Toffoli Addition
• Calculating response functions of coupled oscillators using quantum phase estimation