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

Technologies

\({\ell_0}\) Optimization with Robust Non-Oracular Quantum Search

Tianyi Zhang, Ke Yuan

Published Oct 19, 2023• 1 citation
Publisher

Abstract

In this article, we introduce an innovative hybrid quantum search algorithm, the Robust Non-oracle Quantum Search (RNQS), which is specifically designed to efficiently identify the minimum value within a large set of random numbers. Distinct from the Grover’s algorithm, the proposed RNQS algorithm circumvents the need for an oracle function that describes the true solution state, a feature often impractical for data science applications. Building on existing non-oracular quantum search algorithms, RNQS enhances robustness while substantially reducing running time. The superior properties of RNQS have been demonstrated through careful analysis and extensive empirical experiments. Our findings underscore the potential of the RNQS algorithm as an effective and efficient solution to combinatorial optimization problems in the realm of quantum computing.

DOI
10.3390/technologies11050148

Related papers

Best Subset Selection: Statistical Computing Meets Quantum Computing

Wenxuan Zhong, Ke, Yuan, Ye Wang +3 more

With the rapid development of quantum computers, quantum algorithms have been studied extensively. However, quantum algorithms tackling statistical problems are still lacking. In this paper, we propose a novel non-oracular quantum adaptive search (QAS) method for the best subset selection problems. QAS performs almost identically to the naive best subset selection method but reduces its computational complexity from $O(D)$ to $O(\sqrt{D}\log_2D)$, where $D=2^p$ is the total number of subsets over $p$ covariates. Unlike existing quantum search algorithms, QAS does not require the oracle information of the true solution state and hence is applicable to various statistical learning problems with random observations. Theoretically, we prove QAS attains any arbitrary success probability $q \in (0.5, 1)$ within $O(\log_2D)$ iterations. When the underlying regression model is linear, we propose a quantum linear prediction method that is faster than its classical counterpart. We further introduce a hybrid quantum-classical strategy to avoid the capacity bottleneck of existing quantum computing systems and boost the success probability of QAS by majority voting. The effectiveness of this strategy is justified by both theoretical analysis and extensive empirical experiments on quantum and classical computers.

arXiv:2107.08359•Jul 18, 2021•2 citations

Towards Efficient Function Optimisation with Quantum–Classical Hybrid Search

Mansur Ziatdinov, Fedor Levkovich-Maslyuk, Emmanuel M. Pothos

Finding the global minimum of a function with many local extrema is well known to be a challenging computational task. We propose a hybrid quantum-classical algorithm for this optimisation problem, based on a combination of Grover quantum search and the classical Newton-Raphson method. The approach is tailored to situations with a large number of false minima. The main idea is to use quantum search to efficiently locate the vicinity of the true optimum, after which a classical algorithm can solve the problem in only a few iterations. We specifically address the nontrivial question of choosing the discretisation of the function domain, which is critical for quantum approaches to optimisation of continuous functions. While we do not expect that this method will always be superior, we identify a paradigmatic case of a function for which we demonstrate that, remarkably, our hybrid method quadratically outperforms a purely classical approach (measuring performance by the number of function/oracle calls). We evaluate key performance metrics of the algorithm in numerical experiments. We furthermore discuss its possible extensions as well as the potential relevance of hybrid approaches in the context of quantum cognition.

Entropy•Sep 26, 2026•0 citations

Constraint-oriented biased quantum search for general constrained combinatorial optimization problems

Sören Wilkening

We present a quantum algorithmic routine that extends the realm of Grover-based heuristics for tackling combinatorial optimization problems with arbitrary efficiently computable objective and constraint functions. Building on previously developed quantum methods that were primarily restricted to linear constraints, we generalize the approach to encompass a broader class of problems in discrete domains. To evaluate the potential of our algorithm, we assume the existence of sufficiently advanced logical quantum hardware. With this assumption, we demonstrate that our method has the potential to outperform state-of-the-art classical solvers and heuristics in terms of both runtime scaling and solution quality. The same may be true for more realistic implementations, as the logical quantum algorithm can achieve runtime savings of up to $10^2-10^3$.

quant-pharXiv:2512.08384•Dec 10, 2025•2 citations

Quantum Grover Adaptive Search for Discrete Simulation Optimization

Mingjie Hu, Jian-qiang Hu, Enlu Zhou

Quantum computing has advanced rapidly in recent years and has shown advantages in a variety of domains. In this paper, we investigate its potential for discrete simulation optimization in the fixed-confidence setting, a fundamental problem in the simulation literature. We first introduce a quantum simulation oracle that prepares a coherent superposition over all candidate solutions and provides the foundation for quantum algorithm design. Based on this oracle, we develop the first Grover-search-based quantum algorithm for discrete simulation optimization, called SOGAS. In particular, SOGAS uses a binary-search framework to progressively eliminate suboptimal solutions while carefully controlling the error probability, and eventually identifies a set of near-optimal solutions. We prove that SOGAS returns a near-optimal solution with probability at least the prescribed confidence level and achieves a quadratic speedup in the dependence of query complexity on the number of candidate solutions. Numerical experiments further show that SOGAS substantially outperforms classical benchmarks and provide empirical evidence for quantum advantage in discrete simulation optimization.

quant-pharXiv:2604.26277•Apr 30, 2026•3 citations

Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)

一雄 岩間, 亮周 河内, Rudy Raymond +1 more

The oracle identification problem (OIP) was introduced by Ambainis et.al. [4], which is given as a set $S$ of $M$ oracles and a hidden oracle $f$ .Our task is to figure out which oracle in $S$ is equal to the hidden $f$ by doing queries to $f$ .OIP includes several problems such as Grover Search as special cases.In this paper, we design robust algorithms, i.e., those which are tolerant against noisy oracles, for OIP.Our results include: (i) For any oracle set $S$ such that $|S|$ is polynomial in $N$ , $O(\sqrt{N})$ queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case, (ii) For the case that $|S|\leq 2^{N^{d}}(d<1)$ , we design an algorithm whose query complexity is $O(\sqrt{N\log M/\log N})$ and matches the lower bound proved in [4].(Hi) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of (ii) and the complexity of recovering all information about the hidden oracle whose complexity is $O(N)$ as showed by Buhrman et.al. in [11].Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case [4],

数理解析研究所講究録•Apr 1, 2005•0 citations

Quantum Search using Grover’s Algorithm: Principles, Performance, and Applications

Anggit Gusti Nugraheni, Heri Mahyuzar, Sri Hastuti

Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.

Asian journal of mathematics and computer research•Jun 23, 2026•0 citations
ℓ0{\ell_0}ℓ0​ Optimization with Robust Non-Oracular Quantum Search
In this article, we introduce an innovative hybrid quantum search algorithm, the Robust Non-oracle Quantum Search (RNQS), which is specifically designed to efficiently identify the minimum value within a large set of random numbers. Distinct from the Grover’s algorithm, the proposed RNQS algorithm circumvents the need for an oracle function that describes the true solution state, a feature often impractical for data science applications. Building on existing non-oracular quantum search algorithms, RNQS enhances robustness while substantially reducing running time. The superior properties of RNQS have been demonstrated through careful analysis and extensive empirical experiments. Our findings underscore the potential of the RNQS algorithm as an effective and efficient solution to combinatorial optimization problems in the realm of quantum computing.
With the rapid development of quantum computers, quantum algorithms have been studied extensively. However, quantum algorithms tackling statistical problems are still lacking. In this paper, we propose a novel non-oracular quantum adaptive search (QAS) method for the best subset selection problems. QAS performs almost identically to the naive best subset selection method but reduces its computational complexity from O(D)O(D)O(D) to O(Dlog⁡2D)O(\sqrt{D}\log_2D)O(D​log2​D), where D=2pD=2^pD=2p is the total number of subsets over ppp covariates. Unlike existing quantum search algorithms, QAS does not require the oracle information of the true solution state and hence is applicable to various statistical learning problems with random observations. Theoretically, we prove QAS attains any arbitrary success probability q∈(0.5,1)q \in (0.5, 1)q∈(0.5,1) within O(log⁡2D)O(\log_2D)O(log2​D) iterations. When the underlying regression model is linear, we propose a quantum linear prediction method that is faster than its classical counterpart. We further introduce a hybrid quantum-classical strategy to avoid the capacity bottleneck of existing quantum computing systems and boost the success probability of QAS by majority voting. The effectiveness of this strategy is justified by both theoretical analysis and extensive empirical experiments on quantum and classical computers.
Finding the global minimum of a function with many local extrema is well known to be a challenging computational task. We propose a hybrid quantum-classical algorithm for this optimisation problem, based on a combination of Grover quantum search and the classical Newton-Raphson method. The approach is tailored to situations with a large number of false minima. The main idea is to use quantum search to efficiently locate the vicinity of the true optimum, after which a classical algorithm can solve the problem in only a few iterations. We specifically address the nontrivial question of choosing the discretisation of the function domain, which is critical for quantum approaches to optimisation of continuous functions. While we do not expect that this method will always be superior, we identify a paradigmatic case of a function for which we demonstrate that, remarkably, our hybrid method quadratically outperforms a purely classical approach (measuring performance by the number of function/oracle calls). We evaluate key performance metrics of the algorithm in numerical experiments. We furthermore discuss its possible extensions as well as the potential relevance of hybrid approaches in the context of quantum cognition.
We present a quantum algorithmic routine that extends the realm of Grover-based heuristics for tackling combinatorial optimization problems with arbitrary efficiently computable objective and constraint functions. Building on previously developed quantum methods that were primarily restricted to linear constraints, we generalize the approach to encompass a broader class of problems in discrete domains. To evaluate the potential of our algorithm, we assume the existence of sufficiently advanced logical quantum hardware. With this assumption, we demonstrate that our method has the potential to outperform state-of-the-art classical solvers and heuristics in terms of both runtime scaling and solution quality. The same may be true for more realistic implementations, as the logical quantum algorithm can achieve runtime savings of up to 102−10310^2-10^3102−103.
Quantum computing has advanced rapidly in recent years and has shown advantages in a variety of domains. In this paper, we investigate its potential for discrete simulation optimization in the fixed-confidence setting, a fundamental problem in the simulation literature. We first introduce a quantum simulation oracle that prepares a coherent superposition over all candidate solutions and provides the foundation for quantum algorithm design. Based on this oracle, we develop the first Grover-search-based quantum algorithm for discrete simulation optimization, called SOGAS. In particular, SOGAS uses a binary-search framework to progressively eliminate suboptimal solutions while carefully controlling the error probability, and eventually identifies a set of near-optimal solutions. We prove that SOGAS returns a near-optimal solution with probability at least the prescribed confidence level and achieves a quadratic speedup in the dependence of query complexity on the number of candidate solutions. Numerical experiments further show that SOGAS substantially outperforms classical benchmarks and provide empirical evidence for quantum advantage in discrete simulation optimization.
The oracle identification problem (OIP) was introduced by Ambainis et.al. [4], which is given as a set SSS of MMM oracles and a hidden oracle fff .Our task is to figure out which oracle in SSS is equal to the hidden fff by doing queries to fff .OIP includes several problems such as Grover Search as special cases.In this paper, we design robust algorithms, i.e., those which are tolerant against noisy oracles, for OIP.Our results include: (i) For any oracle set SSS such that ∣S∣|S|∣S∣ is polynomial in NNN , O(N)O(\sqrt{N})O(N​) queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case, (ii) For the case that ∣S∣≤2Nd(d<1)|S|\leq 2^{N^{d}}(d<1)∣S∣≤2Nd(d<1) , we design an algorithm whose query complexity is O(Nlog⁡M/log⁡N)O(\sqrt{N\log M/\log N})O(NlogM/logN​) and matches the lower bound proved in [4].(Hi) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of (ii) and the complexity of recovering all information about the hidden oracle whose complexity is O(N)O(N)O(N) as showed by Buhrman et.al. in [11].Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case [4],
Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.