arXiv:2202.11443 · ACM Transactions on Quantum Computing

Hybrid Quantum-classical Search Algorithms

Ansis Rosmanis

Published Feb 16, 2024• 12 citations

Abstract

Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover’s algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms, and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.

DOI: 10.1145/3648573

Related papers

Tree Search and Quantum Computation

Andreas Wichert

Abstract. Traditional tree search algorithms supply a blueprint for modeling prob-lem solving behaviour. A diverse spectrum of problems can be formulated in terms of tree search. Quantum computation, in particular Grover’s algorithm, has aroused a great deal of interest since it allows for a quadratic speedup to be obtained in search procedures. In this work we consider the impact of incorporating classical search con-cepts alongside Grover’s algorithm into a hybrid quantum search system. Some of the crucial points examined include: (1) the reverberations of contemplating the use of non-constant branching factors; (2) determining the consequences of incorporating an heuristic perspective into a quantum tree search model.

Jan 9, 201612 citations

Efficient Dictionary Search Quantum Algorithms

Farid Mansurovich Ablayev, Nailya Salikhova, Marat Ablayev

Abstract In this paper, we consider the problem of searching for an element in a dictionary. Various approaches to solving this problem have been proposed in recent decades: classical and quantum algorithms. We present two algorithms: a hybrid classical-quantum algorithm [1], that implements Grover’s search, and a “pure” quantum algorithm based on the quantum fingerprinting technique. Both algorithms work (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. Our algorithms are much more memory efficient in terms of the number of qubits used compared to previously known quantum algorithms.

Physics of Particles and NucleiAug 1, 20252 citations

Quadratically Fast Searching in Quantum Computation

Mohit Joshi, Manoj Kumar Mishra, S. Karthikeyan

Grover’s search algorithm is one of the most famous quantum algorithms, which enables search in unstructured dataspaces with a quadratic speedup over any known classical algorithm. This is one of the first algorithms to show quantum advantage over classical methods of computation. Besides its most anticipated application of brute force attack on symmetric key encryptions like AES, it is today being used in many modern applications as a subroutine. In this chapter, we describe the mathematical model of Grover’s quantum search algorithm, its behavior, and the theory of its circuit implementation. This chapter also discusses an exact variant of this algorithm and recent applications of Grover’s quantum search.

CRC Press eBooksMar 24, 20260 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooksApr 26, 20110 citations

Adaptive complete quantum search with unknown number of solutions

Raj Alexandru Guţoiu, Bogdan-Călin Ciobanu, Pantelimon George Popescu

Unstructured database search is a fundamental problem that requires finding one or more elements satisfying a specific property within a set of candidates. While Grover's algorithm provides a quadratic speedup for finding a marked element when the number of solutions is known, finding all solutions when their number is unknown presents additional challenges. In this paper, we thoroughly analyze this problem by considering all the different regimes of combinations of classical, Grover and generalized fixed-point quantum search instances. We unify these into an adaptive Bayesian approach that maximizes the expected success probability per unit execution time at each searching instance. For a problem with a known number of solutions, much lower than the database size, we prove that our proposed approach is asymptotically optimal within the considered search model. Furthermore, we prove that for any probability distribution characterizing the likely number of solutions, in regimes where the classical verification time is at most 25% of the quantum amplitude amplification time, hybrid classical and Grover approaches are preferred to generalized fixed-point. Outside of this regime, we derive an upper bound on the maximal improvement achievable by fixed-point search compared to the best Grover-based score. Additionally, we determine the optimal transition point between classical sampling and quantum searching using an integral approximation of the probability distribution of the number of solutions. The analytical results are also supported by numerical simulations of the proposed algorithm and by comparisons between the generalized fixed-point and Grover-based search policies.

quant-pharXiv:2610.06364Oct 6, 20260 citations

Fast simulation of Grover's quantum search on classical computer

Ayan Chattopadhyay, Menon, Vikram

The research community has been actively working on the realization of quantum computer. But the large scale commercial quantum computers are not a reality yet quantum computing field has become richer by day with the advent of algorithms and the avenue of its application in multiple domains. Availability of efficient quantum simulators will enable the researchers to quickly verify their results and concepts in order to establish a working proof of correctness. One important algorithm that has become one of the basic ingredients to build other algorithms and models is the Grover's search Algorithm which is known to be the most compute intensive. Our approach highlights the design principles for the fast simulation of Grover's search which can be implemented on a general purpose personal computer. The performance obtained are encouraging when compared to the existing simulators.

arXiv:2005.04635May 10, 20203 citations