A Quantum Approach to solve N-Queens Problem

• URL: http://arxiv.org/abs/2312.16312v1
• Date: Tue, 26 Dec 2023 19:42:05 GMT
• Title: A Quantum Approach to solve N-Queens Problem
• Authors: Santhosh G S, Piyush Joshi, Ayan Barui and Prasanta K. Panigrahi
• Abstract summary: We have introduced two innovative quantum algorithms to solve N-Queens problem. N-Queens problem involves the arrangement of $N$ queens on a $N times N$ chessboard such that they are not under attack from each other on the same row, column and diagonal. The algorithms utilize Controlled W-states and dynamic circuits, to efficiently address this NP-Complete computational problem.
• Score: 0.7373617024876725
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• An effcient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems [7.839882853089659]
  We propose a variational quantum Korkin-Zolotarev (VQKZ) algorithm, which significantly reduces the qubit requirement for solving the shortest vector problem (SVP)<n>By transforming the original SVP into a series of subproblems on projected sublattices, the proposed VQKZ algorithm enables near-term quantum devices to solve SVP instances with lattice dimensions 61.39% larger than those solvable by previous methods.
  arXiv  Detail & Related papers  (2025-05-13T09:32:21Z)
• A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits [0.0]
  We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within gate complexity. Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation.
  arXiv  Detail & Related papers  (2025-02-12T23:58:25Z)
• Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup [4.913177281640608]
  Gram-Schmidt process is widely used to solve Vector set normalization and matrix QR decomposition. Existing methods have problems of high complexity, scaling $O(N3)$ in the system dimension $N$. We propose quantum algorithms to solve these two problems based on the idea of Gram-Schmidt process and quantum phase estimation.
  arXiv  Detail & Related papers  (2024-12-26T07:04:34Z)
• Circuit Design of Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems [1.4513830934124627]
  We propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state.
  arXiv  Detail & Related papers  (2024-05-12T01:44:19Z)
• The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
  We propose two quantum algorithms for solving quantum linear systems of equations with coherent superposition. The two quantum algorithms can both compute the rank and general solution by one measurement. Our analysis indicates that the proposed algorithms are mainly suitable for conducting attacks against lightweight symmetric ciphers.
  arXiv  Detail & Related papers  (2024-05-11T03:03:14Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future. In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
  arXiv  Detail & Related papers  (2024-01-25T17:37:40Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms. We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
  arXiv  Detail & Related papers  (2023-09-22T18:00:03Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Implementable Hybrid Quantum Ant Colony Optimization Algorithm [0.0]
  We propose a new hybrid quantum algorithm to produce approximate solutions for NP-hard problems. We develop an improved algorithm that can be truly implemented on near-term quantum computers. The benchmarks made by simulating the noiseless quantum circuit and the experiments made on IBM quantum computers show the validity of the algorithm.
  arXiv  Detail & Related papers  (2021-07-08T13:50:51Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
  We review and extend the application of deep learning to quantum geometric control problems. We demonstrate enhancements in time-optimal control in the context of quantum circuit synthesis problems. Our results are of interest to researchers in quantum control and quantum information theory seeking to combine machine learning and geometric techniques for time-optimal control problems.
  arXiv  Detail & Related papers  (2020-06-19T19:12:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.