2018/06/26 by Rounak Jha, Debaiudh Das, Jha, Rounak +9 · 1 citation
Computer Science · Physics and Astronomy · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1806.10221
9 pages, 2 figures
openalex publication_date 2018/06/26 · arxiv created 2018/07/30 · arxiv updated 2018/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(N3) and polynomial memory of order O(N2) on a quantum computer. We simulate the 4-queens problem and demonstrate its application to satellite communication using IBM Quantum Experience platform.