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

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, Sandhya Jayaraman, Bikash K. Behera, Prasanta Kumar Panigrahi

Published Jun 26, 2018• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1806.10221

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

A Quantum-Inspired Differential Evolution Algorithm for Rigid Image Registration.

Amer Draa, Mohamed Batouche, Hichem Talbi

Abstract: In this paper, a quantum-inspired differential evolution algorithm for solving the N-queens problem is presented. The N-queens problem aims at placing N queens on an NxN chessboard, in such a way that no queen could capture any of the others. The proposed algorithm is a novel hybridization between differential evolution algorithms and quantum computing principles. Accordingly, differential evolution algorithms have been enhanced by the adoption of some quantum concepts such as quantum bits and states superposition. The use of the quantum interference has allowed this hybrid approach to have a remarkable efficiency and good results. Keywords: Quantum computing, differential evolution, N-queens problem, combinatorial optimization.

International Conference on Computational Intelligence•Jan 1, 2004•20 citations

Solving the N-Queens Puzzle by a QUBO Model with Quadratic Size

Shunsuke Tsukiyama, Koji Nakano, Yasuaki Ito +6 more

A quadratic unconstrained binary optimization (QUBO) model is defined by an objective function that consists of a quadratic formula involving multiple binary variables. The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the objective function. One of the most well-known problems that can be reduced to a QUBO problem is the N-Queens problem. The N-Queens problem seeks to find a configuration of n queens on an $n\times n$ chessboard such that no two queens can attack each other. It is widely recognized that a conventional technique can be used to design a QUBO model with an $n\times n$ matrix of binary variables representing the chessboard, where a queen is placed in a particular position if and only if the corresponding binary variable is set to 1. This technique involves incorporating terms in the objective function to ensure that the sum of each row and column is 1, and the sum of each diagonal and anti-diagonal is either 0 or 1. The resulting reduced QUBO model contains $\displaystyle \frac{5}{3}n^{3}-2n^{2}+\frac{1}{3}n$ quadratic terms. Due to the simplicity and straightforwardness of designing such a QUBO model, there are numerous resources available that explain this model as an easy example of QUBO models. However, to the best of our knowledge, no fundamentally different approach to designing a QUBO model for the N-Queens problem has been discovered. The prevailing view within the community is that this approach is the only method for designing a QUBO model for the N-Queens problem, and no superior alternative has been found. In this paper, we will present a counterintuitive result that demonstrates a more efficient QUBO model for the N-Queens problem, requiring fewer quadratic terms. Surprisingly, this alternative model involves only $12n^{2}-24n+12$ quadratic terms, which is smaller than the conventional QUBO model whenever n is greater than or equal to 7. This discovery marks a significant breakthrough in the theoretical challenge of minimizing a QUBO model for solving the N-Queens problem.

International Symposium on Computing and Networking•Nov 28, 2023•4 citations

N-Queens Problem Resolution Using the Quantum Computing Model

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

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.

IEEE Latin America Transactions•Mar 1, 2017•6 citations

Satellite Communication Over Quantum Channel

László Bacsárdi

Abstract Quantum computing offers revolutionary solutions in the field of computer sciences, applying the opportunities of quantum physics which are incomparably richer than classical physics. Although quantum computers are going to be the tools of the far future, there are already a few algorithms to solve problems which are very difficult to handle with traditional computers. Perhaps the easiest example of a structure of a quantum system is a quantum channel. Typically, one is interested in some basis in the Hilbert space representing the input of a channel, which is entangled with a second Hilbert space representing the environment, and then another (possibly the same) basis for the first space at a later time. Free-space quantum key distribution (QKD)—over an optical path of about 30 cm—was first introduced in 1991, and recent advances have led to demonstrations. Indeed there are certain key distribution problems in this category for which free-space QKD has practical advantages (for example it is not practical to send a courier to a satellite). Quantum computing algorithms can be used to affirm our communication in several ways (open-air communication, satellite communications, satellite broadcast, satellite-satellite communication). We set up a free-space quantum-channel-model at the university and made several simulations. The main aim is to trace some adoptable algorithms in the communication between Earth and the satellite and also between satellites. This paper is a theoretical study to compare the simulation results of the three models.

International Astronautical Congress (IAC)•Oct 2, 2006•0 citations
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.
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.
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.
Abstract: In this paper, a quantum-inspired differential evolution algorithm for solving the N-queens problem is presented. The N-queens problem aims at placing N queens on an NxN chessboard, in such a way that no queen could capture any of the others. The proposed algorithm is a novel hybridization between differential evolution algorithms and quantum computing principles. Accordingly, differential evolution algorithms have been enhanced by the adoption of some quantum concepts such as quantum bits and states superposition. The use of the quantum interference has allowed this hybrid approach to have a remarkable efficiency and good results. Keywords: Quantum computing, differential evolution, N-queens problem, combinatorial optimization.
A quadratic unconstrained binary optimization (QUBO) model is defined by an objective function that consists of a quadratic formula involving multiple binary variables. The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the objective function. One of the most well-known problems that can be reduced to a QUBO problem is the N-Queens problem. The N-Queens problem seeks to find a configuration of n queens on an n×nn\times nn×n chessboard such that no two queens can attack each other. It is widely recognized that a conventional technique can be used to design a QUBO model with an n×nn\times nn×n matrix of binary variables representing the chessboard, where a queen is placed in a particular position if and only if the corresponding binary variable is set to 1. This technique involves incorporating terms in the objective function to ensure that the sum of each row and column is 1, and the sum of each diagonal and anti-diagonal is either 0 or 1. The resulting reduced QUBO model contains 53n3−2n2+13n\displaystyle \frac{5}{3}n^{3}-2n^{2}+\frac{1}{3}n35​n3−2n2+31​n quadratic terms. Due to the simplicity and straightforwardness of designing such a QUBO model, there are numerous resources available that explain this model as an easy example of QUBO models. However, to the best of our knowledge, no fundamentally different approach to designing a QUBO model for the N-Queens problem has been discovered. The prevailing view within the community is that this approach is the only method for designing a QUBO model for the N-Queens problem, and no superior alternative has been found. In this paper, we will present a counterintuitive result that demonstrates a more efficient QUBO model for the N-Queens problem, requiring fewer quadratic terms. Surprisingly, this alternative model involves only 12n2−24n+1212n^{2}-24n+1212n2−24n+12 quadratic terms, which is smaller than the conventional QUBO model whenever n is greater than or equal to 7. This discovery marks a significant breakthrough in the theoretical challenge of minimizing a QUBO model for solving the N-Queens problem.
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.
Abstract Quantum computing offers revolutionary solutions in the field of computer sciences, applying the opportunities of quantum physics which are incomparably richer than classical physics. Although quantum computers are going to be the tools of the far future, there are already a few algorithms to solve problems which are very difficult to handle with traditional computers. Perhaps the easiest example of a structure of a quantum system is a quantum channel. Typically, one is interested in some basis in the Hilbert space representing the input of a channel, which is entangled with a second Hilbert space representing the environment, and then another (possibly the same) basis for the first space at a later time. Free-space quantum key distribution (QKD)—over an optical path of about 30 cm—was first introduced in 1991, and recent advances have led to demonstrations. Indeed there are certain key distribution problems in this category for which free-space QKD has practical advantages (for example it is not practical to send a courier to a satellite). Quantum computing algorithms can be used to affirm our communication in several ways (open-air communication, satellite communications, satellite broadcast, satellite-satellite communication). We set up a free-space quantum-channel-model at the university and made several simulations. The main aim is to trace some adoptable algorithms in the communication between Earth and the satellite and also between satellites. This paper is a theoretical study to compare the simulation results of the three models.