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

Bulletin of the European Association for Theoretical Computer Science

Can Quantum Computers Be Useful When There are Not Yet Enough Qubits

Luc Longpré, Владик Крейнович

Published Jan 1, 2003• 3 citations
OpenAlex

Abstract

this paper, we start answering this question by showing the following: for quantum search, even when we do not have enough qubits, we can still get a partial speedup. The fact that we do get a partial speedup for quantum search makes us hope that even when we do not have all the qubits, we can still get a partial speedup for other quantum computing algorithms as well

Related papers

Computational Speedups Using Small Quantum Devices

Vedran Dunjko, Yimin Ge, J. I. Cirac

Suppose we have a small quantum computer with only M qubits. Can such a device genuinely speed up certain algorithms, even when the problem size is much larger than M? Here we answer this question to the affirmative. We present a hybrid quantum-classical algorithm to solve 3-satisfiability problems involving n≫M variables that significantly speeds up its fully classical counterpart. This question may be relevant in view of the current quest to build small quantum computers.

arXiv:1807.08970•Physical Review Letters•Dec 18, 2018•45 citations

Demonstration of the Essentiality of Entanglement in a Deutsch-like Quantum Algorithm

He-Liang Huang, Ashutosh Goswami, Wan‐Su Bao +1 more

Quantum algorithms could efficiently solve certain classically intractable problems by exploiting quantum parallelism. To date, whether the quantum entanglement is useful or not for quantum computing is still a question of debate. Here, we present a new quantum algorithm to show that entanglement could help to gain advantage over classical algorithm and even the quantum algorithm without entanglement. Furthermore, we implement experiments to demonstrate our proposed algorithm using superconducting qubits. Our results show the viability of the algorithm and suggest that entanglement is essential in getting quantum speedup for certain problems in quantum computing, which provide a reliable and clear guidance for developing useful quantum algorithms in future.

arXiv:1706.09489•Jun 28, 2017•2 citations

Far Fewer Qubits Required for “Quantum Memory” Quantum Computers

Erika K. Carlson

Incorporating storage units for quantum information into quantum computers may allow researchers to build such devices with several orders of magnitude fewer qubits in their processors.

Physics•Sep 28, 2021•0 citations

Adiabatic quantum search algorithm for structured problems

Jérémie Roland, Nicolas J. Cerf

The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.

arXiv:quant-ph/0304039•Physical Review A•Dec 15, 2003•29 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

Quantum search algorithms in science and engineering

Colin P. Williams

The kinds of search algorithms that can run on quantum computers are qualitatively different from those that run on classical computers. As this article shows, quantum searches are thus vastly more efficient on certain kinds of problems.

Computing in Science & Engineering•Jan 1, 2001•14 citations
this paper, we start answering this question by showing the following: for quantum search, even when we do not have enough qubits, we can still get a partial speedup. The fact that we do get a partial speedup for quantum search makes us hope that even when we do not have all the qubits, we can still get a partial speedup for other quantum computing algorithms as well
Quantum algorithms could efficiently solve certain classically intractable problems by exploiting quantum parallelism. To date, whether the quantum entanglement is useful or not for quantum computing is still a question of debate. Here, we present a new quantum algorithm to show that entanglement could help to gain advantage over classical algorithm and even the quantum algorithm without entanglement. Furthermore, we implement experiments to demonstrate our proposed algorithm using superconducting qubits. Our results show the viability of the algorithm and suggest that entanglement is essential in getting quantum speedup for certain problems in quantum computing, which provide a reliable and clear guidance for developing useful quantum algorithms in future.
The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.