Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2601.13306

The table maker's quantum search

Stefanos Kourtis

quant-phmath.NASubmitted Jan 19, 2026• Announced Jan 21, 2026• 0 citations
v1 · Jan 19, 2026v2 · Jun 10, 2026
arXivHTMLPDF

Abstract

We show that quantum search can be used to compute the hardness to round an elementary function, that is, to determine the minimum working precision required to compute the values of an elementary function correctly rounded to a target precision of $n$ digits for all possible precision-$n$ floating-point inputs in a given interval. For elementary functions $f$ related to the exponential function, quantum search takes time $\tilde O(2^{n/2} \log (1/δ))$ to return, with probability $1-δ$, the hardness to round $f$ over all $n$-bit floating-point inputs in a given binade. For periodic elementary functions in large binades, standalone quantum search yields an asymptotic speedup over the best known classical algorithms and heuristics.

Comments
11 pages, 0 figures; feedback welcome

Related papers

Quantum Algorithms and Hard Problems

C. Vidya Raj, H. D. Phaneendra, M. S. Shivakumar

Any computation is necessarily a physical process. The current drive towards increasing speed and miniaturization of computers lead modern technology towards the subatomic domain - quantum computing, where strange quantum behavior takes over from familiar classical notions. The quantum computers have the ability to solve problems with varied computational complexities and more importantly hard problems. A problem is said to be hard, if the best possible algorithm requires exponential resources. This exponential quantum parallelism is the basis for the quantum speedup of many algorithms, and has made the construction of fast algorithms for quantum computers possible. Various proposals exist for modeling and devising procedures on computational problems related to factoring, searching, quantum counting, generalization of quantum algorithms etc. (Shor, 1994). In this paper, we have discussed the importance of algorithms such as order-finding, factoring and quantum searching which require exorbitant resources for their solution which otherwise is impossible on a classical computer

IEEE International Conference on Cognitive Informatics•Jul 1, 2006•5 citations

Floating-Point Arithmetic with Consistent Rounding on a Quantum Computer

R. Steijl

Implementation of floating-point arithmetic with consistent rounding is a critical component of many quantum algorithms. Quantum circuit implementations for squaring and division serve as examples here. This work was motivated by ongoing work in developing quantum algorithms for scientific and engineering computing applications, where this type of arithmetic often forms part of the algorithm. A key feature of the work is the use of a reduced-precision floating-point representation of real data specifically designed for near-term future quantum computing hardware with a limited number of qubits (e.g., less than 100) and with an increased level of fault tolerance as compared to current quantum computing hardware. The quantum circuit implementations of the squaring of a floating-point number and the division of two floating-point numbers are detailed here, highlighting similarities in the quantum circuit implementation for the logical steps required for rounding-to-nearest in line with the IEEE 754 standard for the two arithmetic operations. This similarity is an important feature regarding future work where an automated generation of this type of quantum circuit from a set of standard modules and circuit templates is employed.

IntechOpen eBooks•Jun 7, 2024•0 citations

Efficient Evaluation of Exponential and Gaussian Functions on a Quantum Computer

Bill Poirier

The exponential and Gaussian functions are among the most fundamental and important operations, appearing ubiquitously throughout all areas of science, engineering, and mathematics. Whereas formally, it is well-known that any function may in principle be realized on a quantum computer, in practice present-day algorithms tend to be very expensive. In this work, we present algorithms for evaluating exponential and Gaussian functions efficiently on quantum computers. The implementations require a (generally) small number of multiplications, which represent the overall computational bottleneck. For a specific, realistic NISQ application, the Toffoli count of the exponential function is found to be reduced from 15,690 down to 912, when compared against a state-of-the art competing method by Häner and coworkers [arXiv:1805.12445], under the most favorable conditions for each method. For the corresponding Gaussian function comparison, the Toffoli count is reduced from 19,090 down to 704. Space requirements are also quite modest, to the extent that the aforementioned NISQ application can be implemented with as few as 71 logical qubits. More generally, the methods presented here could also be equally well applied in a fault-tolerant context, using error-corrected multiplications, etc.

arXiv:2110.05653•Oct 12, 2021•2 citations

Precision-aware fixed-point emulation of Grover’s algorithm: asymptotic error bounds and design guidelines

S. Choi, Kyeongwon Lee, Jong‐In Choi +2 more

Abstract We propose a rigorous precision-aware framework for fixed-point emulation of Grover’s quantum search algorithm, systematically analyzing how truncation errors propagate and accumulate through quantum gate operations. Although fixed-point arithmetic significantly reduces resource requirements in quantum computing emulators, limited fractional-bit precision introduces non-negligible numerical errors, adversely impacting algorithm accuracy. To address this, we introduce a simplified two-amplitude quantum state representation that captures Grover’s algorithmic structure across iterations. Leveraging this model, we analytically derive explicit asymptotic error bounds on the emulated measurement probability distribution, demonstrating that errors scale exponentially as O(2n−f ), where n is the number of qubits and f is fractional-bit precision. Extensive numerical simulations and practical experiments on an actual fixed-point quantum emulator validate our theoretical predictions, confirming the accuracy and robustness of our error analysis. Finally, we present a closed-form expression to determine the minimal fractional-bit precision needed to meet a specified accuracy threshold, providing concrete, actionable guidelines for designing resource-efficient quantum computing emulators.

Quantum Information Processing•Jun 12, 2026•1 citation

Nanoscale Precision-Related Challenges in Classical and Quantum Optimization

Yao–Hsin Chou, Ching-Hsuan Wu, Yu-Chi Jiang +2 more

Quantum computation and optimization have recently garnered considerable attention, with a noticeable focus on their floating-point and arithmetic designs. In classical computing, numerical optimization problems are commonly employed to assess the performance of optimization algorithms before their application to real-world issues. Nevertheless, precision issues impact the performance analysis of these algorithms, and neglecting these predictable exceptions can lead to unforeseen consequences. Therefore, this study systematically organizes potential precision issues related to how the floating-point storage format impacts optimization. These issues cause the optimal solution to deviate from the theoretical value, introducing imprecision or multiple optimal values, which in turn affects the usability of optimization algorithms, the direction of the search, and the assessment of convergence levels. These analyses offer valuable insights into the practical behavior of optimization algorithms when applied to function optimization problems, aiding researchers in accurately assessing and enhancing algorithm performance. Moreover, these findings contribute to the advancement of both classical and quantum computation.

IEEE Nanotechnology Magazine•Apr 15, 2024•1 citation

Applying quantum algorithms to constraint satisfaction problems

Earl T. Campbell, Ankur Khurana, Ashley Montanaro

Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over 105 relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over 103 . However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.

arXiv:1810.05582•Quantum•Jul 18, 2019•76 citations
We show that quantum search can be used to compute the hardness to round an elementary function, that is, to determine the minimum working precision required to compute the values of an elementary function correctly rounded to a target precision of nnn digits for all possible precision-nnn floating-point inputs in a given interval. For elementary functions fff related to the exponential function, quantum search takes time O~(2n/2log⁡(1/δ))\tilde O(2^{n/2} \log (1/δ))O~(2n/2log(1/δ)) to return, with probability 1−δ1-δ1−δ, the hardness to round fff over all nnn-bit floating-point inputs in a given binade. For periodic elementary functions in large binades, standalone quantum search yields an asymptotic speedup over the best known classical algorithms and heuristics.
Any computation is necessarily a physical process. The current drive towards increasing speed and miniaturization of computers lead modern technology towards the subatomic domain - quantum computing, where strange quantum behavior takes over from familiar classical notions. The quantum computers have the ability to solve problems with varied computational complexities and more importantly hard problems. A problem is said to be hard, if the best possible algorithm requires exponential resources. This exponential quantum parallelism is the basis for the quantum speedup of many algorithms, and has made the construction of fast algorithms for quantum computers possible. Various proposals exist for modeling and devising procedures on computational problems related to factoring, searching, quantum counting, generalization of quantum algorithms etc. (Shor, 1994). In this paper, we have discussed the importance of algorithms such as order-finding, factoring and quantum searching which require exorbitant resources for their solution which otherwise is impossible on a classical computer
Implementation of floating-point arithmetic with consistent rounding is a critical component of many quantum algorithms. Quantum circuit implementations for squaring and division serve as examples here. This work was motivated by ongoing work in developing quantum algorithms for scientific and engineering computing applications, where this type of arithmetic often forms part of the algorithm. A key feature of the work is the use of a reduced-precision floating-point representation of real data specifically designed for near-term future quantum computing hardware with a limited number of qubits (e.g., less than 100) and with an increased level of fault tolerance as compared to current quantum computing hardware. The quantum circuit implementations of the squaring of a floating-point number and the division of two floating-point numbers are detailed here, highlighting similarities in the quantum circuit implementation for the logical steps required for rounding-to-nearest in line with the IEEE 754 standard for the two arithmetic operations. This similarity is an important feature regarding future work where an automated generation of this type of quantum circuit from a set of standard modules and circuit templates is employed.
The exponential and Gaussian functions are among the most fundamental and important operations, appearing ubiquitously throughout all areas of science, engineering, and mathematics. Whereas formally, it is well-known that any function may in principle be realized on a quantum computer, in practice present-day algorithms tend to be very expensive. In this work, we present algorithms for evaluating exponential and Gaussian functions efficiently on quantum computers. The implementations require a (generally) small number of multiplications, which represent the overall computational bottleneck. For a specific, realistic NISQ application, the Toffoli count of the exponential function is found to be reduced from 15,690 down to 912, when compared against a state-of-the art competing method by Häner and coworkers [arXiv:1805.12445], under the most favorable conditions for each method. For the corresponding Gaussian function comparison, the Toffoli count is reduced from 19,090 down to 704. Space requirements are also quite modest, to the extent that the aforementioned NISQ application can be implemented with as few as 71 logical qubits. More generally, the methods presented here could also be equally well applied in a fault-tolerant context, using error-corrected multiplications, etc.
Abstract We propose a rigorous precision-aware framework for fixed-point emulation of Grover’s quantum search algorithm, systematically analyzing how truncation errors propagate and accumulate through quantum gate operations. Although fixed-point arithmetic significantly reduces resource requirements in quantum computing emulators, limited fractional-bit precision introduces non-negligible numerical errors, adversely impacting algorithm accuracy. To address this, we introduce a simplified two-amplitude quantum state representation that captures Grover’s algorithmic structure across iterations. Leveraging this model, we analytically derive explicit asymptotic error bounds on the emulated measurement probability distribution, demonstrating that errors scale exponentially as O(2n−f ), where n is the number of qubits and f is fractional-bit precision. Extensive numerical simulations and practical experiments on an actual fixed-point quantum emulator validate our theoretical predictions, confirming the accuracy and robustness of our error analysis. Finally, we present a closed-form expression to determine the minimal fractional-bit precision needed to meet a specified accuracy threshold, providing concrete, actionable guidelines for designing resource-efficient quantum computing emulators.
Quantum computation and optimization have recently garnered considerable attention, with a noticeable focus on their floating-point and arithmetic designs. In classical computing, numerical optimization problems are commonly employed to assess the performance of optimization algorithms before their application to real-world issues. Nevertheless, precision issues impact the performance analysis of these algorithms, and neglecting these predictable exceptions can lead to unforeseen consequences. Therefore, this study systematically organizes potential precision issues related to how the floating-point storage format impacts optimization. These issues cause the optimal solution to deviate from the theoretical value, introducing imprecision or multiple optimal values, which in turn affects the usability of optimization algorithms, the direction of the search, and the assessment of convergence levels. These analyses offer valuable insights into the practical behavior of optimization algorithms when applied to function optimization problems, aiding researchers in accurately assessing and enhancing algorithm performance. Moreover, these findings contribute to the advancement of both classical and quantum computation.
Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over 105 relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over 103 . However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.