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

The Effective Solving of the Tasks from NP by a Quantum Computer

S. S. Sysoev

Published Jan 23, 2014• 2 citations
arXivHTMLPDF

Abstract

The new model of quantum computation is proposed, for which an effective algorithm of solving any task in NP is described. The work is based and inspired be the Grover's algorithm for solving NP-tasks with quadratic speedup compared to the classical computation model. The provided model and algorithm exhibit the exponential speedup over that described by Grover.

DOI
10.48550/arxiv.1401.6030

Related papers

Quantum Computing Algorithms for Solving Complex Mathematical Problems

Et al. Lalit Mohan Trivedi

The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.

International Journal on Recent and Innovation Trends in Computing and Communication•Nov 7, 2023•2 citations

Finding stable models via quantum computation.

David Meyer, James Pommersheim, Jeffrey B. Remmel

Quantum computers have the potential to out-perform classical computers—certain quantum algorithms run much faster than any known alternative classical algorithm. For example, Grover showed that a quantum computer can search an unordered list of N items in time O ( √ N), providing a quadratic speed-up over the classical algorithm. In this paper, we show that we can modify Grover’s search algorithm to give an algorithm that finds stable models of an Answer Set Program with a similar quadratic improvement over the classical algorithm. Marek and Remmel showed that Answer Set Programming (ASP) programs can uniformly solve all NP-search problems, so our quantum algorithm to find stable models of ASP programs also solves all NP-search problems. It follows that Answer Set Programming could provide a programming language for quantum computation.

Non-Monotonic Reasoning•Jan 1, 2004•2 citations

Multi-layer quantum search and inclusion of NP into BQP

Shan Jin, Xiaoting Wang, Li, Bo

In this work, we present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. As direct applications, any NP problems can be solved efficiently on a quantum circuit with only polynomial gate complexity. In particular, such multi-layer search can solve the factoring problem with an exponential speedup, providing an alternative to Shor's algorithm. Our results show that the exponential speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated. With no contradiction to the quadratic optimality of single-layer query complexity, the great potential of Grover's search is fully released by such multi-layer search design.

arXiv:2004.11347•Apr 23, 2020•1 citation

Complexity and algorithms in quantum computation

Richard Jozsa

In 1982 Feynman noted that the simulation of a quantum process on a classical computer appears to generally involve an exponential slowdown in running time compared to the evolution of the process itself. More recently in quantum computation this effect has been turned around and exploited for computational advantage by formulating quantum processes (quantum algorithms) whose evolution corresponds to the performance of useful computational tasks. Thus the quantum algorithm will engender an exponential speedup in computing time. The most famous such quantum algorithm is Shor's algorithm for factorising whole numbers. It factorises a number having d digits in a time of order less than d whereas no known classical algorithm can perform factorisation in a time bounded by any polynomial in d. In theoretical computer science, computational complexity is generally characterised by classifying computational tasks into complexity classes such as P, BPP and NP. It therefore appears that quantum computers will be able to transgress some of the boundaries set by these classes. (2 pages)

•Jan 1, 1997•15 citations

Implementation of Grover's Algorithm based on Quantum Reservoir Computing

Shivani Mehta, Vidya Praveen Bhallamudi, Arige Sumanth +1 more

Quantum computing represents the leading edge of computational technology, leveraging the principles of quantum mechanics to execute targeted computations much faster than classical computers. In contrast to classical bits, which are limited to representing either 0 or 1, qubits, or quantum bits, exhibit the extraordinary property of superposition. This distinctive characteristic enables qubits to simultaneously occupy multiple states, empowering quantum computers to explore numerous potential solutions to a problem concurrently. This feature makes quantum computing particularly potent for specific tasks. Recent research endeavors have been sparked by the potential of advanced quantum computing technology, leading to the creation of simulations of quantum computers using classical hardware. Grover's quantum search algorithm serves as a notable illustration of quantum computing application, enabling quantum computers to conduct a database search within an unsorted array with a quadratic speedup in time efficiency compared to classical computers. This document presents the quantum Grover search algorithm and its application through 5-qubit quantum circuits, as well as a design framework to simplify the creation of an oracle for a greater number of qubits.

International Conference for Emerging Technology (INCET)•May 24, 2024•2 citations

Progress and Challenges in Quantum Computing Algorithms for NP-Hard Problems

Mohammed I. Younis, Abeer Salim Jamil, Ahmed Hamid Abdulrazzaq +3 more

Background: Traditional computers can be inadequate to solve computationally complex problems, generally known as NP-hard problems, for example, optimization, cryptography, and network design. Quantum Computing is referred to as a breakthrough paradigm, that exploits the principles of quantum physics for performing computation in an exceedingly efficient manner.Objective: This study aims to explore the abilities of quantum algorithms in capturing NP-hard problems and discuss their strengths and limitations. The article illustrates how algorithms like Grover's and Shor's may offer exponential or polynomial improvements under specific circumstances.Methodology: The study provides a thorough survey of present-day quantum algorithms and analyzes their capabilities as well as limitations. This article examines advancements in hardware innovation and error correction methods to assess their ability to address the challenges of limited scalability and elevated error rates currently hindering their adoption.Results: The article underscores the profound impact of quantum computing on NP-hard problems. However, significant barriers remain, such as the inherent limitations of hardware, universality with respect to programming language and robust error correction capabilities.Conclusion: The article shows important progress and open problems for solving NP-hard problems using quantum algorithms. The results reveal the capabilities to achieve significant computational speedup with algorithms such as Grover’s and Shor's especially in concert when current quantum hardware matures along with novel error correction techniques. Nevertheless, scholars have to investigate more about scalability and the creation of standard programming languages for quantum computers.

Conference of Open Innovations Association (FRUCT)•Oct 30, 2024•10 citations
The new model of quantum computation is proposed, for which an effective algorithm of solving any task in NP is described. The work is based and inspired be the Grover's algorithm for solving NP-tasks with quadratic speedup compared to the classical computation model. The provided model and algorithm exhibit the exponential speedup over that described by Grover.
The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.
Quantum computers have the potential to out-perform classical computers—certain quantum algorithms run much faster than any known alternative classical algorithm. For example, Grover showed that a quantum computer can search an unordered list of N items in time O ( √ N), providing a quadratic speed-up over the classical algorithm. In this paper, we show that we can modify Grover’s search algorithm to give an algorithm that finds stable models of an Answer Set Program with a similar quadratic improvement over the classical algorithm. Marek and Remmel showed that Answer Set Programming (ASP) programs can uniformly solve all NP-search problems, so our quantum algorithm to find stable models of ASP programs also solves all NP-search problems. It follows that Answer Set Programming could provide a programming language for quantum computation.
In this work, we present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. As direct applications, any NP problems can be solved efficiently on a quantum circuit with only polynomial gate complexity. In particular, such multi-layer search can solve the factoring problem with an exponential speedup, providing an alternative to Shor's algorithm. Our results show that the exponential speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated. With no contradiction to the quadratic optimality of single-layer query complexity, the great potential of Grover's search is fully released by such multi-layer search design.
In 1982 Feynman noted that the simulation of a quantum process on a classical computer appears to generally involve an exponential slowdown in running time compared to the evolution of the process itself. More recently in quantum computation this effect has been turned around and exploited for computational advantage by formulating quantum processes (quantum algorithms) whose evolution corresponds to the performance of useful computational tasks. Thus the quantum algorithm will engender an exponential speedup in computing time. The most famous such quantum algorithm is Shor's algorithm for factorising whole numbers. It factorises a number having d digits in a time of order less than d whereas no known classical algorithm can perform factorisation in a time bounded by any polynomial in d. In theoretical computer science, computational complexity is generally characterised by classifying computational tasks into complexity classes such as P, BPP and NP. It therefore appears that quantum computers will be able to transgress some of the boundaries set by these classes. (2 pages)
Quantum computing represents the leading edge of computational technology, leveraging the principles of quantum mechanics to execute targeted computations much faster than classical computers. In contrast to classical bits, which are limited to representing either 0 or 1, qubits, or quantum bits, exhibit the extraordinary property of superposition. This distinctive characteristic enables qubits to simultaneously occupy multiple states, empowering quantum computers to explore numerous potential solutions to a problem concurrently. This feature makes quantum computing particularly potent for specific tasks. Recent research endeavors have been sparked by the potential of advanced quantum computing technology, leading to the creation of simulations of quantum computers using classical hardware. Grover's quantum search algorithm serves as a notable illustration of quantum computing application, enabling quantum computers to conduct a database search within an unsorted array with a quadratic speedup in time efficiency compared to classical computers. This document presents the quantum Grover search algorithm and its application through 5-qubit quantum circuits, as well as a design framework to simplify the creation of an oracle for a greater number of qubits.
Background: Traditional computers can be inadequate to solve computationally complex problems, generally known as NP-hard problems, for example, optimization, cryptography, and network design. Quantum Computing is referred to as a breakthrough paradigm, that exploits the principles of quantum physics for performing computation in an exceedingly efficient manner.Objective: This study aims to explore the abilities of quantum algorithms in capturing NP-hard problems and discuss their strengths and limitations. The article illustrates how algorithms like Grover's and Shor's may offer exponential or polynomial improvements under specific circumstances.Methodology: The study provides a thorough survey of present-day quantum algorithms and analyzes their capabilities as well as limitations. This article examines advancements in hardware innovation and error correction methods to assess their ability to address the challenges of limited scalability and elevated error rates currently hindering their adoption.Results: The article underscores the profound impact of quantum computing on NP-hard problems. However, significant barriers remain, such as the inherent limitations of hardware, universality with respect to programming language and robust error correction capabilities.Conclusion: The article shows important progress and open problems for solving NP-hard problems using quantum algorithms. The results reveal the capabilities to achieve significant computational speedup with algorithms such as Grover’s and Shor's especially in concert when current quantum hardware matures along with novel error correction techniques. Nevertheless, scholars have to investigate more about scalability and the creation of standard programming languages for quantum computers.