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

International Conference on Information and Communication Technology Convergence (ICTC)

Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States

Jinyoung Ha, Jun Heo

Published Oct 19, 2022• 1 citation
Publisher

Abstract

In this paper, we propose a construction method of Grover's algorithm to solve the N-Queen problem. Quantum permutation state was designed and applied to the initialization and amplitude amplification process in Grover's algorithm. An oracle-level quantum circuit was constructed using Boolean algebraic expressions. We reduced the number of iterations of the Grover's algorithm by decreasing the number of superposed inputs in the initialize step using quantum permutation state. We show that our algorithm has less time complexity compared to previous study that solved the N -Queen problem using Grover's algorithm with W state as a input.

DOI
10.1109/ictc55196.2022.9952402

Related papers

Optimizing the Quantum Circuit for Solving Boolean Equations Based on Grover Search Algorithm

Hui Liu, Fukun Li, Yilin Fan

The solution of nonlinear Boolean equations in a binary field plays a crucial part in cryptanalysis and computational mathematics. To speed up the process of solving Boolean equations is an urgent task that needs to be addressed. In this paper, we propose a method for solving Boolean equations based on the Grover algorithm combined with preprocessing using classical algorithms, optimizing the quantum circuit for solving the equations, and implementing the automatic generation of quantum circuits. The method first converted Boolean equations into Boolean expressions to construct the oracle in the Grover algorithm. The quantum circuit was emulated based on the IBM Qiskit framework and then simulated the Grover algorithm on this basis. Finally, the solution of the Boolean equation was implemented. The experimental results proved the feasibility of using the Grover algorithm to solve nonlinear Boolean equations in a binary field, and the correct answer was successfully found under the conditions that the search space was 221 and three G iterations were used. The method in this paper increases the solving scale and solving speed of Boolean equations and enlarges the application area of the Grover algorithm.

Electronics•Aug 8, 2022•4 citations

Implementation of Efficient Quantum Computing Algorithm for Searching

Nirhali Atharva, Malwade Rohit, P. Akshay +2 more

The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.

International Research Journal on Advanced Engineering Hub (IRJAEH)•May 21, 2025•0 citations

Resource Efficient Boolean Function Solver on Quantum Computer

Xiang Li, Hanxiang Shen, Weiguo Gao +1 more

Nonlinear boolean equation systems play an important role in a wide range of applications. Grover's algorithm is one of the best-known quantum search algorithms in solving the nonlinear boolean equation system on quantum computers. In this paper, we propose three novel techniques to improve the efficiency under Grover's algorithm framework. A W-cycle circuit construction introduces a recursive idea to increase the solvable number of boolean equations given a fixed number of qubits. Then, a greedy compression technique is proposed to reduce the oracle circuit depth. Finally, a randomized Grover's algorithm randomly chooses a subset of equations to form a random oracle every iteration, which further reduces the circuit depth and the number of ancilla qubits. Numerical results on boolean quadratic equations demonstrate the efficiency of the proposed techniques.

arXiv:2310.05013•Quantum•Oct 10, 2024•1 citation

A Grover based Quantum Algorithm for Finding Pure Nash Equilibria in Graphical Games

Christoph Roch, Santiago Londoño Castillo, Claudia Linnhoff–Popien

The Grover algorithm and its underlying amplitude amplification process are one of the most essential and widely used building blocks of many other subsequent quantum methods. In this work, we adapt Grover’s search algorithm to find pure Nash equilibria in graphical games. In general, the main complexity lies in the construction of the algorithm’s oracle operator. We show how to set up the oracle from a given graphical game by translating it to a Boolean satisfiability problem, which can subsequently be logically synthesized to an oracle quantum circuit. We investigate the algorithm for random graphical game instances on IBM’s quantum simulator and give an outlook regarding the scaling of it.

IEEE International Conference on Software Architecture Companion (ICSA-C)•Mar 1, 2022•7 citations

Reducing Circuit Resources in Grover's Algorithm via Constraint-Aware Initialization

Eunok Bae, Jeonghyeon Shin, Minjin Choi

Grover's search algorithm provides a quadratic speedup over classical brute-force search in terms of query complexity and is widely used as a versatile subroutine in numerous quantum algorithms, including those for combinatorial problems with large search spaces. For such problems, it is natural to reduce the effective search space by incorporating problem constraints at the initialization step, which in Grover's algorithm can be achieved by preparing structured initial states that encode constraint information. In this work, we present a systematic framework with a simple preprocessing procedure for constraint-aware initialization in Grover's algorithm, focusing on problems with linear constraints. While such structured initial states can reduce the number of oracle queries required to obtain a solution, their preparation incurs additional circuit-level costs. We therefore offer a conservative circuit-level resource analysis, showing that the resulting constraint-aware initialization can improve resource efficiency in terms of gate counts and circuit depth. The validity of the framework is further demonstrated numerically using the exact-cover problem. Overall, our results indicate that this approach serves as a practical baseline for achieving more resource-efficient implementations of Grover's algorithm compared to the standard uniform initialization.

quant-pharXiv:2601.17725•Jan 27, 2026•0 citations

Synthesis of Vertex Coloring Problem Using Grover's Algorithm

Amit Saha, Avik Chongder, Sudhindu Bikash Mandal +1 more

Many applications such as Graph coloring, Triangle finding, Boolean satisfiability, Traveling salesman problem can be solved by Grover's search algorithm, which is one of the remarkable quantum computing algorithm. To design a quantum circuit for a given quantum algorithm, which involves Grover's search, we need to define an oracle circuit specific to the given algorithm and the diffusion operator for amplification of the desired quantum state. In this paper, we propose a quantum circuit implementation for the oracle of the vertex coloring problem based on Grover's algorithmic approach. To the best of our knowledge, this is a first of its kind approach in regards to the quantum circuit synthesis of the vertex coloring oracle in binary quantum domain. We have performed the synthesis of the proposed oracle circuit for the six commonly available Physical Machine Description (PMD) gate libraries using the Fault Tolerant Quantum Logic Synthesis (FTQLS) tool. The synthesis results have been presented to understand the cost estimation of the oracle circuit for the various PMDs in terms of number of quantum operations and number of cycles.

IEEE International Symposium on Nanoelectronic and Information Systems (iNIS)•Dec 1, 2015•12 citations
In this paper, we propose a construction method of Grover's algorithm to solve the N-Queen problem. Quantum permutation state was designed and applied to the initialization and amplitude amplification process in Grover's algorithm. An oracle-level quantum circuit was constructed using Boolean algebraic expressions. We reduced the number of iterations of the Grover's algorithm by decreasing the number of superposed inputs in the initialize step using quantum permutation state. We show that our algorithm has less time complexity compared to previous study that solved the N -Queen problem using Grover's algorithm with W state as a input.
The solution of nonlinear Boolean equations in a binary field plays a crucial part in cryptanalysis and computational mathematics. To speed up the process of solving Boolean equations is an urgent task that needs to be addressed. In this paper, we propose a method for solving Boolean equations based on the Grover algorithm combined with preprocessing using classical algorithms, optimizing the quantum circuit for solving the equations, and implementing the automatic generation of quantum circuits. The method first converted Boolean equations into Boolean expressions to construct the oracle in the Grover algorithm. The quantum circuit was emulated based on the IBM Qiskit framework and then simulated the Grover algorithm on this basis. Finally, the solution of the Boolean equation was implemented. The experimental results proved the feasibility of using the Grover algorithm to solve nonlinear Boolean equations in a binary field, and the correct answer was successfully found under the conditions that the search space was 221 and three G iterations were used. The method in this paper increases the solving scale and solving speed of Boolean equations and enlarges the application area of the Grover algorithm.
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.
Nonlinear boolean equation systems play an important role in a wide range of applications. Grover's algorithm is one of the best-known quantum search algorithms in solving the nonlinear boolean equation system on quantum computers. In this paper, we propose three novel techniques to improve the efficiency under Grover's algorithm framework. A W-cycle circuit construction introduces a recursive idea to increase the solvable number of boolean equations given a fixed number of qubits. Then, a greedy compression technique is proposed to reduce the oracle circuit depth. Finally, a randomized Grover's algorithm randomly chooses a subset of equations to form a random oracle every iteration, which further reduces the circuit depth and the number of ancilla qubits. Numerical results on boolean quadratic equations demonstrate the efficiency of the proposed techniques.
The Grover algorithm and its underlying amplitude amplification process are one of the most essential and widely used building blocks of many other subsequent quantum methods. In this work, we adapt Grover’s search algorithm to find pure Nash equilibria in graphical games. In general, the main complexity lies in the construction of the algorithm’s oracle operator. We show how to set up the oracle from a given graphical game by translating it to a Boolean satisfiability problem, which can subsequently be logically synthesized to an oracle quantum circuit. We investigate the algorithm for random graphical game instances on IBM’s quantum simulator and give an outlook regarding the scaling of it.
Grover's search algorithm provides a quadratic speedup over classical brute-force search in terms of query complexity and is widely used as a versatile subroutine in numerous quantum algorithms, including those for combinatorial problems with large search spaces. For such problems, it is natural to reduce the effective search space by incorporating problem constraints at the initialization step, which in Grover's algorithm can be achieved by preparing structured initial states that encode constraint information. In this work, we present a systematic framework with a simple preprocessing procedure for constraint-aware initialization in Grover's algorithm, focusing on problems with linear constraints. While such structured initial states can reduce the number of oracle queries required to obtain a solution, their preparation incurs additional circuit-level costs. We therefore offer a conservative circuit-level resource analysis, showing that the resulting constraint-aware initialization can improve resource efficiency in terms of gate counts and circuit depth. The validity of the framework is further demonstrated numerically using the exact-cover problem. Overall, our results indicate that this approach serves as a practical baseline for achieving more resource-efficient implementations of Grover's algorithm compared to the standard uniform initialization.
Many applications such as Graph coloring, Triangle finding, Boolean satisfiability, Traveling salesman problem can be solved by Grover's search algorithm, which is one of the remarkable quantum computing algorithm. To design a quantum circuit for a given quantum algorithm, which involves Grover's search, we need to define an oracle circuit specific to the given algorithm and the diffusion operator for amplification of the desired quantum state. In this paper, we propose a quantum circuit implementation for the oracle of the vertex coloring problem based on Grover's algorithmic approach. To the best of our knowledge, this is a first of its kind approach in regards to the quantum circuit synthesis of the vertex coloring oracle in binary quantum domain. We have performed the synthesis of the proposed oracle circuit for the six commonly available Physical Machine Description (PMD) gate libraries using the Fault Tolerant Quantum Logic Synthesis (FTQLS) tool. The synthesis results have been presented to understand the cost estimation of the oracle circuit for the various PMDs in terms of number of quantum operations and number of cycles.