Quantum oracles for the finite element method

• URL: http://arxiv.org/abs/2504.19827v1
• Date: Mon, 28 Apr 2025 14:28:31 GMT
• Title: Quantum oracles for the finite element method
• Authors: Sven Danz, Tobias Stollenwerk, Alessandro Ciani,
• Abstract summary: 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.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
• Score: 45.200826131319815
• License: http://creativecommons.org/licenses/by/4.0/
• 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$.

Related papers

• Fast Convex Optimization with Quantum Gradient Methods [2.5094874597551913]
  We study quantum algorithms based on quantum (sub)gradient estimation using noisy evaluation oracles. We match the first-order query complexities of classical gradient descent, using only noisy evaluation oracles. We generalize these algorithms to work in non-Euclidean settings.
  arXiv  Detail & Related papers  (2025-03-21T17:58:12Z)
• Quantum Advantage via Efficient Post-processing on Qudit Shadow tomography [3.19428095493284]
  inner products of the form ( operatornametr(AB) ) are fundamental across quantum science and artificial intelligence.<n>We introduce a quantum approach based on qudit classical shadow tomography, significantly reducing computational complexity.<n>Our results establish a practical and modular quantum subroutine, enabling scalable quantum advantages in tasks involving high-dimensional data analysis and processing.
  arXiv  Detail & Related papers  (2024-08-29T03:56:16Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
  arXiv  Detail & Related papers  (2023-06-02T17:49:35Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• On quantum algorithms for the Schr\"odinger equation in the semi-classical regime [27.175719898694073]
  We consider Schr"odinger's equation in the semi-classical regime. Such a Schr"odinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics.
  arXiv  Detail & Related papers  (2021-12-25T20:01:54Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$. The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
  arXiv  Detail & Related papers  (2020-09-09T18:00:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.