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:1312.4116

Quantum Algorithm to Solve a Maze: Converting the Maze Problem into a Search Problem

Niraj Kumar, Debabrata Goswami

Published Dec 15, 2013• 6 citations
arXivHTMLPDF

Abstract

We propose a different methodology towards approaching a Maze problem. We convert the problem into a Quantum Search Problem (QSP), and its solutions are sought for using the iterative Grover's Search Algorithm. Though the category of mazes we are looking at are of the NP complete class, we have redirected such a NP complete problem into a QSP. Our solution deals with two dimensional perfect mazes with no closed loops. We encode all possible individual paths from the starting point of the maze into a quantum register. A quantum fitness operator applied on the register encodes each individual with its fitness value. We propose an oracle design which marks all the individuals above a certain fitness value and use the Grover search algorithm to find one of the marked states. Iterating over this method, we approach towards the optimum solution.

DOI
10.48550/arxiv.1312.4116

Related papers

Sensing the insensible using optical schemes: converting the maze problem into a quantum search problem

Debabrata Goswami

Many large image processing and data processing scenarios can soon develop into maze problems requiring, say, finding the longest possible path, which are unresponsive, intractable, and challenging to analyze! Such maze problems, of which the traveling salesman decision problem is a special case, are of the Non-determinate Polynomial (NPcomplete) class of problems that are often impossible to solve with finite time and storage. We propose a novel methodology to approach this class of NP-complete problems. We convert a suitably formulated maze problem into a Quantum Search Problem (QSP), and the desired solutions are then sought using the iterative Grover’s Search Algorithm. Thus, we reformulate the entire class of such NP-problems into QSPs. Our current solution deals with two-dimensional perfect mazes with no closed loops. We encode all possible individual paths from the starting point of the maze into a quantum register. A quantum fitness operator applied to the register encodes each qubit with its fitness value. We propose the design of an optical oracle that marks all entities above a certain fitness value and uses the Grover search algorithm to find the optimal marked state in an iterative manner.

•Apr 23, 2020•0 citations

A Quantum Algorithm for Solving the Travelling Salesman Problem by Quantum Phase Estimation and Quantum Search

Ch. Tszyun'si, Ilya I. Beterov

Abstract A quantum algorithm for solving the traveling salesman problem by the quantum phase estimation and quantum search method is considered. An approach is developed that was previously proposed for solving this problem. A quantum register is used to encode the eigenstates of a unitary operator whose phase determines the length of each possible route. The quantum phase estimation algorithm is used to estimate the length of a route. Then, to find the minimum route length, the measured values of length are encoded into the states of the second quantum register, and the search for the optimal route is carried out using a modified Grover algorithm. Numerical simulation of the proposed quantum algorithm is carried out using the Qiskit library for one and two iterations of the modified Grover algorithm.

Journal of Experimental and Theoretical Physics•Aug 1, 2023•11 citations

A Quantum Algorithm for Solving the Travelling Salesman Problem by Quantum Phase Estimation and Quantum Search

Ch. Tszyun'si, Ilya I. Beterov

A quantum algorithm for solving the traveling salesman problem by the quantum phase estimation and quantum search method is considered. An approach is developed that was previously proposed for solving this problem. A quantum register is used to encode the eigenstates of a unitary operator whose phase determines the length of each possible route. The quantum phase estimation algorithm is used to estimate the length of a route. Then, to find the minimum route length, the measured values of length are encoded into the states of the second quantum register, and the search for the optimal route is carried out using a modified Grover algorithm. Numerical simulation of the proposed quantum algorithm is carried out using the Qiskit library for one and two iterations of the modified Grover algorithm.

Журнал Экспериментальной и Теоретической Физики•Dec 15, 2023•0 citations

A Non-Oracle Quantum Search Algorithm and Its Experimental Implementation

Nanyang Xu, Zhu Jin, Xinhua Peng +2 more

Grover's algorithm has achieved great success. But quantum search algorithms still are not complete algorithms because of Grover's Oracle. We concerned on this problem and present a new quantum search algorithm in adiabatic model without Oracle. We analyze the general difficulties in quantum search algorithms and show how to solve them in the present algorithm. As well this algorithm could deal with both single-solution and multi-solution searches without modification. We also implement this algorithm on NMR quantum computer. It is the first experiment which perform a real quantum database search rather than a marked-state search.

arXiv:0809.0664•Sep 3, 2008•2 citations

Quantum search algorithm in unstructured database

A. D. Kozhukhivskyi

Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.

Scientific Notes of the State University of Telecommunications•Jan 1, 2022•2 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 eBooks•Apr 26, 2011•1 citation
We propose a different methodology towards approaching a Maze problem. We convert the problem into a Quantum Search Problem (QSP), and its solutions are sought for using the iterative Grover's Search Algorithm. Though the category of mazes we are looking at are of the NP complete class, we have redirected such a NP complete problem into a QSP. Our solution deals with two dimensional perfect mazes with no closed loops. We encode all possible individual paths from the starting point of the maze into a quantum register. A quantum fitness operator applied on the register encodes each individual with its fitness value. We propose an oracle design which marks all the individuals above a certain fitness value and use the Grover search algorithm to find one of the marked states. Iterating over this method, we approach towards the optimum solution.
Many large image processing and data processing scenarios can soon develop into maze problems requiring, say, finding the longest possible path, which are unresponsive, intractable, and challenging to analyze! Such maze problems, of which the traveling salesman decision problem is a special case, are of the Non-determinate Polynomial (NPcomplete) class of problems that are often impossible to solve with finite time and storage. We propose a novel methodology to approach this class of NP-complete problems. We convert a suitably formulated maze problem into a Quantum Search Problem (QSP), and the desired solutions are then sought using the iterative Grover’s Search Algorithm. Thus, we reformulate the entire class of such NP-problems into QSPs. Our current solution deals with two-dimensional perfect mazes with no closed loops. We encode all possible individual paths from the starting point of the maze into a quantum register. A quantum fitness operator applied to the register encodes each qubit with its fitness value. We propose the design of an optical oracle that marks all entities above a certain fitness value and uses the Grover search algorithm to find the optimal marked state in an iterative manner.
Abstract A quantum algorithm for solving the traveling salesman problem by the quantum phase estimation and quantum search method is considered. An approach is developed that was previously proposed for solving this problem. A quantum register is used to encode the eigenstates of a unitary operator whose phase determines the length of each possible route. The quantum phase estimation algorithm is used to estimate the length of a route. Then, to find the minimum route length, the measured values of length are encoded into the states of the second quantum register, and the search for the optimal route is carried out using a modified Grover algorithm. Numerical simulation of the proposed quantum algorithm is carried out using the Qiskit library for one and two iterations of the modified Grover algorithm.
A quantum algorithm for solving the traveling salesman problem by the quantum phase estimation and quantum search method is considered. An approach is developed that was previously proposed for solving this problem. A quantum register is used to encode the eigenstates of a unitary operator whose phase determines the length of each possible route. The quantum phase estimation algorithm is used to estimate the length of a route. Then, to find the minimum route length, the measured values of length are encoded into the states of the second quantum register, and the search for the optimal route is carried out using a modified Grover algorithm. Numerical simulation of the proposed quantum algorithm is carried out using the Qiskit library for one and two iterations of the modified Grover algorithm.
Grover's algorithm has achieved great success. But quantum search algorithms still are not complete algorithms because of Grover's Oracle. We concerned on this problem and present a new quantum search algorithm in adiabatic model without Oracle. We analyze the general difficulties in quantum search algorithms and show how to solve them in the present algorithm. As well this algorithm could deal with both single-solution and multi-solution searches without modification. We also implement this algorithm on NMR quantum computer. It is the first experiment which perform a real quantum database search rather than a marked-state search.
Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.
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.