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

Discrete Quantum Walk for solving Nonlinear Equations over finite fields

Essam Al-Daoud

Published Sep 4, 2014• 0 citations
OpenAlex

Abstract

This paper reviews some of quantum computation basics: qubit definition, quantum operations, quantum algorithm, measurement and quantum walk, and then applies the discrete quantum hypercube walk to the nonlinear systems over Galois Finite Field GF (2 n). The modified quantum mn nm walk algorithm needs O ( 2) iteration while the best classical general solution takes O ( 2) iteration. The paper also compares the classical and the modified algorithm numerically by using the Quack library.

Related papers

Quantum Computing for Solving a System of Nonlinear Equations over GF(q).

Essam Al-Daoud

Abstract: Grover’s quantum search algorithm is one of the most widely studied and has produced results in some search applications faster than their classical counterpart by a square-root. This paper modifies Grover’s algorithm to solve nonlinear equations over Galois Finite field GF(q) in O( mn 2) iteration, while the best classical general solution takes O(2 nm) iteration. The modification is done by using a register for each variable and represent it by n qubits. The paper also introduces the implementation of the suggested algorithm by using the simulator QCL 5.1.

The International Arab Journal of Information Technology•Jan 1, 2007•4 citations

Quantum Arithmetic on Galois Fields

Stéphane Beauregard, Gilles Brassard A, José M. Fernandez

In this paper we discuss the problem of performing elementary finite field arithmetic on a quantum computer. Of particular interest, is the controlled-multiplication operation, which is the only group-specific operation in Shor's algorithms for factoring and solving the Discrete Log Problem. We describe how to build quantum circuits for performing this operation on the generic Galois fields GF($p^k$), as well as the boundary cases GF($p$) and GF($2^k$). We give the detailed size, width and depth complexity of such circuits, which ultimately will allow us to obtain detailed upper bounds on the amount of quantum resources needed to solve instances of the DLP on such fields.

arXiv:quant-ph/0301163•Jan 29, 2003•18 citations

Algorithme de recherche par marche quantique sur hypercube : analyse propre et calcul de la probabilité de succès en temps polynomial

Hugo Pillin

Discrete time quantum walk algorithms are the direct analogs of classical random walk algorithms, an important family in theoretical informatics. They can solve a variety of problems, in particular the NPcomplete SAT problem, in a relatively short time. Thus, the study of quantum walks could lead to the conception of new quantum algorithms. Among the quantum algorithms, one of the most extensively studied is Grover’s searchalgorithm, an iterative process that can find one element among N that meet a certain criterion, with a quadratic time gain over any classical algorithm. In this thesis, we study the variant of Grover’s search algorithm proposed by Shenvi, Kempe and Whaley, based on walks on hypercube graphs.As search algorithms are iterative processes, one has to compute the correct number of steps R before running the search, as the probability of success decreases past a certain point. The value of R depends on the number of elements N, but also the number of solutions M. For Grover's algorithm, the optimal number of iterations is well known, but this is not the case for the search on the hypercube as soon as there are multiple solutions. In this thesis, we propose an extensive eigenanalysis of the hypercube search algorithm, which leads to a procedure that allows us to compute the probability of success of the search algorithm on the hypercube without running it, in polynomial time.

•Apr 5, 2024•0 citations

Quantum walk search algorithm based on phase matching and circuit cmplementation

Hanwu Chen, Ke Li, Shengmei Zhao

As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.

Acta Physica Sinica•Jan 1, 2015•0 citations

Quantum walks: a comprehensive review

Salvador Elías Venegas-Andraca

Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of research of quantum computation full of exciting open problems for physicists, computer scientists and engineers. In this paper we review theoretical advances on the foundations of both discrete- and continuous-time quantum walks, together with the role that randomness plays in quantum walks, the connections between the mathematical models of coined discrete quantum walks and continuous quantum walks, the quantumness of quantum walks, a summary of papers published on discrete quantum walks and entangle-ment as well as a succinct review of experimental proposals and realizations of discrete-time quantum walks. Furthermore, we have reviewed several algorithms based on both discrete- and continuous-time quantum walks as well as a most important result: the computational universality of both continuous- and discrete-time quantum walks.

•Jan 1, 2012•436 citations

Coined quantum walks

Nguyen, Long

Quantum computing is a developing field that applies the properties of quantum mechanics to develop solutions to complex problems that the most powerful classical computers cannot solve or cannot solve efficiently. Solving difficult tasks requires sophisticated and efficient algorithms that can utilize stochastic processes as the primary techniques. The typical models of these stochastic processes include discrete-time random walks and continuous ones. Quantum walks represent a quantum extension of discrete random walks, whose demonstrated utility in algorithm design has motivated signi cant interest in quantum computational research. Therefore, the purpose of this thesis is to explore the potential of discrete-time coined quantum walks using the Python package with high-performance computing (HPC) compared to classical walks by conducting a literature review. To supplement this research, some simulations are implemented to analyze the spreading behavior of coined quantum walks, compare them with classical walks, and demonstrate their application in search tasks, such as binary hypercube search algorithm. These simulations aim to clarify the extent to which quantum walks can be effectively modeled and applied in computational contexts. The results gained show that coined quantum walks exhibit faster spreading than classical random walks, which contributes to a deeper understanding of potential applications of quantum walks, such as quantum simulation, in the future.

•Sep 5, 2025•0 citations
This paper reviews some of quantum computation basics: qubit definition, quantum operations, quantum algorithm, measurement and quantum walk, and then applies the discrete quantum hypercube walk to the nonlinear systems over Galois Finite Field GF (2 n). The modified quantum mn nm walk algorithm needs O ( 2) iteration while the best classical general solution takes O ( 2) iteration. The paper also compares the classical and the modified algorithm numerically by using the Quack library.
Abstract: Grover’s quantum search algorithm is one of the most widely studied and has produced results in some search applications faster than their classical counterpart by a square-root. This paper modifies Grover’s algorithm to solve nonlinear equations over Galois Finite field GF(q) in O( mn 2) iteration, while the best classical general solution takes O(2 nm) iteration. The modification is done by using a register for each variable and represent it by n qubits. The paper also introduces the implementation of the suggested algorithm by using the simulator QCL 5.1.
In this paper we discuss the problem of performing elementary finite field arithmetic on a quantum computer. Of particular interest, is the controlled-multiplication operation, which is the only group-specific operation in Shor's algorithms for factoring and solving the Discrete Log Problem. We describe how to build quantum circuits for performing this operation on the generic Galois fields GF(pkp^kpk), as well as the boundary cases GF(ppp) and GF(2k2^k2k). We give the detailed size, width and depth complexity of such circuits, which ultimately will allow us to obtain detailed upper bounds on the amount of quantum resources needed to solve instances of the DLP on such fields.
Discrete time quantum walk algorithms are the direct analogs of classical random walk algorithms, an important family in theoretical informatics. They can solve a variety of problems, in particular the NPcomplete SAT problem, in a relatively short time. Thus, the study of quantum walks could lead to the conception of new quantum algorithms. Among the quantum algorithms, one of the most extensively studied is Grover’s searchalgorithm, an iterative process that can find one element among N that meet a certain criterion, with a quadratic time gain over any classical algorithm. In this thesis, we study the variant of Grover’s search algorithm proposed by Shenvi, Kempe and Whaley, based on walks on hypercube graphs.As search algorithms are iterative processes, one has to compute the correct number of steps R before running the search, as the probability of success decreases past a certain point. The value of R depends on the number of elements N, but also the number of solutions M. For Grover's algorithm, the optimal number of iterations is well known, but this is not the case for the search on the hypercube as soon as there are multiple solutions. In this thesis, we propose an extensive eigenanalysis of the hypercube search algorithm, which leads to a procedure that allows us to compute the probability of success of the search algorithm on the hypercube without running it, in polynomial time.
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.
Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of research of quantum computation full of exciting open problems for physicists, computer scientists and engineers. In this paper we review theoretical advances on the foundations of both discrete- and continuous-time quantum walks, together with the role that randomness plays in quantum walks, the connections between the mathematical models of coined discrete quantum walks and continuous quantum walks, the quantumness of quantum walks, a summary of papers published on discrete quantum walks and entangle-ment as well as a succinct review of experimental proposals and realizations of discrete-time quantum walks. Furthermore, we have reviewed several algorithms based on both discrete- and continuous-time quantum walks as well as a most important result: the computational universality of both continuous- and discrete-time quantum walks.
Quantum computing is a developing field that applies the properties of quantum mechanics to develop solutions to complex problems that the most powerful classical computers cannot solve or cannot solve efficiently. Solving difficult tasks requires sophisticated and efficient algorithms that can utilize stochastic processes as the primary techniques. The typical models of these stochastic processes include discrete-time random walks and continuous ones. Quantum walks represent a quantum extension of discrete random walks, whose demonstrated utility in algorithm design has motivated signi cant interest in quantum computational research. Therefore, the purpose of this thesis is to explore the potential of discrete-time coined quantum walks using the Python package with high-performance computing (HPC) compared to classical walks by conducting a literature review. To supplement this research, some simulations are implemented to analyze the spreading behavior of coined quantum walks, compare them with classical walks, and demonstrate their application in search tasks, such as binary hypercube search algorithm. These simulations aim to clarify the extent to which quantum walks can be effectively modeled and applied in computational contexts. The results gained show that coined quantum walks exhibit faster spreading than classical random walks, which contributes to a deeper understanding of potential applications of quantum walks, such as quantum simulation, in the future.