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
N queens on an
N×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.
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×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×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
35n3−2n2+31n 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+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.
Achieving quantum advantage remains a milestone in the noisy intermediate-scale quantum era. Without complexity proofs, scaling advantage—where quantum resource requirements grow more slowly than their classical counterparts—is the primary indicator. However, direct applications of quantum optimization algorithms to classically intractable problems have yet to demonstrate this advantage. Here we develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem. We propose a restricting space reduction algorithm that achieves optimal search-space dimensionality under mod-2 arithmetic, thereby reducing qubit requirements and time complexity. Numerical studies on instances with up to 70 variables demonstrate that our enhanced quantum approximate optimization algorithm- and quantum adiabatic algorithm-based solvers outperform state-of-the-art classical solvers; the quantum adiabatic algorithm-based solver serves as a lower-bound reference while retaining scaling advantage. Furthermore, experiments on a 13-qubit superconducting processor confirm the predicted improvements. Collectively, our results provide empirical evidence of quantum speedup for an NP-complete problem. This study develops enhanced quantum solvers for an NP-complete Boolean satisfiability problem and reports empirical scaling advantages over leading classical solvers in large-scale simulations, with supporting validation on a superconducting quantum processor.
In this article we keep digging into the capabilities of optical lattices as simulators, showing how they can also be a powerful tool for simulating phenomena traditionally linked to quantum-optical systems (a study that we began in de Vega et al., (2008)). The basic idea consists of connecting an atomic state trapped in the optical lattice to a non trapped state through a Raman scheme. The coupling between these two types of atoms (trapped and free) turns out to be similar to that describing light-matter interaction within the rotating-wave approximation, the role of matter and photons being played by the trapped and free atoms, respectively.