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

IEEE Latin America Transactions

N-Queens Problem Resolution Using the Quantum Computing Model

Flavio Jesus de Souza, Flávio Luís de Mello

Published Mar 1, 2017• 6 citations
Publisher

Abstract

This paper aims to propose solution for a classical and difficult decision problem using quantum computing. At first, it provides experimental samples taking well-known search problems, where it is possible to establish a plausible comparison between classical search algorithms and a similar quantum algorithm. Moreover, a quantum algorithm is construct in order to deliver solution for a sophisticated mathematical problem called N-Queens. The algorithm was implemented in a quantum computing simulator obtaining solutions for problems with up to 128 queens at a reasonable cost.

DOI
10.1109/tla.2017.7867605

Related papers

A Quantum Approach to Solve N-Queens Problem

G S Santhosh, Piyush Joshi, Ayan Barui +1 more

In this work, we have introduced two innovative quantum algorithms: the Direct Column Algorithm and the Quantum Backtracking Algorithm to solve N-Queens problem, which involves the arrangement of $N$ queens on an $N \times N$ chessboard such that they are not under attack from each other on the same row, column and diagonal. These algorithms utilizes Controlled W-states and dynamic circuits, to efficiently address this NP-Complete computational problem. The Direct Column Algorithm strategically reduces the search space, simplifying the solution process, even with exponential circuit complexity as the problem size grows, while Quantum Backtracking Algorithm emulates classical backtracking techniques within a quantum framework which allows the possibility of solving complex problems like satellite communication, routing and VLSI testing.

arXiv:2312.16312•International Conference on Communication Systems & Networks (COMSNETS)•Jan 3, 2024•1 citation

A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience

Rounak Jha, Debaiudh Das, Avinash Dash +3 more

Quantum computers can potentially solve problems that are computationally intractable on a classical computer in polynomial time using quantum-mechanical effects such as superposition and entanglement. The N-Queens Problem is a notable example that falls under the class of NP-complete problems. It involves the arrangement of N chess queens on an N x N chessboard such that no queen attacks any other queen, i.e. no two queens are placed along the same row, column or diagonal. The best time complexity that a classical computer has achieved so far in generating all solutions of the N-Queens Problem is of the order O(N!). In this paper, we propose a new algorithm to generate all solutions to the N-Queens Problem for a given N in polynomial time of order O(N^3) and polynomial memory of order O(N^2) on a quantum computer. We simulate the 4-queens problem and demonstrate its application to satellite communication using IBM Quantum Experience platform.

arXiv:1806.10221•Jun 26, 2018•14 citations

A Quantum N-Queens Solver

Valentin Torggler, Philipp Aumann, Helmut Ritsch +1 more

The N -queens problem is to find the position of N queens on an N by N chess board such that no queens attack each other. The excluded diagonals N -queens problem is a variation where queens cannot be placed on some predefined fields along diagonals. This variation is proven NP-complete and the parameter regime to generate hard instances that are intractable with current classical algorithms is known. We propose a special purpose quantum simulator that implements the excluded diagonals N -queens completion problem using atoms in an optical lattice and cavity-mediated long-range interactions. Our implementation has no overhead from the embedding allowing to directly probe for a possible quantum advantage in near term devices for optimization problems.

arXiv:1803.00735•Quantum•Jun 3, 2019•20 citations

[The NMR implementation of quantum algorithm].

Xuemei Luo

A quantum computer is a device that processes information in a quantum-mechanically coherent fashion. In principle, it can exploit coherent quantum interference and entanglement to perform computations, such as factoring large numbers or searching an unsorted database, more rapidly than classical computers. Noise, decoherence, and manufacturing problems make constructing large scale quantum computers difficult. Ion traps and optical cavities offer promising experimental approaches, but no quantum algorithm has yet been implemented with those systems. On the other hand, because of their natural isolation from the environment, nuclear spins are particularly good 'quantum bits', and their use for quantum computation is possible by applying nuclear magnetic resonance (NMR) techniques in an unconventional manner. Here, we report on the experimental implementation of a quantum algorithm using NMR to solve a purely mathematical problem in fewer steps than is possible classically. Our simple quantum computer can determine the type of an unknown function using fewer function 'calls' than is possible using a classical computer.

•Feb 1, 2003•0 citations

Classical simulation of Grovers quantum algorithm

Jairo Ernesto Castillo Hernández, Yesenia Sierra, Nelson L. Cubillos

This paper in a didactic way, presents an introduction to quantum computing where some quantum formalisms are analyzed to finally address Grover's algorithm. It is widely known that this algorithm is one of the key algorithms in quantum computing, being its ability to explode successfully the superposition principle one of the reasons. In addition, this algorithm can be used for both locating efficiently a specific element in a cluttered database and solving certain problems when it is difficult finding a proper solution, but at the same time it is very simple to try with possible candidates. Finally, a simulation of this algorithm is carried out and the results are compared with other classical algorithms to illustrate the significant potential advantages of quantum computing.

Revista Brasileira de Ensino de Física•Nov 9, 2019•4 citations

Quantum Algorithms and Hard Problems

C. Vidya Raj, H. D. Phaneendra, M. S. Shivakumar

Any computation is necessarily a physical process. The current drive towards increasing speed and miniaturization of computers lead modern technology towards the subatomic domain - quantum computing, where strange quantum behavior takes over from familiar classical notions. The quantum computers have the ability to solve problems with varied computational complexities and more importantly hard problems. A problem is said to be hard, if the best possible algorithm requires exponential resources. This exponential quantum parallelism is the basis for the quantum speedup of many algorithms, and has made the construction of fast algorithms for quantum computers possible. Various proposals exist for modeling and devising procedures on computational problems related to factoring, searching, quantum counting, generalization of quantum algorithms etc. (Shor, 1994). In this paper, we have discussed the importance of algorithms such as order-finding, factoring and quantum searching which require exorbitant resources for their solution which otherwise is impossible on a classical computer

IEEE International Conference on Cognitive Informatics•Jul 1, 2006•5 citations
This paper aims to propose solution for a classical and difficult decision problem using quantum computing. At first, it provides experimental samples taking well-known search problems, where it is possible to establish a plausible comparison between classical search algorithms and a similar quantum algorithm. Moreover, a quantum algorithm is construct in order to deliver solution for a sophisticated mathematical problem called N-Queens. The algorithm was implemented in a quantum computing simulator obtaining solutions for problems with up to 128 queens at a reasonable cost.
In this work, we have introduced two innovative quantum algorithms: the Direct Column Algorithm and the Quantum Backtracking Algorithm to solve N-Queens problem, which involves the arrangement of NNN queens on an N×NN \times NN×N chessboard such that they are not under attack from each other on the same row, column and diagonal. These algorithms utilizes Controlled W-states and dynamic circuits, to efficiently address this NP-Complete computational problem. The Direct Column Algorithm strategically reduces the search space, simplifying the solution process, even with exponential circuit complexity as the problem size grows, while Quantum Backtracking Algorithm emulates classical backtracking techniques within a quantum framework which allows the possibility of solving complex problems like satellite communication, routing and VLSI testing.
Quantum computers can potentially solve problems that are computationally intractable on a classical computer in polynomial time using quantum-mechanical effects such as superposition and entanglement. The N-Queens Problem is a notable example that falls under the class of NP-complete problems. It involves the arrangement of N chess queens on an N x N chessboard such that no queen attacks any other queen, i.e. no two queens are placed along the same row, column or diagonal. The best time complexity that a classical computer has achieved so far in generating all solutions of the N-Queens Problem is of the order O(N!). In this paper, we propose a new algorithm to generate all solutions to the N-Queens Problem for a given N in polynomial time of order O(N^3) and polynomial memory of order O(N^2) on a quantum computer. We simulate the 4-queens problem and demonstrate its application to satellite communication using IBM Quantum Experience platform.
The N -queens problem is to find the position of N queens on an N by N chess board such that no queens attack each other. The excluded diagonals N -queens problem is a variation where queens cannot be placed on some predefined fields along diagonals. This variation is proven NP-complete and the parameter regime to generate hard instances that are intractable with current classical algorithms is known. We propose a special purpose quantum simulator that implements the excluded diagonals N -queens completion problem using atoms in an optical lattice and cavity-mediated long-range interactions. Our implementation has no overhead from the embedding allowing to directly probe for a possible quantum advantage in near term devices for optimization problems.
A quantum computer is a device that processes information in a quantum-mechanically coherent fashion. In principle, it can exploit coherent quantum interference and entanglement to perform computations, such as factoring large numbers or searching an unsorted database, more rapidly than classical computers. Noise, decoherence, and manufacturing problems make constructing large scale quantum computers difficult. Ion traps and optical cavities offer promising experimental approaches, but no quantum algorithm has yet been implemented with those systems. On the other hand, because of their natural isolation from the environment, nuclear spins are particularly good 'quantum bits', and their use for quantum computation is possible by applying nuclear magnetic resonance (NMR) techniques in an unconventional manner. Here, we report on the experimental implementation of a quantum algorithm using NMR to solve a purely mathematical problem in fewer steps than is possible classically. Our simple quantum computer can determine the type of an unknown function using fewer function 'calls' than is possible using a classical computer.
This paper in a didactic way, presents an introduction to quantum computing where some quantum formalisms are analyzed to finally address Grover's algorithm. It is widely known that this algorithm is one of the key algorithms in quantum computing, being its ability to explode successfully the superposition principle one of the reasons. In addition, this algorithm can be used for both locating efficiently a specific element in a cluttered database and solving certain problems when it is difficult finding a proper solution, but at the same time it is very simple to try with possible candidates. Finally, a simulation of this algorithm is carried out and the results are compared with other classical algorithms to illustrate the significant potential advantages of quantum computing.
Any computation is necessarily a physical process. The current drive towards increasing speed and miniaturization of computers lead modern technology towards the subatomic domain - quantum computing, where strange quantum behavior takes over from familiar classical notions. The quantum computers have the ability to solve problems with varied computational complexities and more importantly hard problems. A problem is said to be hard, if the best possible algorithm requires exponential resources. This exponential quantum parallelism is the basis for the quantum speedup of many algorithms, and has made the construction of fast algorithms for quantum computers possible. Various proposals exist for modeling and devising procedures on computational problems related to factoring, searching, quantum counting, generalization of quantum algorithms etc. (Shor, 1994). In this paper, we have discussed the importance of algorithms such as order-finding, factoring and quantum searching which require exorbitant resources for their solution which otherwise is impossible on a classical computer