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:quant-ph/0301153

Solving a problem in the quantum way

M.P. John

Published Jan 28, 2003• 0 citations
arXivHTMLPDF

Abstract

A general quantum algorithm for solving a problem is discussed. The number of steps required to solve a problem using this method is independent of the number of cases that has to be considered classically. Hence, it is more efficient than existing classical algorithms or quantum algorithm, which requires O(sqrt(N)) steps.
DOI
10.48550/arxiv.quant-ph/0301153

Related papers

A Quantum Algorithm for finding the Maximum

Ahuja, Ashish, Sanjiv Kapoor

This paper describes a quantum algorithm for finding the maximum among N items. The classical method for the same problem takes O(N) steps because we need to compare two numbers in one step. This algorithm takes O(sqrt(N)) steps by exploiting the property of quantum states to exist in a superposition of states and hence performing an operation on a number of elements in one go. A tight upper bound of 6.8(sqrt(N)) for the number of steps needed using this algorithm was found. These steps are the number of queries made to the oracle.

arXiv:quant-ph/9911082•Nov 18, 1999•42 citations

Rapid solution of problems by quantum computation

David Deutsch, Richard Jozsa

Abstract A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.

Proceedings of the Royal Society of London Series A Mathematical and Physical Sciences•Dec 8, 1992•2,675 citations

Solving Highly Constrained Search Problems with Quantum Computers

Tad Hogg

A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms.

arXiv:1105.5459•Journal of Artificial Intelligence Research•Feb 1, 1999•5 citations

Solving Highly Constrained Search Problems with Quantum Computers

Tad Hogg

A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms. 1. Introduction Quantum computers (Benioff, 1982; Bernstein & Vazirani, 1993; Deutsch, 1985, 1989; DiVincenzo, 1995; Feynman, 1986; Lloyd, 1993) offer a new approach to combinatorial search problems (Garey & Johnson, 1979) with quantum parallelism, i.e., the abilit...

•Jan 1, 1998•9 citations

Introduction to Quantum Algorithms

Peter W. Shor

These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms. So far, we have only discovered a few techniques which can produce speed up versus classical algorithms. It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.

arXiv:quant-ph/0005003•Apr 29, 2000•78 citations

Effectiveness of quantum algorithms on classical computing complexities

Hicham Amellal, Abdelmajid Meslouhi, Abderrahim El Allati

In this paper, we analyze the effectiveness of quantum algorithms to solve some classical computing complexities. In fact, we focus in this study on several famous quantum algorithms, where we discussed their impact on classical computing using in computer science.

International Conference on Smart City Applications (SCA)•Oct 10, 2018•2 citations
This paper describes a quantum algorithm for finding the maximum among N items. The classical method for the same problem takes O(N) steps because we need to compare two numbers in one step. This algorithm takes O(sqrt(N)) steps by exploiting the property of quantum states to exist in a superposition of states and hence performing an operation on a number of elements in one go. A tight upper bound of 6.8(sqrt(N)) for the number of steps needed using this algorithm was found. These steps are the number of queries made to the oracle.
A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms.
A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms. 1. Introduction Quantum computers (Benioff, 1982; Bernstein & Vazirani, 1993; Deutsch, 1985, 1989; DiVincenzo, 1995; Feynman, 1986; Lloyd, 1993) offer a new approach to combinatorial search problems (Garey & Johnson, 1979) with quantum parallelism, i.e., the abilit...