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

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.

arXiv comment9 pages, 2 figures

References in corpus (3)

• Exploiting Feature and Class Relationships in Video Categorization with Regularized Deep Neural Networks
• Generation of N-qubit W state with rf-SQUID qubits by adiabatic passage
• Quantum Annealing and the Satisfiability Problem

Cited by in corpus (5)

• Experimental Demonstration of Quantum Tunneling in IBM Quantum Computer
• Quantum Simulation of Klein Gordon Equation and Observation of Klein Paradox in IBM Quantum Computer
• Demonstration of a general fault-tolerant quantum error detection code for (2n+1)-qubit entangled state on IBM 16-qubit quantum computer
• Spin-Boson Model to Demonstrate Quantum Tunneling in Biomolecules using IBM Quantum Computer
• Simulation of Lennard-Jones Potential on a Quantum Computer