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•47 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•31 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

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•100 citations

Quantum Search-To-Decision Reductions and the State Synthesis Problem

Sandy Irani, Anand Natarajan, Chinmay Nirkhe +2 more

It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the $\textit{de facto}$ computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for $\mathsf{QMA}$, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a $\mathsf{QMA}$ problem up to inverse polynomial precision by making one query to a $\mathsf{PP}$ decision oracle. We complement this result by showing that $\mathsf{QMA}$-search does $\textit{not}$ reduce to $\mathsf{QMA}$-decision in polynomial-time, relative to a quantum oracle. We also explore the more general $\textit{state synthesis problem}$, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes $O(n)$ queries to a classical oracle to prepare an $n$-qubit state, and asked if the query complexity could be made sublinear.

arXiv:2111.02999•Leibniz international proceedings in informatics•Nov 4, 2021•31 citations

Quantum Effects in Algorithms

Richard Jozsa

We discuss some seemingly paradoxical yet valid effects of quantum physics in information processing. Firstly, we argue that the act of ``doing nothing'' on part of an entangled quantum system is a highly non-trivial operation and that it is the essential ingredient underlying the computational speedup in the known quantum algorithms. Secondly, we show that the watched pot effect of quantum measurement theory gives the following novel computational possibility: suppose that we have a quantum computer with an on/off switch, programmed ready to solve a decision problem. Then (in certain circumstances) the mere fact that the computer would have given the answer if it were run, is enough for us to learn the answer, even though the computer is in fact not run.

arXiv:quant-ph/9805086•May 29, 1998•15 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
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.
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the de facto\textit{de facto}de facto computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for QMA\mathsf{QMA}QMA, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a QMA\mathsf{QMA}QMA problem up to inverse polynomial precision by making one query to a PP\mathsf{PP}PP decision oracle. We complement this result by showing that QMA\mathsf{QMA}QMA-search does not\textit{not}not reduce to QMA\mathsf{QMA}QMA-decision in polynomial-time, relative to a quantum oracle. We also explore the more general state synthesis problem\textit{state synthesis problem}state synthesis problem, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes O(n)O(n)O(n) queries to a classical oracle to prepare an nnn-qubit state, and asked if the query complexity could be made sublinear.
We discuss some seemingly paradoxical yet valid effects of quantum physics in information processing. Firstly, we argue that the act of ``doing nothing'' on part of an entangled quantum system is a highly non-trivial operation and that it is the essential ingredient underlying the computational speedup in the known quantum algorithms. Secondly, we show that the watched pot effect of quantum measurement theory gives the following novel computational possibility: suppose that we have a quantum computer with an on/off switch, programmed ready to solve a decision problem. Then (in certain circumstances) the mere fact that the computer would have given the answer if it were run, is enough for us to learn the answer, even though the computer is in fact not run.