arXiv:2504.19827 · SIAM Journal on Scientific Computing

An Implementation of Quantum Oracles for the Finite Element Method

Sven Danz, Tobias Stollenwerk, Alessandro Ciani

Published Jun 1, 2026• 1 citation

Abstract

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 [Formula: see text] 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 [Formula: see text]-qubit register, construct the oracle using [Formula: see text] ancilla qubits and have an [Formula: see text] runtime, with [Formula: see text] the order at which we truncate the polynomials and [Formula: see text] the number of iterations in the Newton–Raphson subroutine for the square root, while [Formula: see text] and [Formula: see text] are the number of hypercuboids used to approximate the geometry and the boundary, respectively. Since in practice [Formula: see text] scales as [Formula: see text], for numbers between 0 and [Formula: see text], and assuming that the other parameters are fixed independently of [Formula: see text], this shows that the oracles, while still costly in practice, do not endanger potential polynomial or exponential advantages in [Formula: see text].

DOI: 10.1137/25m1761513

Related papers

IQFEM: A quantum finite element method for heterogeneous problems with immersed boundaries

Shehara Perera, Yiren Wang, Fehmi Cirak

arXiv:2609.14077Sep 12, 20260 citations

Quantum Matrix Arithmetics with Hamiltonian Evolution

Christopher Kang, Yuan Su

arXiv:2510.06316ACM Transactions on Quantum ComputingAug 8, 20260 citations

Quantum framework for simulating linear PDEs with Robin boundary conditions

Nikita Guseynov, Xiajie Huang, Nana Liu

arXiv:2506.20478Quantum Science and TechnologyJan 27, 20260 citations

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps, Lin Lin, Roel Van Beeumen +1 more

arXiv:2203.10236SIAM Journal on Matrix Analysis and ApplicationsMar 11, 202478 citations

Circuit complexity of quantum access models for encoding classical data

Xiao‐Ming Zhang, Xiao Yuan

arXiv:2311.11365npj Quantum InformationApr 23, 202421 citations

Opening the Black Box inside Grover’s Algorithm

Edwin Miles Stoudenmire, Xavier Waintal

arXiv:2303.11317Physical Review XNov 1, 202427 citations

arXiv:2504.19827 · SIAM Journal on Scientific Computing

An Implementation of Quantum Oracles for the Finite Element Method

Sven Danz, Tobias Stollenwerk, Alessandro Ciani

Published Jun 1, 2026• 1 citation

arXiv HTML PDF

Abstract

DOI: 10.1137/25m1761513

Related papers

IQFEM: A quantum finite element method for heterogeneous problems with immersed boundaries

Shehara Perera, Yiren Wang, Fehmi Cirak

Quantum computing offers the potential to solve computational mechanics problems with a more favourable complexity scaling than classically possible. To realise this potential, a quantum-compatible formulation of the finite element method is essential. We present such a formulation for Poisson problems with spatially varying coefficients on general domains discretised by an immersed uniform Cartesian grid. The resulting banded sparse system matrices are encoded as the sum of diagonal matrices with polynomial entries and their products with shift matrices. The sum of the matrices is formed using the linear combination of unitaries (LCU) technique. The resulting block-encoded system matrix can be implemented using a polylogarithmic number of elementary gates. For immersed boundaries, the block-encoded system matrix is further processed using a diagonal indicator matrix with zeros and ones. The indicator matrix is defined in terms of an integer-valued level-set function composed of simple geometric primitives via Boolean set operations. The required integer operations are computed on the fly using quantum arithmetic. The resulting block-encoded linear system of equations is solved using quantum singular value transformation (QSVT). The overall gate count, including the QSVT, is $O(N_{\text{tot}}^{2/d} \operatorname{polylog}(N_{\text{tot}}))$ , where $d$ is the problem dimension and $N_{\text{tot}}$ the number of grid points. In numerical examples that confirm the theoretical complexity estimates, the solutions converge approximately linearly for immersed problems and quadratically for simply connected domains.Quantum computing offers the potential to solve computational mechanics problems with a more favourable complexity scaling than classically possible. To realise this potential, a quantum-compatible formulation of the finite element method is essential. We present such a formulation for Poisson problems with spatially varying coefficients on general domains discretised by an immersed uniform Cartesian grid. The resulting banded sparse system matrices are encoded as the sum of diagonal matrices with polynomial entries and their products with shift matrices. The sum of the matrices is formed using the linear combination of unitaries (LCU) technique. The resulting block-encoded system matrix can be implemented using a polylogarithmic number of elementary gates. For immersed boundaries, the block-encoded system matrix is further processed using a diagonal indicator matrix with zeros and ones. The indicator matrix is defined in terms of an integer-valued level-set function composed of simple geometric primitives via Boolean set operations. The required integer operations are computed on the fly using quantum arithmetic. The resulting block-encoded linear system of equations is solved using quantum singular value transformation (QSVT). The overall gate count, including the QSVT, is $O(N_{\text{tot}}^{2/d} \operatorname{polylog}(N_{\text{tot}}))$, where $d$ is the problem dimension and $N_{\text{tot}}$ the number of grid points. In numerical examples that confirm the theoretical complexity estimates, the solutions converge approximately linearly for immersed problems and quadratically for simply connected domains.

arXiv:2609.14077Sep 12, 20260 citations

Quantum Matrix Arithmetics with Hamiltonian Evolution

Christopher Kang, Yuan Su

The efficient implementation of matrix arithmetic operations underpins the speedups of many quantum algorithms. We develop a suite of methods to perform matrix arithmetics—with the result encoded in the off-diagonal blocks of a Hamiltonian—using Hamiltonian evolutions of input operators. We show how to maintain this Hamiltonian block encoding , so that matrix operations can be composed one after another, and the entire quantum computation takes ≤ 2 ancilla qubits. We achieve this for matrix multiplication, matrix addition, matrix inversion, Hermitian conjugation, fractional scaling, integer scaling, complex phase scaling, as well as singular value transformation for both odd and even polynomials. We also present an overlap estimation algorithm to extract classical properties of Hamiltonian block encoded operators, analogous to the well known Hadamard test, at no extra cost of qubit. Our Hamiltonian matrix multiplication uses the Lie group commutator product formula and its higher-order generalizations due to Childs and Wiebe. Our Hamiltonian singular value transformation employs a dominated polynomial approximation, where the approximation holds within the domain of interest, while the constructed polynomial is upper bounded by the target function over the entire unit interval. We describe a circuit for simulating a class of sum-of-squares Hamiltonians, attaining a commutator scaling in step count, while leveraging the power of matrix arithmetics to reduce the cost of each simulation step. In particular, we apply this to the doubly factorized tensor hypercontracted Hamiltonians from recent studies of quantum chemistry, obtaining further improvements for initial states with a fixed number of particles. We achieve this with 1 ancilla qubit.The efficient implementation of matrix arithmetic operations underpins the speedups of many quantum algorithms. We develop a suite of methods to perform matrix arithmetics—with the result encoded in the off-diagonal blocks of a Hamiltonian—using Hamiltonian evolutions of input operators. We show how to maintain this Hamiltonian block encoding , so that matrix operations can be composed one after another, and the entire quantum computation takes ≤ 2 ancilla qubits. We achieve this for matrix multiplication, matrix addition, matrix inversion, Hermitian conjugation, fractional scaling, integer scaling, complex phase scaling, as well as singular value transformation for both odd and even polynomials. We also present an overlap estimation algorithm to extract classical properties of Hamiltonian block encoded operators, analogous to the well known Hadamard test, at no extra cost of qubit. Our Hamiltonian matrix multiplication uses the Lie group commutator product formula and its higher-order generalizations due to Childs and Wiebe. Our Hamiltonian singular value transformation employs a dominated polynomial approximation, where the approximation holds within the domain of interest, while the constructed polynomial is upper bounded by the target function over the entire unit interval. We describe a circuit for simulating a class of sum-of-squares Hamiltonians, attaining a commutator scaling in step count, while leveraging the power of matrix arithmetics to reduce the cost of each simulation step. In particular, we apply this to the doubly factorized tensor hypercontracted Hamiltonians from recent studies of quantum chemistry, obtaining further improvements for initial states with a fixed number of particles. We achieve this with 1 ancilla qubit.

arXiv:2510.06316ACM Transactions on Quantum ComputingAug 8, 20260 citations

Quantum framework for simulating linear PDEs with Robin boundary conditions

Nikita Guseynov, Xiajie Huang, Nana Liu

Abstract We propose an explicit quantum framework for numerically simulating general linear partial differential equations (PDEs), extending previous work (Guseynov et al 2025 Phys. Rev. Res. 7 033100) to incorporate (a) Robin boundary conditions—which include Neumann and Dirichlet conditions as special cases–(b) inhomogeneous terms, and (c) variable coefficients in space and time. Our approach begins with a general finite-difference discretization and applies the Schrödingerisation technique to transform the resulting system into one that admits unitary quantum evolution, enabling quantum simulation. For the Schrödinger equation corresponding to the discretized PDE, we construct an efficient block-encoding of the Hamiltonian H that scales polylogarithmically with the number of grid points N . This encoding is compatible with quantum signal processing and allows for the implementation of the evolution operator e − i H t . The explicit circuit construction in our method permits complexity to be measured in fundamental gate units–namely, CNOT gates and single-qubit rotations–bypassing the inefficiencies of oracle queries. Consequently, the overall algorithm scales polynomially with N and linearly with the spatial dimension d . Under certain input/output assumptions our method achieves a polynomial speedup in N and an exponential advantage in d for a wide class of PDEs, thereby mitigating the classical curse of dimensionality. The validity and efficiency of the proposed approach are further substantiated by numerical simulations. By explicitly defining the quantum operations and quantifying their resource requirements, our approach offers a practical alternative for numerically solving PDEs, distinct from others that rely on oracle queries and purely asymptotic scaling methods.Abstract We propose an explicit quantum framework for numerically simulating general linear partial differential equations (PDEs), extending previous work (Guseynov et al 2025 Phys. Rev. Res. 7 033100) to incorporate (a) Robin boundary conditions—which include Neumann and Dirichlet conditions as special cases–(b) inhomogeneous terms, and (c) variable coefficients in space and time. Our approach begins with a general finite-difference discretization and applies the Schrödingerisation technique to transform the resulting system into one that admits unitary quantum evolution, enabling quantum simulation. For the Schrödinger equation corresponding to the discretized PDE, we construct an efficient block-encoding of the Hamiltonian H that scales polylogarithmically with the number of grid points N . This encoding is compatible with quantum signal processing and allows for the implementation of the evolution operator e − i H t . The explicit circuit construction in our method permits complexity to be measured in fundamental gate units–namely, CNOT gates and single-qubit rotations–bypassing the inefficiencies of oracle queries. Consequently, the overall algorithm scales polynomially with N and linearly with the spatial dimension d . Under certain input/output assumptions our method achieves a polynomial speedup in N and an exponential advantage in d for a wide class of PDEs, thereby mitigating the classical curse of dimensionality. The validity and efficiency of the proposed approach are further substantiated by numerical simulations. By explicitly defining the quantum operations and quantifying their resource requirements, our approach offers a practical alternative for numerically solving PDEs, distinct from others that rely on oracle queries and purely asymptotic scaling methods.

arXiv:2506.20478Quantum Science and TechnologyJan 27, 20260 citations

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps, Lin Lin, Roel Van Beeumen +1 more

Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.

arXiv:2203.10236SIAM Journal on Matrix Analysis and ApplicationsMar 11, 202478 citations

Circuit complexity of quantum access models for encoding classical data

Xiao‐Ming Zhang, Xiao Yuan

Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.

arXiv:2311.11365npj Quantum InformationApr 23, 202421 citations

Opening the Black Box inside Grover’s Algorithm

Edwin Miles Stoudenmire, Xavier Waintal

Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024

arXiv:2303.11317Physical Review XNov 1, 202427 citations

O(N_{\text{tot}}^{2/d} \operatorname{polylog}(N_{\text{tot}}))

, where

d

is the problem dimension and

N_{\text{tot}}

the number of grid points. In numerical examples that confirm the theoretical complexity estimates, the solutions converge approximately linearly for immersed problems and quadratically for simply connected domains.